diff options
| author | Marek Vavrusa <marek.vavrusa@nic.cz> | 2013-03-15 09:51:27 +0100 |
|---|---|---|
| committer | Marek Vavrusa <marek.vavrusa@nic.cz> | 2013-03-15 09:51:27 +0100 |
| commit | 674c7fab258e3a8f197c5bb773be5ef1be5c1e5d (patch) | |
| tree | 602fc2a9696a2c6353a0fb48a23b404ae994394c /samples | |
| parent | Remove empty block in --enable-lto, this should fix older autoconf (diff) | |
| download | knot-674c7fab258e3a8f197c5bb773be5ef1be5c1e5d.tar.xz knot-674c7fab258e3a8f197c5bb773be5ef1be5c1e5d.zip | |
Hopscotch hashing for resolving collisions in RRL.
The idea is to insert colliding items in the H distance of
the original hash value. H must be chosen to accomodate log(N)
items, we use sizeof(unsigned). Unlike in linear probing,
lookup is always in constant time and doesn't require
extra memory and chaining costs as in external chaining.
Extra memory is just sizeof(unsigned) per bucket.
Builtin __builtin_ctz() is used for fast hop lookup.
Herlihy, Maurice and Shavit, Nir and Tzafrir, Moran (2008).
"Hopscotch Hashing". DISC '08: Proceedings of the 22nd
international symposium on Distributed Computing.
Arcachon, France: Springer-Verlag. pp. 350--364.
http://people.csail.mit.edu/shanir/publications/disc2008_submission_98.pdf
Diffstat (limited to 'samples')
0 files changed, 0 insertions, 0 deletions