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

Subject: Re: [boost] Idea for O(1) hash-table
From: Rani Sharoni (ranisharoni75_at_[hidden])
Date: 2013-03-16 12:10:16

On Sat, Mar 16, 2013 at 2:35 PM, Shakti Misra
<shakti.misra.study_at_[hidden]>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" <ranisharoni75_at_[hidden]> 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...