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?
Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For single key, there is only one block. But as it grows, it may reach the next cluster, making this cluster much larger:
aaaa.bbbb...
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:
aaaaabbbba..
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:
aaaaaabbbb..
