4 ms·

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

> 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).
  - SilasX 6y ago
    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.
    - bdowling 6y ago
      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.
      - SilasX 6y ago
        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.
        bdowling 6y ago
        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-algorithm-does-pythons-dictionary-mapping-use https://stackoverflow.com/questions/8997894/what-hash-algori...
        6y ago

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).
- SilasX 6y ago
  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.
  - bdowling 6y ago
    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.
    - SilasX 6y ago
      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.
      - bdowling 6y ago
        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-algorithm-does-pythons-dictionary-mapping-use https://stackoverflow.com/questions/8997894/what-hash-algori...
        6y ago