Hacker News Reader

Comment by recursive | Hacker News Reader

The first two myths aren't really myths.

In "The worst case is terrible", the author goes on to explain that the worst case is unlikely. That may be true, but it's still O(n).

In "Hash tables become full, and bad things happen", if I'm reading it correctly, the author shows how you can make each hash table bucket a linked list so that each bucket never becomes full. But what happens when you have 1000 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, at which time you need to re-hash every element in the table.

I'm a fan of hashtables, but there's some rather suspicious handwaving in this article.

View on HN

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.

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.

But the solution to that problem (using a cryptographic hash function randomized with a secret) doesn't change the complexity of the algorithm.

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?

The fundamental problem, especially wrt to 1 and 2, is that you're starting to deal more with the design and implementation of the hash table than anything else. There are two things that need to be considered for a good hash table implementation:

1. Collisions should be expected, and handled correctly.

2. The hashing algorithm should minimize collisions as much as possible.

Yes, the worst case running time is linear. However, assuming a properly defined hashing function, it's practically a linear running time over the expected number of collisions per bucket, which should be a tiny fraction of the total expected data size.

The problem that the second gives us is that proper hash algorithms are tailored to the specific problem at hand. MD5 is overkill when your entire pool of data is 1000 names. And knowing your data set makes it so you can avoid having a relatively large percentage of your data in one bucket.

Minor correction:

The worst case runtime is not O(n), it is defined by how you store your nodes in a hash bucket. If you choose to use a linked list, then searching a linked list is O(n). Also, obviously, there is no free lunch, so using a hash table in each bucket does not magically produce O(1) lookups.

Pick a data structure that has O(log n) runtime for lookups and use it when the hash table breaks down - that is, use it when searching in a bucket.

On the other hand, if your hash table has enough nodes in a bucket that you even notice the difference between O(very small n) and O(log very small n), you really should migrate to a larger hash table.

I;'m the author. It's not hand waving, it's an attempt to write a simple, approachable article -- I'm not trying to be Knuth.

If you want details, read the two articles that are linked into the text -- in those I delve into plenty of details, and include real-world experiments.

I thought it was a great article.

If things are being hashed evenly, and you have a 100 bucket table, putting 200, 300, etc. elements into the table isn't a terribly big deal, because it's just not slow to traverse a few nodes of a linked list. Of course, there's no reason not to make the table much bigger--it's just an array of pointers, make it 1,000,000 entries and you're still within a few megabytes.

Now, if someone wants to be a jerk, and figures out how to easy collide on your hash function, then you could have problems. He could stuff 1 million elements into the same hash table element, which will suck for linked-list traversal. So get a good hash algorithm :)

It's not just a "good" hash algorithm, it has to be one that cannot be made to behave in a way predictable to an attacker.

Picking a new secure random seed value at startup time and prepending it to every hashed value is generally what you need to do.

I am not going to buy a lottery ticket because the super unlikely best case is really good. For the same reason, I am not going to avoid a hash table because the super unlikely worst case is kind of bad.

You never have 1000 items in each bucket. You resize well before then.

I think at the point of having 1000 items in each bucket, a hashtable was never a good idea. I read it more as like, "Don't worry if you have collisions cos it'll be OK" as opposed to "Collisions have no impact on performance".

When you have 1000 items per bucket, you realize that you needed a bigger table. Depending on the implementation you're using, it may be able to expand the table without going "ok, hold everything, I have to rehash all this existing content". For instance, you can create a second hash table, start putting new additions in there. When you get an access, first check the new table, then the original one. If it's in the original table, return the value and move the k/v pair to the new table. Lots of papers have surely been written on this topic.

I ran experiments back in the day that varied the size of the hash table, and tried extremes where there were extremely long chains (high collisions). Take a look at pages 274 and 275, you'll be perhaps surprised how fast hash tables are when there are collisions -- especially if you use the move-to-front heuristic. (I agree with the other comments that the article is primarily concerned with the read use case.) http://www.mathcs.emory.edu/~whalen/Hash/Hash_Articles/In-me...

You could make each hash bucket a tree instead?

I'm the author of the article. I've tried that -- the downside is that the data structures (nodes in particular) take more space, and have more costs to manage / reorganize. Using a linked list with move-to-front-on-access works better in all experiments I've tried.

Reply on news.ycombinator.com