Skip to content
Snippets Groups Projects
  1. Mar 29, 2013
  2. Mar 22, 2013
  3. Mar 21, 2013
  4. Mar 19, 2013
  5. Mar 15, 2013
    • Marek Vavrusa's avatar
      Hopscotch hashing for resolving collisions in RRL. · 674c7fab
      Marek Vavrusa authored
      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
      674c7fab
  6. Mar 13, 2013
  7. Mar 12, 2013
  8. Mar 11, 2013
  9. Mar 01, 2013
  10. Feb 28, 2013
Loading