4 ms·

Eli5?

laweijfmvo 2y ago
hash tables are most famous for their O(1) lookup time, but then you have to deal with collisions. There's many famous ways of dealing with collisions and you can convince yourself of their [worst case] lookup time. The article is discussing a new upper bound on that worst case.
- SilasX 2y ago
  This is always a point of frustration for me. Under the normal big-O model, hashtables aren't, and can't be O(1) lookup, even for the mythic perfect hash function! You can only get the O(1) figure by breaking the big-O model and bolting on some in-practice assumptions[1] that are used nowhere else in discussion of asymptotic complexity. Specifically, as you resize the table, you need a function with a bigger output space to give you more places to store the item. To have a bigger output space, you unavoidably have to do more computations. If you go from a function with n possible outputs to one with 2n possible outputs, as n goes to infinity, you eventually have to use a function with more steps. [1] elaborated on in this earlier discussion: https://news.ycombinator.com/item?id=9807739 https://news.ycombinator.com/item?id=9807739 Specifically this comment about the extra assumptions: https://news.ycombinator.com/item?id=9813524 https://news.ycombinator.com/item?id=9813524
  - Aunche 2y ago
    To be fair, in tree tables, we also assume that comparison is a constant time operation as well when it also necessarily needs to be O(log(n)) for an arbitrary sized table, making it an O(log(n)^2) data structure by this standard.
    - meribold 2y ago
      You don't need to compare the whole key most of the time. I think the amortized cost for a comparison is in O(1).
      - sltkr 2y ago
        Not in a balanced tree, since the further down the tree you go, the longer the shared prefix between the search key and node key becomes. So the complexity becomes something like 1 + 2 + 3 + .. + log n = O(log^2 n).
        meribold 2y ago
        Good point. Perhaps we could store the length of the common prefix from the last time we went left as well as from the last time we went right. The minimum of those two should remain a common prefix with the search key for the rest of the lookup and should therefore be safe to skip during subsequent comparisons.
        SilasX 2y ago
        But that would actually help it because you can store how far down the match is by that point in the tree, and know how few digits you have to actually compare.
  - magicalhippo 2y ago
    Your sense of frustration seems to stem from thinking about something which is similar to big-O, but not actually being big-O. All of the points you raise are valid if you want to have a good understanding of actual runtime cost of an algorithm. None of it is relevant if you want to compare algorithms according to big-O, in order to find one which doesn't lead to failure[1] when faced with large amounts of data. Perhaps you should define your own big-R notation for what you're after. [1]: https://arstechnica.com/information-technology/2013/12/exponential-algorithm-making-windows-xp-miserable-could-be-fixed/ https://arstechnica.com/information-technology/2013/12/expon...
    - SilasX 2y ago
      What are you taking about? By the actual standards of big-O that allow you to derive the constant run time? See the second linked comment which establishes that it only becomes constant when you add in practical hardware considerations. No bounded run time function can have an infinite output space (while still halting, anyway).
      - magicalhippo 2y ago
        What you are saying in that post is that a hashmap should be O(log(n)) because if you have a word size w you need k_w = log(n)/w operations to compute the hash of a key that's large enough to not have collisions. However by that logic the comparison function should also have a similar factor, since by the same argument the key values need to be large enough not to collide. Ie if the key values are just the natural numbers up to n for example, you'll need k_w words to store them and hence comparison takes O(k_w) = O(log(n)). Thus a binary tree should also have an additional log(n) factor due to this, and hence be O(log(n)^2)). However the point of big O is to compare, and since both have this log(n) factor you could just cancel that in both, leaving you with the familiar O(1) and O(log(n)) respectively for the hashmap and binary tree. Is it sloppy to do that prematurely? Kinda yes, but it makes comparisons much easier as you don't have to go cancelling those log(n) factors all the time. And the point of big O is to compare the algorithms, not accurate running time.
        2y ago
- anothernewdude 2y ago
  O(1) lookup is bullshit that ignores the memory hierarchy.
tejohnso 2y ago
If you're trying to find an available cubby hole for your boots, you'll find one very quickly if they're almost all empty. But if they're almost all full, it will take longer for you find one. This discovery shows that it won't take as long as previously thought.

Eli5?

hash tables are most famous for their O(1) lookup time, but then you have to deal with collisions. There's many famous ways of dealing with collisions and you can convince yourself of their [worst case] lookup time. The article is discussing a new upper bound on that worst case.

SilasX 2y ago
This is always a point of frustration for me. Under the normal big-O model, hashtables aren't, and can't be O(1) lookup, even for the mythic perfect hash function! You can only get the O(1) figure by breaking the big-O model and bolting on some in-practice assumptions[1] that are used nowhere else in discussion of asymptotic complexity. Specifically, as you resize the table, you need a function with a bigger output space to give you more places to store the item. To have a bigger output space, you unavoidably have to do more computations. If you go from a function with n possible outputs to one with 2n possible outputs, as n goes to infinity, you eventually have to use a function with more steps. [1] elaborated on in this earlier discussion: https://news.ycombinator.com/item?id=9807739 https://news.ycombinator.com/item?id=9807739 Specifically this comment about the extra assumptions: https://news.ycombinator.com/item?id=9813524 https://news.ycombinator.com/item?id=9813524
- Aunche 2y ago
  To be fair, in tree tables, we also assume that comparison is a constant time operation as well when it also necessarily needs to be O(log(n)) for an arbitrary sized table, making it an O(log(n)^2) data structure by this standard.
  - meribold 2y ago
    You don't need to compare the whole key most of the time. I think the amortized cost for a comparison is in O(1).
    - sltkr 2y ago
      Not in a balanced tree, since the further down the tree you go, the longer the shared prefix between the search key and node key becomes. So the complexity becomes something like 1 + 2 + 3 + .. + log n = O(log^2 n).
      - meribold 2y ago
        Good point. Perhaps we could store the length of the common prefix from the last time we went left as well as from the last time we went right. The minimum of those two should remain a common prefix with the search key for the rest of the lookup and should therefore be safe to skip during subsequent comparisons.
      - SilasX 2y ago
        But that would actually help it because you can store how far down the match is by that point in the tree, and know how few digits you have to actually compare.
- magicalhippo 2y ago
  Your sense of frustration seems to stem from thinking about something which is similar to big-O, but not actually being big-O. All of the points you raise are valid if you want to have a good understanding of actual runtime cost of an algorithm. None of it is relevant if you want to compare algorithms according to big-O, in order to find one which doesn't lead to failure[1] when faced with large amounts of data. Perhaps you should define your own big-R notation for what you're after. [1]: https://arstechnica.com/information-technology/2013/12/exponential-algorithm-making-windows-xp-miserable-could-be-fixed/ https://arstechnica.com/information-technology/2013/12/expon...
  - SilasX 2y ago
    What are you taking about? By the actual standards of big-O that allow you to derive the constant run time? See the second linked comment which establishes that it only becomes constant when you add in practical hardware considerations. No bounded run time function can have an infinite output space (while still halting, anyway).
    - magicalhippo 2y ago
      What you are saying in that post is that a hashmap should be O(log(n)) because if you have a word size w you need k_w = log(n)/w operations to compute the hash of a key that's large enough to not have collisions. However by that logic the comparison function should also have a similar factor, since by the same argument the key values need to be large enough not to collide. Ie if the key values are just the natural numbers up to n for example, you'll need k_w words to store them and hence comparison takes O(k_w) = O(log(n)). Thus a binary tree should also have an additional log(n) factor due to this, and hence be O(log(n)^2)). However the point of big O is to compare, and since both have this log(n) factor you could just cancel that in both, leaving you with the familiar O(1) and O(log(n)) respectively for the hashmap and binary tree. Is it sloppy to do that prematurely? Kinda yes, but it makes comparisons much easier as you don't have to go cancelling those log(n) factors all the time. And the point of big O is to compare the algorithms, not accurate running time.
      - 2y ago
anothernewdude 2y ago
O(1) lookup is bullshit that ignores the memory hierarchy.

tejohnso 2y ago

If you're trying to find an available cubby hole for your boots, you'll find one very quickly if they're almost all empty. But if they're almost all full, it will take longer for you find one. This discovery shows that it won't take as long as previously thought.