Nice job,
A hash table is basically an optimized way of retrieving an object given a name through grouping. You can see this strategy in dictionarys, where words are grouped by their first letter, so the first step in finding a word is to skip to the section of the dictionary with the first letter of the word. This greatly optimizes the process of finding the word. This hash-table calculates a unique number for each word (ok, so words linger than about 8 charachters will make it loop around). This is modded by the capacity of the table, so that an index within the table is computed. Then, it adds the element to the linked list at that location. Upon retrieval, it can simply re-perform the calculation upon the name, and narrow the search down by a great amount. For instance, if you have 200 possible hash instances, on average the amount you have ot search from say, a list, is divided by 200.
There is, however, one error in the code (calcHashCode) that prevents it from working correctly, infact, all elements will have an index of 0, since it uses the variable s rather than the parameter n. Also, this should be a function I think. I also changed the names of some of the methods to be OOP.
A hash table is basically an optimized way of retrieving an object given a name through grouping. You can see this strategy in dictionarys, where words are grouped by their first letter, so the first step in finding a word is to skip to the section of the dictionary with the first letter of the word. This greatly optimizes the process of finding the word. This hash-table calculates a unique number for each word (ok, so words linger than about 8 charachters will make it loop around). This is modded by the capacity of the table, so that an index within the table is computed. Then, it adds the element to the linked list at that location. Upon retrieval, it can simply re-perform the calculation upon the name, and narrow the search down by a great amount. For instance, if you have 200 possible hash instances, on average the amount you have ot search from say, a list, is divided by 200.
There is, however, one error in the code (calcHashCode) that prevents it from working correctly, infact, all elements will have an index of 0, since it uses the variable s rather than the parameter n. Also, this should be a function I think. I also changed the names of some of the methods to be OOP.
' 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 ' Small modifications by Bot_Builder Strict ' 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 Create:Hashtable(psize:Short=200) Local ht:Hashtable = New Hashtable ht.Init(psize) Return ht End Function ' Create hashtable by copy ' ht : the source hashtable Function Copy:Hashtable(sourceht:Hashtable) Local ht:Hashtable = New Hashtable ht.InitCopy(sourceht) Return ht End Function ' Methods ' Initialize the hashtable Method Init(psize:Short=30) capacity = psize buckets = New TList[capacity] End Method ' Initialize the hashtable by copying another Method InitCopy(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 Rem unecessary, once hashtable is freed by flushmem, buckets will be freed as well. ' Delete a hashtable Method DHashtable(ht:Hashtable) buckets = Null End Method EndRem ' 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 Add(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 Function calcHashCode(s: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 Return Abs(hc) End Function End TypeExample:
Local MH:HashTable=HashTable.Create() MH.Add("Greeting","Hi") MH.Add("Cow","Moo") MH.Add("5+5=","10") MH.Add("2+2=","4") Print String(MH.GetObject("Cow")) Print String(MH.GetObject("Greeting")) Print String(MH.GetObject("2+2="))