Here is a simple Hashtable for the community. Tell me what you think.
Scott Knowles
Flickerpath
Scott Knowles
Flickerpath
' A simple Hashtable. ' ' A hashtable allows the storage of large number of ' objects, but with quick object retrieval. ' ' A hashtable is really just an array of lists. Each object ' is mapped to a String. By using a simple calculation the ' String can be changed into an index. ' ' The object is added to the list at that index and retrieved ' by searching the list at that index. Since the lists are ' short, the object can be found quickly, compared to searching ' the entire collection. How long the list is depends on the ' capacity, the length of the list array. Determining the ' right capacity is important in the efficientcy of the table. ' ' Here is the calculation to create the index from the name: ' ' index = calcHashCode(name) Mod capacity ' ' The calcHashCode function is found at the bottom of the Type ' and capacity is the length of the array of lists. ' ' TODO: Add the ability to redistribute the table by resizing ' the array of lists. ' ' author: Scott Knowles ' Entry within the hash table Type HashEntry Field obj:Object Field name:String Function CHashEntry:HashEntry(n:String, o:Object) Local he:HashEntry = New HashEntry he.obj = o he.name = n Return he End Function End Type Type Hashtable ' Member variables Field capacity:Short = 0 ' The capacity is the length of the buckets array Field size:Short = 0 ' The # of objects within the table Field buckets:TList[] = Null ' The array of TList objects to hold the Objects ' Functions ' Create hashtable ' psize : number of buckets to have Function CHashtable:Hashtable(psize:Short=200) Local ht:Hashtable = New Hashtable ht.IHashtable(psize) Return ht End Function ' Create hashtable by copy ' ht : the source hashtable Function CPHashtable:Hashtable(sourceht:Hashtable) Local ht:Hashtable = New Hashtable ht.ICPHashtable(sourceht) Return ht End Function ' Methods ' Initialize the hashtable Method IHashtable(psize:Short=30) capacity = psize buckets = New TList[capacity] End Method ' Initialize the hashtable by copying another Method ICPHashtable(ht:Hashtable) capacity = ht.capacity size = ht.size buckets = New TList[capacity] Local list:TList = Null Local i:Short = 0 For i = 0 To size-1 If ht.buckets[i] <> Null list = TList(ht.buckets[i]) buckets[i] = list.Copy() End If Next End Method ' Delete a hashtable Method DHashtable(ht:Hashtable) buckets = Null End Method ' Add an Object to the table, based upon name in object ' name : The name to list the object under ' obj : The object to add ' check: Check if name already exists ' if the name already exists an exception is thrown Method AddObject(name:String, obj:Object, check=True) Local index = calcHashCode(name) Mod capacity If buckets[index] = Null Then buckets[index] = CreateList() If check Then If Contains(name) Then Throw "Duplicate name: "+name+" being added To hashtable" End If Local he:HashEntry = HashEntry.CHashEntry(name, obj) buckets[index].AddLast(he) size:+1 End Method ' Does the hashtable already contain that name ' name : The name to check for Method Contains(name:String) Local tl:TLink = GetTLink(name) If tl = Null Then Return False Return True End Method ' A helper function for Contains, GetObject and Remove ' name: The name to check for Method GetTLink:TLink(name:String) Local index:Short = calcHashCode(name) Mod capacity If buckets[index] = Null Then Return Null If buckets[index].Count() = 0 Then Return Null Local lo:TListEnum = buckets[index].ObjectEnumerator() Local he:HashEntry = Null Local link:TLink = Null While lo.HasNext() link = lo._link he = HashEntry(lo.NextObject()) If he.name = name Return link Wend Return Null End Method ' Get an Object from the Hashtable ' name : The name to find ' return: The object listed under that name ' If the table contains more than one Object of that name the first ' Object with that name in the given list is returned Method GetObject:Object(name:String) Local tl:TLink = GetTLink(name) If tl = Null Then Return Null Local he:HashEntry = HashEntry(tl._value) Return he.obj End Method ' Remove an object from the table ' name: The name of the object to remove Method RemoveObject:Object(name:String) Local tl:TLink = GetTLink(name) If tl = Null Then Return Null Local he:HashEntry = HashEntry(tl._value) tl.Remove() size:-1 Return he.obj End Method Method toString:String() Return "capacity = " + capacity + " size = " + size End Method ' Calculate the hashcode for a name Method calcHashCode(n:String) Local hc = 0 Local l = Len(s) Local i:Byte = 0 For i = 0 To l hc = hc * 131 + Asc(Right(s,l-i)) Next If hc < 0 Then hc = hc * -1 Return hc End Method End Type