Hash

I've been working to speed up some code and the original was a straight list which made finding entries slow, so it makes sense to try and speed this up with a better set-up. Now you can either use something like a binary tree or use a hash to look it up. Binary tree's are good, but can get unbalanced easily if it's a dynamic list, so I've opted for a simple hashing table. Now this is a VERY simple hashing table, but still far outstrips a straight array.

Each object I have uses a 32 bit INT as an ID, so I can use that as the HASH access. The simplest way of hashing this is to use the lower "X" bits as an access to multiple lists meaning we simply have far less to look through to find our object.

So, imagine an array of 512 linked lists, with each list being accessed with the lower 9 bits of the object ID. Pretty simple, and simple means quick. It's also worth noting I could use 512 binary tree's if need be, but I simply don't need that. And that's it, it's as simple as that.

Now I'm not a fan of templates, I think they are used far to often for really simple things, and then you end up with templates inside templates which means people simply don't know (or understand) what's going on inside the compiler generated code. STL suffers a lot from this, it's so old now, and has been updated so much, it's now crippling. Still, templates have their place and this is an ideal situation where a template will do some real good. So, I've dusted off my template head and written a very simple Hash template - which I'm now going to let you all have a play with.

The first thing to decide when writing a general API like this, is figuring out exactly how you want it to look, and what is the best use case. I normally do this by writing some sample code which will use the API in very pretty manner, then write the actual code around the desired API. So here's the API I've gone for; or rather some sample code showing it's use.

 TestObj* pObj;

 // Make the HASH table with 512 linked lists (must be POW2)
 Hash* HashTable = new Hash(512);
 
 // Add some dummy objects
 HashTable->Add( 0, new TestObj(0) );
 HashTable->Add( 14, new TestObj(14) );
 HashTable->Add( 271334, new TestObj(271334) );
 HashTable->Add( 512, new TestObj(512) );
 HashTable->Add( 512*10, new TestObj(512*10) );


 // Itterate over the WHOLE list
 Hash::iterator Iterator = HashTable->GetIterator();
 while( *Iterator != NULL )
 {
  pObj = *Iterator;
  Iterator.Next();           // Doing this here means we can delete the pObj from the list if we wish
  
  // Do code here....
 }


 // General functions...
 pObj = HashTable->Find( 512*10 );
 HashTable->Delete( 0 );    // Delete HASH index + object
 HashTable->Delete( 512*10 );   // Delete HASH index + object
 HashTable->Remove( 271334 );   // REMOVE from hash table, but DON'T delete the object!

And that's all there is too it. Very simple simple, but works. This operates very much like a C# Dictionary<> so is pretty nice to use. If you find that it's getting slow due to a high number of objects, you can either increase the base array size, or you could change the internal storage from a linked list, into a binary tree or something.

Anyway, you can get the template here: Hash.h

Hope it's of use to someone - Enjoy!