I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I thought there could only possibly be one block, since linear probing will go through all addresses sequentially?


1 Answer 1


For single key, there is only one block. But as it grows, it may reach the next cluster, making this cluster much larger:


Here aaaa is cluster for "a" key, and bbbb is cluster for "b" key. Once you fill the first "." entry with data, clusters are combined. Now the next item for "a" key will be inserted after bbbb, so find() operation need to search the entire cluster:


There are techniques such as Robin Hood hashing which keeps all keys sorted by the position of the first entry where they can be stored, so the same data will build the following table:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.