HashTable object

BlitzMax Forums/BlitzMax Programming/HashTable object

Defoc8

(Posted 2006) [#1]

Ok, i figured id share this type/class with the community..
already sent a copy to noel, but no doubt others would like
a basic hashtable system too..

this is my first bmax class - perhaps not great, but it does
the job...anyway enjoy ;)

feel free to credit me if you use it :]


''InsertEntry(name:string,o:object) - add an object to the table, the name is used to
''                                    to generate an index 0-255, selecting the list.
''
''RemoveEntry(name:string) - if you need to remove an object.
''
''GetEntry(name:string) - grab an entry, you must cast is back to its original type,
''                        myobject=myType(GetEntry(name:string))
''
''
''Flush() - removes all objects from the hash table                                    
''
''

''all entries should have unique names - you should first getEntry(), if this returns
''null - its safe to insert the new object, if it returns a valid object, you may want
''to return this object back to the user...


'''''''''''''''''''''''''''
''
''HASHTABLE OBJECT
''
''- M.Laurenson/Defoc8 2006
''''''''''''''''''''''''''''


Type gHashTable

 Field table:TList[]
 
 Method New()
  table=table[..256]
  For Local n:Int=0 To 255
   table[n]=CreateList()
  Next
 EndMethod

 Method genIndex(name$)
  Local val:Int=0
   For Local n:Int=0 To name.length-1
    val=val+(name[n]^2)
   Next
   val=(val&255)  
  Return val
 EndMethod

 Method insertEntry(name:String,obj:Object)
  Local index:Int=genIndex(name$)
  Local entry:gHashEntry=New gHashEntry
    entry.name=name
    entry.obj=obj 
    entry.link=ListAddLast(table[index],entry)
 EndMethod

 Method removeEntry(name:String)
  Local index:Int=genIndex(name)
   For Local entry:gHashEntry=EachIn table[index]
    If(entry.name=name)
     RemoveLink(entry.link)
     Return
    EndIf
   Next
 EndMethod                 

 Method getEntry:Object(name:String)
  Local index:Int=genIndex(name)
   For Local entry:gHashEntry=EachIn table[index]
    If(entry.name=name)
     Return(entry.obj)
    EndIf
   Next
  Return Null
 EndMethod

 Method flush()
  For Local n:Int=0 To 255
   ClearList(table[n])
  Next
 EndMethod 

 Method getEntryCount(index:Int)
   Return CountList(table[index])
 EndMethod
EndType

Type gHashEntry
 Field name:String
 Field obj:Object
 Field link:TLink
EndType

FlameDuck

(Posted 2006) [#2]

table=table[..256]

You should use a prime number as the number of buckets. Like 257. Otherwise it looks like an okay implementation.

Defoc8

(Posted 2006) [#3]

hmmm...i dont actually see why the number of buckets
should be prime - doesnt this depend on the system used
to generate the bucket selection? regardless, i have tested
the distrubution on multiple data sets & the results have
been good - its a simple system, this doesnt mean its bad.

Anyway- the code is public, so anyone can modify it..

N	(Posted 2006) [#4]

I figure I may as well share the version I molested...

Rem
    HASHTABLE OBJECT
    
    - M.Laurenson/Defoc8 2006
EndRem

Rem
    While not explicitly mentioned in the code (most of you probably
    overlooked the actual writing in the post), I can promise
    you Def would appreciate if you credited him if you used this.
    No credit is to go to me.
    
    -Noel
EndRem

Strict

Public

Import "hash.c"

Extern "C"
    Function __c_hash:Int(key$z, length:Int, initval:Int)="Hash"
EndExtern

Global HashKey:Int(name:String) = gHashKey

Function gHashKey%( name:String )
    Return __c_hash( name, name.Length, 0 )
End Function

Type gHashTable
    'private:

    Field table:TList[]
    
    'protected:
    
    Method _rement(key:Int)
        For Local entry:gHashEntry = EachIn table[key Shr 24]
            If entry.key = key
                entry.link.Remove( )
                Return
            EndIf
        Next
    End Method
    
    Method _addent(key:Int,o:Object)
        Local entry:gHashEntry = New gHashEntry
        entry.key = key
        entry.obj = o 
        entry.link = table[key Shr 24].AddLast(entry)
    End Method
    
    Method _getent:Object(key:Int)
        For Local entry:gHashEntry = EachIn table[key Shr 24]
            If entry.key = key
                Return entry.obj
            EndIf
        Next
        Return Null
    End Method
    
    'public:
    
    Method New()
        table=New TList[256]
        For Local n:Int = 0 To 255
            table[n] = New TList
        Next
    End Method
    
    Method SetEntry( name:String, obj:Object )
        Local key:Int = HashKey( name )
        Local o:Object = _getent(key)
        If o And o <> obj Then _rement(key)
        _addent(key,obj)
    End Method
    
    Method InsertEntry(name:String,obj:Object)
        Local key:Int = HashKey( name )
        _addent(key,obj)
    End Method
    
    Method RemoveEntry(name:String)
        Local key:Int = HashKey( name )
        _rement(key)
    End Method
    
    Method GetEntry:Object(name:String)
        Local key:Int = HashKey( name )
        Return _getent(key)
    End Method
    
    Method Flush()
        For Local n:Int = 0 To 255
            table[n].Clear( )
        Next
    End Method 
    
    Method GetEntryCount(index:Int)
        Return table[index].Count( )
    End Method
End Type

Type gHashEntry
    Field key:Int
    Field obj:Object
    Field link:TLink
End Type

hash.c

/*
    Code by Bob Jenkins, December 1996, Public Domain.  Plus some minor,
    minor tweaks by Noel Cower.  Nothing that affects the implementation.
    You can use this free for any purpose.  It has no warranty.
*/

#define mix(a,b,c) \
{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8); \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12);  \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5); \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}

int Hash( k, length, initval )
register const unsigned char *k;        /* the key */
register int  length;   /* the length of the key */
register int  initval;    /* the previous hash, or an arbitrary value */
{
   register int a,b,c,len;

   /* Set up the internal state */
   len = length;
   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
   c = initval;           /* the previous hash value */

   /*---------------------------------------- handle most of the key */
   while (len >= 12)
   {
      a += (k[0] +((int)k[1]<<8) +((int)k[2]<<16) +((int)k[3]<<24));
      b += (k[4] +((int)k[5]<<8) +((int)k[6]<<16) +((int)k[7]<<24));
      c += (k[8] +((int)k[9]<<8) +((int)k[10]<<16)+((int)k[11]<<24));
      mix(a,b,c);
      k += 12; len -= 12;
   }

   /*------------------------------------- handle the last 11 bytes */
   c += length;
   switch(len)              /* all the case statements fall through */
   {
   case 11: c+=((int)k[10]<<24);
   case 10: c+=((int)k[9]<<16);
   case 9 : c+=((int)k[8]<<8);
      /* the first byte of c is reserved for the length */
   case 8 : b+=((int)k[7]<<24);
   case 7 : b+=((int)k[6]<<16);
   case 6 : b+=((int)k[5]<<8);
   case 5 : b+=k[4];
   case 4 : a+=((int)k[3]<<24);
   case 3 : a+=((int)k[2]<<16);
   case 2 : a+=((int)k[1]<<8);
   case 1 : a+=k[0];
     /* case 0: nothing left to add */
   }
   mix(a,b,c);
   /*-------------------------------------------- report the result */
   return c;
}

"If it ain't broke, don't fix it" doesn't really apply to Def's code ;) Then again, I'm rather notorious for fixing that which isn't broken.

FlameDuck

(Posted 2006) [#5]

i dont actually see why the number of buckets
should be prime - doesnt this depend on the system used
to generate the bucket selection?

Yes. Which should also use primes to reduce the risk of hash collisions. Perhaps you could also distribute your test code, so others could have a go at testing it? Have you tried adding the canonical location of all files on your root drive, for example? I know that dataset in particular took down early Java hashing algorithms (because they where radix based, and thus would generate identical hashes, for nearly identical keys, where as a solid hashing algorithm generates wildly different hashes from similar keys).

its a simple system, this doesnt mean its bad.

I'm not saying it is.

Duckstab[o]

(Posted 2006) [#6]

Can someone show a mini demo of the hash tables in use please

klepto2

(Posted 2006) [#7]

Well, first I have to say : nice thing. but as second I have to ask:
Isn't a Hashtable Type already included in BMAX which is called TMap. And what is the advantage of this system in comparison to the TMap type?

Defoc8

(Posted 2006) [#8]

hey im new to bmax - i jst thought id share stuff :p
- and good stuff noel ;) :]

klepto2

(Posted 2006) [#9]

Don't get me wrong,Your stuff is very good. I only was thinking about it. So keep up and share more stuff ;)

FlameDuck

(Posted 2006) [#10]

Isn't a Hashtable Type already included in BMAX which is called TMap.

No. TMap is a Set implemented as a binary search tree.

And what is the advantage of this system in comparison to the TMap type?

'This system' has close to constant look-up times. TMap has Log(n). Also this hashTable implementation doesn't appear to be a Set (that is, the same object can be indexed more than once).

It's a trade of between speed and space.

N	(Posted 2006) [#11]

Duckstab: Here you go. It's a pseudo-managed resource handler. You request a resource, it's loaded into memory, and then only unloaded when all the banks created with its buffer are deleted (or when you call UnloadResources( )).

There are better ways to do this, but this is a rudimentary example.

'' Use's Defoc8's nice hash table code (modified, of course)

Strict

Import "src/hashtable.bmx"

Private

Global _rtable:gHashTable = New gHashTable

Type IResource
    Field path$
    Field buffer@ Ptr = Null
    Field refs%
    Field size%
    Field key%
    
    Method AsBank:TBank( )
        Open( )
        If buffer = Null Then Return
        Return IResBank.CreateRes( buffer, size, key )
    End Method
    
    Method Open( )
        refs :+ 1
        If refs = 1 Then
            Local s:TStream = OpenStream( path, True, False )
            If s = Null Then
                refs = 0
                Return
            EndIf
            size = s.Size( )
            If size = 0 Then
                refs = 0
                Return
            EndIf
            buffer = MemAlloc( size )
            s.ReadBytes( buffer, size )
            s.Close( ); s = Null
        EndIf
    End Method
    
    Method Close( )
        If refs = 0 Then Return
        
        refs :- 1
        
        If refs = 0 Then
            memset_( buffer, 0, size )
            MemFree( buffer )
            buffer = Null
            size = 0
        EndIf
    End Method
    
    Method Delete( )
        While refs
            Close( )
        Wend
    End Method
End Type

Type IResBank Extends TBank
    Field key:Int
    
    Method PokeByte( o%, v% )
        Assert "Cannot write to resource bank"
    End Method
    Method PokeShort( o%, v% )
        Assert "Cannot write to resource bank"
    End Method
    Method PokeInt( o%, v% )
        Assert "Cannot write to resource bank"
    End Method
    Method PokeLong( o%, v:Long )
        Assert "Cannot write to resource bank"
    End Method
    Method PokeFloat( o%, v# )
        Assert "Cannot write to resource bank"
    End Method
    Method PokeDouble( o%, v! )
        Assert "Cannot write to resource bank"
    End Method
    
    Method Delete( )
        Local rs:IResource = IResource( _rtable._getent(key) )
        If rs Then rs.Close( )
    End Method
    
    Function CreateRes:IResBank( buffer@ Ptr, size%, key% )
        Assert size>=0 Else "Illegal bank size"
		Local bank:IResBank = New IResBank
		bank._buf = buffer
		bank._size = size
		bank.key = key
		bank._capacity = -1
		Return bank
    End Function
End Type

Function RBindResources( dir%, cpath$="/", rpath$="./" )
    Local f$ = NextFile( dir )
    While f <> ""
        If f.Find(".",0) = 0 Then
            f = NextFile( dir )
            Continue
        EndIf
        Try
            If FileType( rpath+f ) = 1 Then
                Local r:IResource = New IResource
                r.path = rpath+f
                r.key = gHashKey( cpath+f )
                _rtable._addent( r.key, r )
            ElseIf FileType( rpath+f ) = 2 Then
                Local underling:Int = ReadDir( rpath+f+"/" )
                RBindResources( underling, cpath+f+"/", rpath+f+"/" )
            EndIf
        Catch o:Object
            DebugLog o.ToString( )
            Continue
        End Try
        f = NextFile( dir )
    Wend
End Function

Public

Function UnloadResources( )
    _rtable.Flush( )
    GCCollect( )
End Function

Function LoadResources( ipath$="./" )
    _rtable.Flush( )
    GCCollect( )
    ipath = ipath.Replace("\","/")
    Local dir:Int = ReadDir( ipath )
    RBindResources( dir, "/", ipath )
    CloseDir( dir )
End Function

Function GetResource:TBank( name$ )
    If name[0] <> "/" Then name = "/"+name
    Local key:Int = gHashKey( name )
    Local rs:IResource = IResource( _rtable._getent( key ) )
    If rs Then Return rs.AsBank( )
    Return Null
End Function