7 ms·

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 degen

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.

jmalicki 6y ago
You also misunderstand hash tables.. they are not merely expected constant time, they are amortized constant time.
- Tainnor 6y ago
  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.
  - josephg 6y ago
    > 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.
    - Tainnor 6y ago
      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.
      - eru 6y ago
        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.
        Tainnor 6y ago
        This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.
        6y ago
- nurumaik 6y ago
  No, they are not amotrized constant time because there is some predefined sequence of inputs that makes them always work in linear time
  - FeepingCreature 6y ago
    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.
    - josephg 6y ago
      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.
      - eru 6y ago
        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.)
        BeetleB 6y ago
        > 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)
- eru 6y ago
  It depends on what implementation of hash tables you use.
lxe 6y ago
> 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.
- pkolaczk 6y ago
  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.
adamzerner 6y ago
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.
SilasX 6y ago
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 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”.
- zests 6y ago
  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) :)
  - SilasX 6y ago
    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.
- higerordermap 6y ago
  Tangentially related question; what's best way to design a map/set that doesn't take O(n) time for resizing, considering memory locality?
  - Const-me 6y ago
    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 https://en.wikipedia.org/wiki/B-tree
- Tainnor 6y ago
bdowling 6y ago
> 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.)
- SilasX 6y ago
  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.
  - bdowling 6y ago
    > 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).

jmalicki 6y ago

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

Tainnor 6y ago
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.
- josephg 6y ago
  > 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.
  - Tainnor 6y ago
    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.
    - eru 6y ago
      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.
      - Tainnor 6y ago
        This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.
        6y ago
nurumaik 6y ago
No, they are not amotrized constant time because there is some predefined sequence of inputs that makes them always work in linear time
- FeepingCreature 6y ago
  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.
  - josephg 6y ago
    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.
    - eru 6y ago
      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.)
      - BeetleB 6y ago
        > 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)
eru 6y ago
It depends on what implementation of hash tables you use.

lxe 6y ago

> 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.

pkolaczk 6y ago
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.

adamzerner 6y ago

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.

SilasX 6y ago

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 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”.

zests 6y ago
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) :)
- SilasX 6y ago
  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.
higerordermap 6y ago
Tangentially related question; what's best way to design a map/set that doesn't take O(n) time for resizing, considering memory locality?
- Const-me 6y ago
  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 https://en.wikipedia.org/wiki/B-tree
Tainnor 6y ago

bdowling 6y ago

> 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.)

SilasX 6y ago
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.
- bdowling 6y ago
  > 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).