goes on to explain that the worst case is unlikely. That may be true, but it's still O(n).
It's not O(n), it's more like O(1 + max(0, n - m)) where n is the number of elements in the table and m is the number of buckets. The table can grow up to about n == m and it's still approximately O(1).
But what happens when you have 1000 items in each bucket?
Don't do that. Rather if you do that, then you don't get to complain that the performance of your data structure is that of the fallback strategy instead of a properly sized hashtable.
You should have begin executing your growth strategy back at about 0.5 items in each bucket.
If you keep adding elements and you want to keep reads fast, sooner or later you're going to have to add more buckets,
Sooner or later you're going to have to put more RAM in the machine too. But in the meantime, your trusty old hash-based data structure will give you reliable service.
at which time you need to re-hash every element in the table.
If latency is a concern this re-hashing can be done incrementally.
If the hashing of elements itself is expensive, you can store the resulting hash value for each element.
Note that there are three zero bits at the bottom of each 64-bit-aligned pointer value. You could use these to store three additional bits of the hash value, allowing you to grow your table by a factor of 8 without rehashing.
It's not O(n), it's more like O(1 + max(0, n - m)) where n is the number of elements in the table and m is the number of buckets. The table can grow up to about n == m and it's still approximately O(1).
Isn't that just the long way of saying "O(n)"? It's a worst-case bound.
I'm guilty of sometimes using big-O notation when discussing amortized average costs as well.
It seems nonsensical to discuss worst-case behavior of hash-based data structures since we can (and should) make it arbitrarily unlikely.
In other words, if O(n) is the limit as n goes to infinity then the probability of actually encountering worst-case beahvior on a hashtable operation is 0 (assuming a non-broken hash function). Near-worst case behavior becomes similarly improbable.
This is different than many algorithms like, say, classic quicksort which have worst-case behavior on values that naturally appear in practice.
It depends on the application of the hash table, but malicious agents could 'attack' code by purposefully creating collisions if the author isn't careful. An algorithm expected to run in O(1) that runs at O(n) could be catastrophic.
I'm just pointing out that the worst case time complexity is an issue that can't always be cast aside. Aren't cryptographic hash functions generally slower?
It's not O(n), it's more like O(1 + max(0, n - m)) where n is the number of elements in the table and m is the number of buckets. The table can grow up to about n == m and it's still approximately O(1).
But what happens when you have 1000 items in each bucket?
Don't do that. Rather if you do that, then you don't get to complain that the performance of your data structure is that of the fallback strategy instead of a properly sized hashtable.
You should have begin executing your growth strategy back at about 0.5 items in each bucket.
If you keep adding elements and you want to keep reads fast, sooner or later you're going to have to add more buckets,
Sooner or later you're going to have to put more RAM in the machine too. But in the meantime, your trusty old hash-based data structure will give you reliable service.
at which time you need to re-hash every element in the table.
If latency is a concern this re-hashing can be done incrementally.
If the hashing of elements itself is expensive, you can store the resulting hash value for each element.
Note that there are three zero bits at the bottom of each 64-bit-aligned pointer value. You could use these to store three additional bits of the hash value, allowing you to grow your table by a factor of 8 without rehashing.