Re: [boost] Idea for O(1) hash-table

On Sat, Mar 16, 2013 at 2:35 PM, Shakti Misra wrote:

Hi, May be you can add in boost.hash. it will be a good add. On Mar 16, 2013 2:42 PM, "Rani Sharoni" wrote:

...

Hi All,

I hope that you will find the following idea interesting. [...]

Lookup(key): for (hash = key, I = 0 ; I < K ;++i) { hash = HASH(hash); // double-hashing if (A[hash % N][i] == key) return found; }

return not-found;

The trick is to perform “re-insert”: Pick some random element, key1, from failed insert phase, replace it with the new key, and (re) Insert(key1).

...

Though this hash-table is general purposed it has some interesting properties: 1) O(1) non-amortized with very low chance for collisions (each key has its own unique “virtual” bucket). 2) Can be implemented on continuous memory without pointers and with excellent utilization 3) Allow wait free implementation of caches (i.e. no lock or even interlocked needed). 4) Allow caches on shared memory – corruption safe/hazard algorithm (assuming at least 64 bit keys). 5) Allow persistent using direct memory to file mapping (i.e. disk representation is same as in-memory one). 6) Average 50% LRU eviction for caches (i.e. on average entry half from the oldest is evicted)

BTW – there is little chance for patenting this algorithm since I already published similar idea in the public domain ;-)

After little wiki digging I saw that my idea is already well established and known as "Cuckoo Hashing" (2001): http://en.wikipedia.org/wiki/Cuckoo_hashing http://www.ru.is/faculty/ulfar/CuckooHash.pdf Sorry for the noise. IMHO, you should consider having such hashing/caching scheme in boost...