Simple Hashtable

BlitzMax Forums/BlitzMax Programming/Simple Hashtable

scooter43

(Posted 2005) [#1]

Here is a simple Hashtable for the community. Tell me what you think.

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

ImaginaryHuman

(Posted 2005) [#2]

Cool, thanks!

So a hashtable is what's used for, say, a web-browsers cache of images/pages? ... where you see all those folders with long strings of characters?

Bot Builder

(Posted 2005) [#3]

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 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 Type

Example:

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="))

scooter43

(Posted 2005) [#4]

Thanks for catching my error... that is what you get for too much copying and pasting from BlitzPlus...

I would prefer to just have a function called Create, Copy, Init and InitCopy, but BlitzMax does not allow for function overloading (same function name, different number of arguments)

Take a look at the code below if my explanation didn't make sense.

If I wanted to inherit from Hashtable, but make another function called Create that takes 2 shorts instead of one.

Import "Hashtable.bmx"

Type OptHashTable Extends Hashtable
  Field resizeAt:Short=2000     ' The size to redistribute the objects
  Function Create:OptHashTable(psize:Short=200, resizeCount:Short=2000)
     Local oht:OptHashtable = New OptHashtable
     oht.Init(psise)
     resizeAt = resizeCount
     return oht
  End Function  
End Type

If I tried to compile this, it would fail because Hashtable's Create only takes a single short, while OptHashtable's Create takes 2 shorts... the compiler complains... check out my post
http://www.blitzbasic.com/Community/posts.php?topic=42732

So I came up with this naming convention

C+<Type Name> = Create Type
CP+<Type Name> = Copy Type
I+<Type Name> = Init Type
IP+<Type Name> = Init Copy Type

I would prefer not having to do this... but you work with what you've got.

Thanks again for the bug fix.