3 ms·
> Issues with open addressing are issues like clustering if linear probing is used. Robin Hood hashing more or less solves that problem. > When we delete keys
by dragontamer 7y ago
> Issues with open addressing are issues like clustering if linear probing is used.
Robin Hood hashing more or less solves that problem.
> When we delete keys, we have to leave "tombstone" entries in their place, so that the linear probing can continue past them to find other items.
Actually no. Even ignoring Robin Hood Hashing, you just swap a later element into place.
idx = hash(value);
delete(array[idx]);
for(int i=idx+1; array[i] != empty; i = (i+1) % TABLE_SIZE){
if(hash(array[i].value) <= idx){
array[idx] = array[i];
idx = i; // Repeat for the new location
}
}
I just typed the above in like 2 minutes, so there's probably a bug. But its probably "correct enough" that you can get the concept. There's no tombstones needed for linear probing (and only linear probing).
Conceptually, you can see that array[i] is simply being "re-hashed" into the hash table. Donald Knuth in "The Art of Computer Programming" proves that the above procedure (well... the correct bug-free version at least) is equivalent to clearing out the hash table and rehashing all elements. Except of course, the above procedure is way faster.
--------
Robin Hood hashing solves the problem in a different way. See this other guy's blog post for details: https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ https://www.sebastiansylvan.com/post/robin-hood-hashing-shou...
- kazinator 7y agoWhat you have to do is walk the linear (or whatever) probe sequence completely to find two elements: the to-be-deleted element, and the last element in the sequence. Then if the to-be-deleted element exists, and is the same as the last element, we just mark that element as a free slot. Otherwise, we move the last element over the to-be-deleted element and mark last element's slot free. Of course, "the last element" has to be one which belongs to the original starting hash slot S. We must check that its hash value odulo the table size is S. The first element that we encounter which not followed by an occupied slot is not necessary that last element.
- dragontamer 7y ago> Otherwise, we move the last element over the to-be-deleted element and mark last element's slot free. That doesn't work at all. Consider a hash table of size 5: [Foo, Bar, 0, 0, 0], where 0 represents "empty" locations. Assume "Foo" is in "slot#0" (0-indexed arrays. Note that Knuth in The Art of Computer Programming works with 1-indexed arrays) Lets say we delete Foo. Bar does NOT necessarily want to go into location #0. For example, hash(Bar) might == 1 (in the case of linear probing). So in this case, we want to leave Bar exactly where it is. That's why I have the "if(hash(array[i].value) <= idx){" line in the code. However, this conditional seems impossible to write in the case of quadratic (or other forms) of hashing. This if-statement ONLY works on linear-probing. ---------- Consider this other pattern (still Quadratic probing): [Foo, Bar, 0, 0, Foo2], where Hash(Foo) == Hash(Foo2) == 0. While Hash(Bar) == 1. Lets say you want to delete Bar. How do you know to "move" Foo2 into Slot#1 ? You don't. There's no easy pattern to check for here. Quadratic-probing requires the tombstone method. ---------- The code I presented is very subtle (subtle enough that I probably have a few bugs in it). It works because linear probing has a very predictable sequence. Quadratic probing, and other forms of probing (ex: double hashing, Cuckoo hashing, etc. etc.) are very irregular, and hard to figure out if an object "should" be moved back. ------------ There's a lot of ways of thinking about this problem. But I'm pretty sure the description you gave is incorrect. My preferred way of understanding the problem is as follows: 1. Upon any deletion, you want to perform a set of operations that is equivalent to rebuilding the Hash Table from scratch. 2. The procedure I listed before, is provably equivalent to rebuilding the hash table from scratch. (Most elements stay where they are). At least, if I didn't write a bug in it accidentally... -------- > The first element that we encounter which not followed by an occupied slot is not necessary that last element. I disagree. An empty slot, __in the case of linear probing__, guarantees that you've finished the chaining sequence. That's why linear probing is best. Because you have simple guarantees for which objects are part of a "collision chain", and which ones aren't. This means that deletion under linear-probing can be implemented efficiently. But deletion under other probing schemes (ex: Quadratic) requires the inefficient "tombstone and vacuum" procedure you were describing. There's a lot of subtleties at play here which makes linear probing the best. And a lot of textbooks get these details wrong (ex: the Cormen book!!).