Sep 02, 2016

> How do you know what the commenter (erichocean) meant?

Because "bucket" is a well-defined term-of-the-art with regard to cuckoo hashes, because Erich has demonstrated deep knowledge of similar algorithms in the past, because I've been thinking about improving the memory locality of cuckoo hashes for years, and because I would have used approximately the same phrasing as Erich did to describe the memory locality advantages of "buckets".

If they say that using "buckets" can mean the same locality of memory references as linear probing, their interpretation of what "buckets" mean must deal with that problem in some way.

Not only do buckets "deal" with locality, because of the granular nature of cachelines and parallel abilities of memory controllers, searching two compact small regions turns out to be just as searching one region of twice the size. Vectorized linear probing and SIMD cuckoo hashes are so similar that your question very likely indicates that you are not using the same terminology as others are.

Here's paper that offers a good comparison:

  Rethinking SIMD Vectorization for In-Memory Databases
  Polychroniou, Roghaven, and Ross (2015) 
http://www.cs.columbia.edu/~orestis/sigmod15.pdf