3 ms·

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 tab

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

by SilasX 6y ago

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

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.

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