Society of Robots - Robot Forum

Software => Software => Topic started by: lemontree on June 19, 2009, 12:22:43 AM

Title: Hash Table with adjustable Jitter Table
Post by: lemontree on June 19, 2009, 12:22:43 AM
Microsoft in their benevolence toward all human kind shares this information with us:
http://research.microsoft.com/en-us/um/people/hoppe/perfecthash.pdf (http://research.microsoft.com/en-us/um/people/hoppe/perfecthash.pdf)
The idea is to create a hash function that has an additional user defined jitter table that you can use to prevent collisions in a hash  table, and further you can use it to create a prefect hash table, where each slot in the hash table contains exactly one data item, ie there are no empty slots and no collisions.

My insight is that you could replace the jitter table with a few Bloom filters, eg. b1(x),b2(x),b3(x)
Hence the resulting hash function would be H(x)=h(x)+b1(x)+2*b2(x)+4*b3(x)
That would be a lot easier to program and perhaps better than the greedy algorithm microsoft use to create the jitter table. 
I don't have the 3 or 4 days I would require to test my idea, so I just throw it out into internet space.
Title: Re: Hash Table with adjustable Jitter Table
Post by: lemontree on June 19, 2009, 11:04:14 PM
Well whatever.  I also found this information about cuckoo hashing:
http://en.wikipedia.org/wiki/Cuckoo_hashing (http://en.wikipedia.org/wiki/Cuckoo_hashing)
It does seem there is renewed interest in the hash table related topics now. 
You can put simple ideas together in ingenious ways and maybe come up with human level AI.
If you don't want to get involved in heavy duty maths but you still want to do AI then hash tables/bloom filters are a good area to get into.
Title: Re: Hash Table with adjustable Jitter Table
Post by: awally88 on June 20, 2009, 03:18:24 AM
Hash tables are amazing when they work properly O(1) lookup, addition and deletion, its just that a good hash function is hard to write, and a O(n) rehash is worrying at times in robot applications. The jitter table method looks good for removing collisions though it just starts to get away from the O(1) properties of the hashtables. I'll have a look at this more when I have more time.