Hacker News Reader

Comment by Tainnor | Hacker News Reader

No, the author didn't really understand how hash tables* work and what the big-O notation really means.

If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything by using them. That's where you have 0(n) performance.

But hash tables are probabilistic data structures, so we don't actually look at worst-case performance, but at the average case. It's important that for this analysis we need to make some assumptions about the hash function itself (e.g. what its collision probability is). Out of that, we can compute that hash table operations are on average constant.

* There are actually multiple ways to deal with collisions in hash table, let's focus on open hashing/seperate chaining for now.

View on HN

Even in the average case, hashtables can't really be constant. Simple proof: As elements are added, you either resize the table or you don't.[1]

Resize the table: a bigger table requires larger keys (to have a sufficient number of distinct ones), which require logarithmically more time to compute.

Don't resize the table: You have to stuff a logarithmic number of keys into each bucket and iterate over them.

Both increase time with input size.

Earlier discussion: https://news.ycombinator.com/item?id=9807739

[1] to clarify, I don’t mean resize on every addition. Just “you occasionally resize or you never do”.

How often do you resize your hash tables in your mental model? Maybe there's a better "resizing schedule" where you don't resize as often and the amortized time taken in the resizing is O(1) :)

What I’ve said is true even if you got the resizing for free.

Added a clarifying note. The point is, resizing is not the (only) problem.

Tangentially related question; what's best way to design a map/set that doesn't take O(n) time for resizing, considering memory locality?

Use an off-the-shelf database engine, sql or good enough nosql (like esent on windows).

Most file systems also have these properties, optimized for memory locality (because disk seeks were incredibly slow), and you can create files in a folder much faster than O(n).

If interested how they do it: https://en.wikipedia.org/wiki/B-tree

Yes, if you assume that your keys are going to be arbitrarily long inputs.

I think it's typical that in the analysis of algorithms we often make simplifying assumptions that we don't always spell out explicitly (and probably we should). The assumption here (which IMHO is often practically sensible) was that there is a certain fixed set of all possible keys, e.g. from a bounded set of integers. In that case, hash tables indeed have constant-time operations no matter how many elements you have.

I think it's a bit similar to saying that e.g. Gauss elimination is O(n^3). This is only true for fixed-size numbers, e.g. floats or bounded integer types, not for arbitrary integers - in fact, the Gauss algorithm is incredibly bad for true, arbitrary-precision arithmetic. Nevertheless, the algorithm is incredibly useful, because the fixed-size assumption is often warranted - the most notable exceptions are probably from the realm of cryptography.

>Yes, if you assume that your keys are going to be arbitrarily long inputs.

No, it only requires that they lengthen enough to be distinct for the keyspace size. The problem arises not from arbitrarily big keys but from the fact that, whatever your keys are, if want a longer output of the hash function, you have to do more computations on the keys.

Late follow-up: argh, I should really have been referring to values (the output of a hash function) rather than keys, because that determines where they go in memory block used for the hash table.

> If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything by using them. That's where you have 0(n) performance.

I don't gain anything from going outside because if you do a worst-case analysis I can get hit by lightning and die.

The worst case for a hashtable degenerating to a linked list can be often exploited to form a DOS attack. It is enough that user controls the keys inserted to the hashtable and the hash function is not cryptographically secure (typically they are not for performance reasons). That's why it is much wiser to use a binary tree for resolving collisions.

So in this case - the worst case analysis is useful.

Author here. Ah, that makes sense. I always took it for granted that such a scenario of everything hashing to the same bucket wouldn't happen, but I understand now that in such a scenario it would take linear time, which means that technically the _worst_ case is O(n).

However, I don't see that this influences the main point of the post. In practice, hash collisions are extremely rare, which means that the linked list inside the array slot is going to have few elements, and so we shouldn't be looking at the worst case time complexity of that linked list.

> If you do a worst-case analysis, hash tables just degenerate to a single linked list ... That's where you have 0(n) performance.

Even under a best-case analysis, hash table lookups are O(N) when using a single hash function. Assume you have a perfect hash function such that the N inputs are equally distributed among K output values (each of K gets (1/K)N values). Lookup will be O((1/K)N). O(CN) = O(N) for any constant C. (1/K) is constant, therefore lookups are O((1/K)N) = O(N).

> Out of that, we can compute that hash table operations are on average constant.

The only way you get constant time is if the number of collisions is bounded by some constant. That's not possible for arbitrary N when using a single hash function and constant K, as shown above.

Actual implementations try to improve performance by rebuilding the hash table as more items are inserted, using a new hash function with larger K. This can keep the linked list sizes bounded by some constant, which means O(1) lookups but at the cost of rebuild operations which are at least O(N). (Note: The optimal hash table is one in which K>=N with no collisions.)

This is the first time I've seen someone make this point (your first two paragraphs) besides me. One disagreement though:

>Actual implementations try to improve performance by rebuilding the hash table as more items are inserted, using a new hash function with larger K. This can keep the linked list sizes bounded by some constant, which means O(1) lookups but at the cost of rebuild operations which are at least O(N).

Even ignoring the rebuild operations, it's still not O(1), because if you use a different (evenly distributing) hash function with larger key size, you necessarily need more computations to compute K, and so lookup time increases.

> hash function with larger key size, you necessarily need more computations to compute K

You're right and I saw your other reply on this thread after I posted my reply. The time complexity is only O(1) if we ignore the cost of the hash function, which is really O(log N) because it needs to process at least log N bits. However, by that reasoning even an array lookup is O(log N) because an array lookup requires adding an offset to a base address and the addition function may require O(log N) operations to calculate.

According to some brief googling it appears that some (most?) sources avoid this problem by simply defining "elementary operations" to be O(1). A constant number of elementary options would also be O(1) by that definition. That is probably what is meant by those who say that a hash lookup is O(1).

But a (well-mixed) hash function must change to produce a larger output, requiring more elementary operations. That is, if you’re going to scramble the input, then you must do more operations to mix them as you increase the output size.

In contrast, the array does a single addition on a number that is larger, which seems different.

A simple hash function may be something like dividing by K and taking the remainder, which is probably considered an "elementary operation" by definition.

But in general, keys and the hash function could be anything. For example, if the keys are strings of length N, then it's O(N) for just calculating the hash. Or if the keys are bitmap images, the hash function could apply image recognition and use recognized features as hash values. So, textbooks and other sources probably just ignore the key size and hash function because they could be literally anything.

In order for it to be anything like an ideal hash function that evenly distributes the keys across buckets, it must be a "avalanche effect" hash function that mixes each byte with all the others. If you limit it to O(1) elementary operations, you can no longer have it operate that way, and are back to assuming significant collisions and iteration over them.

The hash functions used for hash tables are designed to be fast to compute and typically just involve a couple of operations. See, for example, this Stack Overflow answer about Python dict hash functions. https://stackoverflow.com/questions/8997894/what-hash-algori...

Yes, they fall short of being cryptographically secure hash functions, but the examples given in Python do force each byte to mix with all the other bytes. As long as you have to increase the size of the output (as the table gets bigger), you (eventually) have to increase the number of elementary operations in the hash function.

You also misunderstand hash tables.. they are not merely expected constant time, they are amortized constant time.

as far as I understand, the amortization factor comes in because you occasionally might have to grow your table of buckets, in the same way that arbitrary-size array lookup is not actually constant, but only amortised constant.

if we sidestep that issue for one moment, it's still true that you have worst case O(n) and average O(1), though.

> arbitrary-size array lookup is not actually constant, but only amortised constant.

Array lookup operations are constant time. You don't need to grow an array while reading from it. Append operations in a vector are O(n) but amortized constant time.

Hash tables work the same way - they have amortized constant time when inserting, but they should have constant time for reads when using a good hash function.

That said, technically we still classify hash table reads and writes as O(n). Big-O notation defines an upper bound on time, not the average time. And the upper bound on hash table reads and writes is O(n) if you have a terrible hash function (or carefully crafted inputs).

This is not useful knowledge though, because hash tables are usually fast in practice. If you're trying to figure out how something performs in practice (like the "isVowel" function in the blog post), the tool to reach for is a benchmark. Guess how a benchmark result will come out before you see the result, and over time you'll build an intuition for these things.

You're right about the lookup being constant and insertions not, I didn't think it through well enough before posting. :)

But I disagree about the O notation. The O notation is just a mathematical notation, it defines certain classes of functions. It can be used for many different things, worst-case complexity is one, but not the only one. It's perfectly possible (and quite common) to describe expected complexity (which is a mathematical function of the input size, too) with O notation.

People do look at expected complexity for probabilistic algorithms and data structures and they are useful. The idea that "O notation is not useful and you should perform benchmarks" should also be taken with a grain of salt, you don't always have time to perform benchmarks (and for good benchmarks, you also have to make some assumptions about the data, in particular when it comes to probabilistic data structures), while you can just read up on O notation for common algorithms (and do a quick in-your-head calculation for custom algorithms, e.g. three nested loops, then it's probably O(n^3), not always of course) and use that at least as a very useful first-order approximation.

But you're right that it's more complex: one of the best examples of this is that the simplex algorithm for linear optimisation is not known to be polynomial (in fact, I think for every possible variant of the algorithm that has so far been proposed, we know that it can degenerate to exponential time with bad inputs), but somehow that doesn't appear to be an issue in practice - it is my understanding that nobody fully understands why not. There are proven polynomial algorithms for linear optimisation, but they are more complicated and therefore less often used.

I think they have recently found polynomial simplex algorithms.

Or I think at least a randomised simplex that has expected polynomial runtime even on the worst case input.

This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.

I just searched for 'polynomial time simp lex algorithm' and found things like eg https://cstheory.stackexchange.com/questions/2373/complexity... which references https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc....

thanks, it seems to be quite complex though, as far as I understand it's still "only" an expected polynomial algorithm given some assumptions about the input, and not a truly worst-case polynomial algorithm - as opposed to e.g. the ellipsoid method which is actually worst-case polynomial.

As far as I understand it's runs in expected polynomial time regardless of input.

No assumptions on the input necessary.

The expectation is over the choice of random bits created while running the algorithm.

I agree its misleading. Another example is that despite being O(log n), B-trees or skip lists can be much faster than hash tables if your keys are naturally ordered (and queried in order) because of memory caching.

> It's perfectly possible (and quite common) to describe expected complexity (which is a mathematical function of the input size, too) with O notation.

Yep - its common in practice but sloppy. Technically its not big-O anymore if you're doing that. Its big-theta notation. (Same thing, just T(n) instead of O(n)).

https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...

Why is it sloppy? The question of whether you use O or Theta is just that the one gives an upper bound only, and the other one ensures a tight bound (usually many people write O, when they mean Theta, which is not wrong, but is also doesn't tell you as much; in the end, it's mostly clear what is intended though).

That doesn't mean that you can't use either notation to refer to a worst-case or an average-case (given a suitably defined probability distribution) performance. To say "expected complexity for hash table lookup is O(1)" is neither wrong, nor sloppy.

No, they are not amotrized constant time because there is some predefined sequence of inputs that makes them always work in linear time

Though you should be able to sidestep this by doing something like seeding your hash with your hashtable pointer. Then you'd also need control over the memory allocator to break the hashtable.

Nope. Big-O is a mathematical measure, not a practical measure. Mathematically speaking we don't care if malicious input difficult to construct. We care that its possible - which it is - so the upper bound on time is at least O(n).

If you think this isn't useful in practice, you're right! If you want to compare the actual speed of an algorithm, benchmark it. And once you've done enough of that, your intuition will guide you far better than big-O notation ever could.

Randomised algorithms add an interesting wrinkle.

Eg even the worst case input for a randomised QuickSort still has an expected runtime of O(n log n). (Where the expectation is averaged over the random choices, not over the input.)

> Eg even the worst case input for a randomised QuickSort still has an expected runtime of O(n log n).

This statement is imprecise. What is "worst case input" when speaking of "expected".

Mathematically, worst case doesn't mean a known worst case that works every time. As long as I have an input that the random algorithm has a chance of generating the worst case, it will be O(n^2).

From an adversarial standpoint: If I have information about the random algorithm and the seed, I can make exploit it.

So yes, even the randomized Quick Sort has worst case of O(n^2)

> From an adversarial standpoint: If I have information about the random algorithm and the seed, I can make exploit it.

Randomised QuickSort as an algorithm doesn't have any random seed. It just uses pure randomness. (Specific implementations might use a pseudo-RNG.)

> This statement is imprecise. What is "worst case input" when speaking of "expected".

Oh, just the opposite! Speaking of 'expected' tells you exactly what worst-case to look for.

What I mean is that 'worst case input' by itself is not a-priori well-defined for randomised algorithms. Because you could eg have an input that worsens the 75%-ile runtime but improves the 25%-ile runtime.

By specifying eg 'expected', you make clear that you are talking about the worst case for the expected runtime.

> So yes, even the randomized Quick Sort has worst case of O(n^2)

The worst case over both input and random choices is O(n^2). The worst case over input for the expected running time is O(n log n).

Even more, for any input, even the worst case input, randomised quicksort has O(n log n) running time with 'very high probability', ie for any epsilon there's a big enough m and a constant c, so that with probability at least 1-epsilon, the running time of the worst case input of size n > m is smaller than c * n log n.

---

There's a different, but equivalent, way to analyse randomised algorithms that might be easier to digest for you, because it completely avoids having to directly talk about randomness:

Take your favourite deterministic machine model, say a Turing machine or a random access machine, and in addition to the normal input tape, give it access to an extra immutable one-sided 'random' tape that's pre-filled with binary symbols (0 or 1).

Everything is deterministic in this model.

An analysis of the expected runtime for the worst case input means that the adversary gets to prepare the input tape, but for the rest of the analysis we are analysing all possible contents of the 'random tape'.

For each possibility, there is one specific deterministic run. Talking about the expected (worst-case input) runtime just means that we are averaging over all possible 'random' tapes.

If we talk about the 95%-ile instead, that means that we are ordering all the runtimes for the different possibilities for the 'random tape' and taking the runtime of the 95%-ile. Still, everything is deterministic.

When you want to run this algorithm in practice, you sample from the space of possible contents of the 'random tape'. But crucially, the standard assumption is that you sample after your adversary has selected their input.

That standard assumption is in line with Kerckhoffs's principle in cryptography that the adversary knows your system, but that you are able to pick secret random keys at will.

https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle

> seeding your hash with your hashtable pointer

This is not how worst-case complexity analysis works. Worst-case means worst-case, ie. the input is selected by an adversary with complete knowledge of your algorithm and initial memory; and there is no source of randomness other than the input itself.

And, yes, that's usually not applicable in practice. But worst-case complexity is a theoretical concept defined only on abstract machines (implicitly a Von Neumann-like machine here).

Instead, to do useful analysis on hash tables, you should use probability complexity analysis, which allows your algorithm access to a source of randomness the adversary doesn't have access to.

You can analysis the worst-case input, but still average over random choices your algorithm makes.

That gives you 'worst-case expected runtime'. That concept is useful for eg analysing QuickSort with randomised pivots.

You can also analysis worst-case input and eg 99.999%-ile on the random choices.

> but still average over random choices your algorithm makes

Worst-case complexity is usually defined on Turing Machines or Von Neumann machines. In these models, algorithms cannot make "random choices", they are deterministic.

If you want to use a different computation model, you have to explicitly define it.

If you have a probability distribution, it is however possible to calculate the running time for different types of inputs and multiply those by the probability of the input being of that type to get an expected runtime which can then be expressed via O-notation.

I think this is well established practice, since there are a lot of interesting algorithms and data structures that have been widely studied and are probabilistic.

The analysis of probabilistic algorithms usually differentiates between inputs and random choices you make when running the algorithm.

You can analyze the worst case on the input while at the same time doing probability theory on the random choices. And since you control the random choice, you can impose nearly any reasonable distribution you feel like. (You just have to 'pay' for the generation of the random bits. Economizing on the number of random bits involved is just as much an area of research as economizing on runtime or memory.)

Of course, you can also analyze randomly distributed inputs. But that's a different beast, because in practice you seldom have a good handle on those distributions.

Fair enough, I'm not intimately familiar with how randomised algorithms are most often analysed in a very formal sense (I never saw an explicit theory of it, even though I've seen multiple more "intuitive" analyses). My point was more that there is no reason why you shouldn't be able to describe an expected runtime via O notation, whether or not that's the right way to do it in practice.

> Of course, you can also analyze randomly distributed inputs. But that's a different beast, because in practice you seldom have a good handle on those distributions.

But isn't this how it works for a hash table? It was my understanding that the actual hash function is deterministic, so there are no random choices to make - the randomness comes from the inputs; on the other hand you do have some assumptions (maybe not strictly proven) about the collision frequency, which should allow you to get a handle on the input distribution, or am I wrong?

In simpler times, hash maps used to be deterministic.

But that lead to easy denial of service attacks. So many languages, like eg Python, patched their hashmaps to use randomized hashes.

See eg https://arstechnica.com/information-technology/2011/12/huge-... or https://lwn.net/Articles/474912/ or https://bugs.python.org/issue13703

Now that you mentioned it, I remember running into this.

We would compute hashes out of some objects to compare for equality and it turned out we sometimes had more collisions than expected (orders of magnitude more), but this wasn't really reproducible. That was when I found out that the hashing algorithm wasn't deterministic. (Of course, the underlying cause was that our hash code calculations were not good and we had to fix them.)

> If you want to use a different computation model, you have to explicitly define it.

Probabilistic Turing machine are sufficiently standard and well known. They (or the random-access machine equivalent) are basically the implied context whenever you talk about randomized algorithm.

See https://en.wikipedia.org/wiki/Probabilistic_Turing_machine and https://en.wikipedia.org/wiki/Randomized_algorithm#Computati...

Worst case performance for the best compression algorithms result in an output file that's a few thousand bytes bigger than the input. And yet we are using compression to have this conversation.

It depends on what implementation of hash tables you use.

Especially if you use a randomized implementation.

Which is why we had a bunch of programming languages used for web servers scrambling to replace their hash algorithms with one that has better default key collision behavior and generates different output on every run.

Without upgrading your server you have the potential for someone to run a DDOS attack against you.

It depends on what implementation of hash tables you use.

Reply on news.ycombinator.com