3 ms·

That is not what we are measuring. We don't care about the cost of the comparison itself, as long as it stays the same for every element for a chosen key size,

That is not what we are measuring. We don't care about the cost of the comparison itself, as long as it stays the same for every element for a chosen key size, but the number of comparisons performed. A hash algorithm, that has a constant number of chains, will always perform a constant number of comparisons, regardless of the key size. Article makes a different mistake, OP doesn't understand big-O notation and takes his conclusion on a real world example, instead of it being theoretical.

mindslight 11y ago
Sure, the entire goal of a hash construction is to carve out a constant time in a limited context. But the general problem is lower-bounded by (log n), and nothing can change that. The hash appears O(1) because it incorporates large fixed constants, and the working set size never "outruns" that head start. It's not surprising that the complexity of the general problem could leak through, since various best-case optimizations (eg caching) can erase the head start that was supposed to hide the growth.
- 36erhefg 11y ago
  Actually in the theoretical world, the cost is always O(1) because the hash function computation always takes constant time. You are restricting yourself to a machine model with bits, which is not assumed by big-O notation.
  - SilasX 11y ago
    But it doesn't even work in that theoretical world: as n gets arbitrarily large, you've used up all the keys and they have to start sharing buckets, forcing you to iterate over O(n) of them -- although the constant on that is only logarithmic in the size of the hash function output space (aka linear in the size of hash output)! Edit: clarify and fix error.
    - mcphage 11y ago
      Generally you move to a larger hash table long before you get that much key collision. Which is a big cost once, but the amortized cost doesn't change much. But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size. In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm.
      - SilasX 11y ago
        >Generally you move to a larger hash table long before you get that much key collision. Which is a big cost once, but the amortized cost doesn't change much. No, it's a big cost every time you pass a threshold, which happens an infinite number of times, because big-O assumes numbers can be arbitrarily large. >But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size. As long as the max number size is orthogonal to the number of elements n, you can assume a bound on the time for an addition operation, and then it becomes a constant in your run-time expression with respect to n. No sleight-of-hand there. >In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm. All true, but the spec for big-O doesn't say "assume away stuff that doesn't matter in practice". It says, "as n gets arbitrarily large". When you make inconsistent, varying assumptions between problems, you're not doing STEM anymore; you're doing memorization, the kind of thing STEM isn't supposed to be like. If "the" definition of big-O consistently included a definition that "we never have to deal with more than 2^64 elements", that would be fine. Instead, we have to memorize "the right answers" for when you can and can't assume that, and only then does O(1) for hash lookup pop out. And if you really just care about in-practice, then you can no safely assume that a typical balanced binary tree lookup takes fewer ops than e.g. SHA256.

mindslight 11y ago

Sure, the entire goal of a hash construction is to carve out a constant time in a limited context. But the general problem is lower-bounded by (log n), and nothing can change that. The hash appears O(1) because it incorporates large fixed constants, and the working set size never "outruns" that head start. It's not surprising that the complexity of the general problem could leak through, since various best-case optimizations (eg caching) can erase the head start that was supposed to hide the growth.

36erhefg 11y ago
Actually in the theoretical world, the cost is always O(1) because the hash function computation always takes constant time. You are restricting yourself to a machine model with bits, which is not assumed by big-O notation.
- SilasX 11y ago
  But it doesn't even work in that theoretical world: as n gets arbitrarily large, you've used up all the keys and they have to start sharing buckets, forcing you to iterate over O(n) of them -- although the constant on that is only logarithmic in the size of the hash function output space (aka linear in the size of hash output)! Edit: clarify and fix error.
  - mcphage 11y ago
    Generally you move to a larger hash table long before you get that much key collision. Which is a big cost once, but the amortized cost doesn't change much. But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size. In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm.
    - SilasX 11y ago
      >Generally you move to a larger hash table long before you get that much key collision. Which is a big cost once, but the amortized cost doesn't change much. No, it's a big cost every time you pass a threshold, which happens an infinite number of times, because big-O assumes numbers can be arbitrarily large. >But in general with these discussions, you assume that certain operations are constant on your "machine". For instance, addition is usually considered constant even though it isn't if your numbers are larger than your machine's word size. As long as the max number size is orthogonal to the number of elements n, you can assume a bound on the time for an addition operation, and then it becomes a constant in your run-time expression with respect to n. No sleight-of-hand there. >In the case of the hash tables, you assume your hash is constant, even if, as you note, it isn't really. But the fact is, the coefficient for the O(log N) term is so small, that it doesn't really offer any useful insight towards the performance of the algorithm. All true, but the spec for big-O doesn't say "assume away stuff that doesn't matter in practice". It says, "as n gets arbitrarily large". When you make inconsistent, varying assumptions between problems, you're not doing STEM anymore; you're doing memorization, the kind of thing STEM isn't supposed to be like. If "the" definition of big-O consistently included a definition that "we never have to deal with more than 2^64 elements", that would be fine. Instead, we have to memorize "the right answers" for when you can and can't assume that, and only then does O(1) for hash lookup pop out. And if you really just care about in-practice, then you can no safely assume that a typical balanced binary tree lookup takes fewer ops than e.g. SHA256.