Here is my version of a hashtable.
I'm sure someone can make a better one, but it has worked so far for me...
Use it like this...
Each key must be unique and if you try to add one that already exist, it will just skip adding it.
I'm sure someone can make a better one, but it has worked so far for me...
Type TListNode Field NextNode:TListNode Field PrevNode:TListNode Field Key:String Field Value:Object 'Method Delete() 'Print "Key "+Key + " says: -"+Chr(34)+"yeah, I'm free!"+Chr(34) 'End Method Method FindKey:Int(Key:String) Local CurrNode:TListNode = Self Repeat If CurrNode.Key = Key Then Return True If CurrNode.NextNode = Null Then Exit CurrNode = CurrNode.NextNode Forever Return False End Method Method RemoveKey:Int(Key:String) Local CurrNode:TListNode = Self Repeat If CurrNode.Key = Key Then If Not(CurrNode.PrevNode = Null) Then CurrNode.PrevNode.NextNode = CurrNode.NextNode If Not(CurrNode.NextNode=Null) Then CurrNode.NextNode.PrevNode = CurrNode.PrevNode FlushMem() EndIf Return True EndIf If CurrNode.NextNode = Null Then Exit CurrNode = CurrNode.NextNode Forever Return False End Method Method CutPrevNodeLinks() Local CurrNode:TListNode = Self 'Simply go through all nodes and cut the prevnode link... Repeat CurrNode.PrevNode = Null If CurrNode.NextNode = Null Then Exit CurrNode = CurrNode.NextNode Forever End Method Method GetValueByKey:Object(Key:String) Local CurrNode:TListNode = Self Repeat If CurrNode.Key = Key Then Return CurrNode.Value If CurrNode.NextNode = Null Then Exit CurrNode = CurrNode.NextNode Forever Return Null End Method Method Add:Int(Key:String,Value:Object) Local CurrNode:TListNode = Self Repeat If CurrNode.Key = Key Then Return False If CurrNode.NextNode = Null Then Exit CurrNode = CurrNode.NextNode Forever CurrNode.NextNode = New TListNode CurrNode.NextNode.Key = Key CurrNode.NextNode.Value = Value CurrNode.NextNode.PrevNode = CurrNode Return True End Method End Type Type HashTable Field Buckets:Int ' The nr of rows in the array Field HTable:TListNode[] Method New() Buckets = 4093 ' Prime... HTable = HTable[..Buckets] ClearTable() End Method Method ClearTable() For Local i=0 To Buckets-1 HTable[i] = Null Next End Method Function Create:HashTable(NrOfBuckets:Int = 4093) Local NewHT:HashTable = New HashTable NewHT.Buckets = NrOfBuckets NewHT.HTable = NewHT.HTable[..NrOfBuckets] NewHT.ClearTable() Return NewHT End Function Method Add:Int(Key:String,Value:Object) FlushMem() Local hash = HashValue(Key) If HTable[hash] = Null Then 'Ok, no collision. Just create a node here... HTable[hash] = New TListNode HTable[hash].Key = Key HTable[hash].Value = Value Return True Else 'Collision, make sure the key doesn't exist already. If it doesn't add a new node at the end... Return HTable[hash].Add(Key,Value) EndIf End Method Method GetValue:Object(Key:String) Local hash = HashValue(Key) If HTable[hash] = Null Then Return Null Return HTable[hash].GetValueByKey(Key) End Method Method Remove:Int(Key:String) Local hash = HashValue(Key) If HTable[hash] = Null Then Return Null If HTable[hash].Key = Key Then 'Remove Rootnode HTable[hash] = HTable[hash].NextNode FlushMem() Else 'Print "Removed Sub Node" Return HTable[hash].RemoveKey(Key) EndIf End Method Method RemoveAllKeys() For Local i = 0 To Buckets-1 If Not(HTable[i]=Null) Then HTable[i].CutPrevNodeLinks() HTable[i] = Null FlushMem() ' This should release all nodes EndIf Next End Method Method ContainsKey:Int(Key:String) Local hash = HashValue(Key) If HTable[hash] = Null Then Return False Return HTable[hash].FindKey(Key) End Method Method HashValue:Int(Key:String) 'Return Key Mod Buckets Local hash For Local i=0 To Key.Length-1 hash = hash*613 + Key[i] Next If hash>=0 Then Return hash Mod Buckets Else Return -hash Mod Buckets End Method End Type
Use it like this...
Local MyTable:HashTable = HashTable.Create(500) MyTable.Add("Apple","I'm an apple!") MyTable.Add("Pear","I'm a pear!") MyTable.Add("Orange","I'm an orange!") Print String(MyTable.GetValue("Pear")) If MyTable.ContainsKey("Peach")=False then Print "No peach in the table"
Each key must be unique and if you try to add one that already exist, it will just skip adding it.