The "how to implement a hash table" article <a href="https://benhoyt.com/writings/hash-table-in-c/" rel="nofollow">https://benhoyt.com/writings/hash-table-in-c/ was really helpful for me. I thought that hash tables were something that were basically impossible to make in C, but this showed that it was simpler.
When I was in university, hash tables were definitely among the things we had to learn about and then implement in C, probably in first year. Per Wikipedia, the concept dates to 1953 (with an implementation in assembly); of course people made them in C once that was an option.
I always liked that idea of just doing a linear wrap-around sweep through an array that holds (key, value) pairs, until you find the pair with the key you're looking for (for 'get' or 'contains?') or an empty spot (for 'put'). The trick to make this fast is that the hash function (key -> int) tells you at which index to start the sweep.
No secondary data structures, super simple to implement, and it works great for small use cases.
This isn't great though if you need to find out if an element exists in the table, and you have the ability to remove elements from it. I suppose you could optimize the hash table after deletions, but that again would be slow.. ?
Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.
The expected or amortized complexity of the standard hash table operations (put, get, contains, remove) are all O(1) for linear probing (under the usual assumptions for the hash function and as long as the table does not get too full). Of course that doesn't shield a single operation from being O(n) in the worst case.
The standard hash table has buckets, though, not just a single array that is probed through in case there's no space for a value in the slot determined by the hash function?
Right, that's the beauty of this simple approach: there's only one array and it doubles as the storage for buckets. But yes, the table will have a maximum size after which you cannot add more entries. That is, in practice you would create a new hashtable with a larger capacity and rehash all the existing entries into the new, bigger table (in practice, you would do that even sooner than that, namely when a certain load factor is passed - see my previous comment where I alluded to the role of the load factor).
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
Let's say we have removed all elements from the hash. Then all following contains -calls will need to be O(n), if I understood correctly? They need to check every slot in the array to confirm inexistence, rather than just one bucket.
There are different ways on how to implement remove, but one way to do it is to overwrite the (key, value) pair to be removed with a special "tombstone" symbol that is different from null. Another way is to shift all elements with the same hash value as the one to be removed one index to the left, and null the final position.
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
ancientstraits · · focus · HN ↗
zahlman · · focus · HN ↗
kleiba2 · · focus · HN ↗
No secondary data structures, super simple to implement, and it works great for small use cases.
_flux · · focus · HN ↗
Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.
kleiba2 · · focus · HN ↗
_flux · · focus · HN ↗
kleiba2 · · focus · HN ↗
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
_flux · · focus · HN ↗
kleiba2 · · focus · HN ↗
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
zahlman · · focus · HN ↗
I suppose that would work, but I can't recall ever hearing of an implementation that actually does that.