4 ms·
Cuckoo hashing
- yread 15y ago> But we’ve shown that these types of subgraphs don’t appear with high probability! Hence the greedy routine works for hash tables with an occupancy of less than 0.5. I haven't completely understood the probability estimation, but doesn't the insertion algorithm have an infinite worst case running time (albeit not with "high probability")?
- jaekwon 15y agoi guess, without loop detection.
- ErikCorry 15y agoYes, from the original paper: "As it may happen that this process loops, the number of iterations is bounded by a value, MaxLoop, to be specied below. If this number of iterations is reached, everything is rehashed with new hash functions, and we try once again to accommodate the nestless key"
- padenot 15y agoFor those interested in concurrent hashing, this paper [1] shows a remarkable implementation of an hashmap that performs way better that the one presented in the article. [1] : http://www.springerlink.com/content/u710121187m65436/ http://www.springerlink.com/content/u710121187m65436/
- ErikCorry 15y agoAlso described here: http://en.wikipedia.org/wiki/Hopscotch_hashing http://en.wikipedia.org/wiki/Hopscotch_hashing
- barrkel 15y agoAnd if you're especially interested in concurrency (768 cores), see Cliff Click's lock-free hash table: http://video.google.com/videoplay?docid=2139967204534450862 http://video.google.com/videoplay?docid=2139967204534450862
- xtacy 15y agoI am wondering if the benefits of Cuckoo hashing are due to the power of 2 random choices: http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20...
- adrianN 15y agoYes, some of it. You get a very low collision rate due to that.
- thyrsus 15y agoIf the original hash function is f(x), are there reasons the "second" hash function shouldn't be (f(x)+1)mod n (n being the number of hash slots)? I'm sure that some distribution of x would generate pathological behavior, but my question is whether it breaks the reasoning about the probabilities. I'm trying to convince myself that a "second" hash function might be a reasonable cost even for modest n (e.g., when, as in perl, you use hashes to hold the attributes of an object, and the number of attributes will rarely exceed 50).
- andylei 15y agoyou want two items that have the same result from the first hash function to have different results from the second hash function, with relatively high probability. if f1(x0) = f1(x1), you don't want f2(x0) = f2(x1) to happen very much.