Secondly, it is possible for all of a linked list to in fact be in L1.
Thirdly, if by "linear probing" you are at all referring to "open addressing", then there are some disadvantages to consider there.
If we suspect that linked lists are performing badly, the reasonable thing would be to stick with the chained hash table, but replace the chains by little vectors. Essentially, "linear probing" but sideways out of the table, into little sub-tables.
Issues with open addressing are issues like clustering if linear probing is used. If we use quadratic probing, then the table size has to be prime, otherwise we may not be able to able to insert a key into the table even if it is nowhere near full. 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. Things of that sort.
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.
What 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.
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!!).
I think you're underestimating the number of memory redirections that are necessary for chaining. It's more than one. That's the killer.
It's important to be wary of assuming your data will be in cache. It usually isn't. The problem isn't making lots of high density searches in a hash map, the problem is making a search every now and then. A hash map that makes three DRAM accesses will always be worse that one that makes one, regardless of how much work it needs to do, and this is for two reasons. First is there obvious: RAM is slow as balls, we get it. Second is more insidious. You just evicted two cache lines. It's not just the lookup itself that's slower, you also made the consumer of your data structure slower.
Here's a look at what open addressing looks like these days: https://youtu.be/ncHmEUmJZf4 (warning, it's an hour. Takes a while to build up, too. Still worth it.)
Even if the list is fully in L1 at best you'll be able to check an element every 5-6 cycles. With open addressing you can test at least 2 elements per clock cycle, many more with SIMD.
Edit: somehow I missed your mention of partially unrolled lists. Those can of course mitigate many of the downsides.
Comments
Firstly, we have L2 caches, not only L1.
Secondly, it is possible for all of a linked list to in fact be in L1.
Thirdly, if by "linear probing" you are at all referring to "open addressing", then there are some disadvantages to consider there.
If we suspect that linked lists are performing badly, the reasonable thing would be to stick with the chained hash table, but replace the chains by little vectors. Essentially, "linear probing" but sideways out of the table, into little sub-tables.
Issues with open addressing are issues like clustering if linear probing is used. If we use quadratic probing, then the table size has to be prime, otherwise we may not be able to able to insert a key into the table even if it is nowhere near full. 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. Things of that sort.
Robin Hood hashing more or less solves that problem.
Actually no. Even ignoring Robin Hood Hashing, you just swap a later element into place.
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-shou...
What 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.
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...
--------
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!!).
I think you're underestimating the number of memory redirections that are necessary for chaining. It's more than one. That's the killer.
It's important to be wary of assuming your data will be in cache. It usually isn't. The problem isn't making lots of high density searches in a hash map, the problem is making a search every now and then. A hash map that makes three DRAM accesses will always be worse that one that makes one, regardless of how much work it needs to do, and this is for two reasons. First is there obvious: RAM is slow as balls, we get it. Second is more insidious. You just evicted two cache lines. It's not just the lookup itself that's slower, you also made the consumer of your data structure slower.
Here's a look at what open addressing looks like these days: https://youtu.be/ncHmEUmJZf4 (warning, it's an hour. Takes a while to build up, too. Still worth it.)
Even if the list is fully in L1 at best you'll be able to check an element every 5-6 cycles. With open addressing you can test at least 2 elements per clock cycle, many more with SIMD.
Edit: somehow I missed your mention of partially unrolled lists. Those can of course mitigate many of the downsides.