4 ms·

> 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

> 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...
      - SilasX 6y ago
        Yes, they fall short of being cryptographically secure hash functions, but the examples given in Python do force each byte to mix with all the other bytes. As long as you have to increase the size of the output (as the table gets bigger), you (eventually) have to increase the number of elementary operations in the hash function.

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...
    - SilasX 6y ago
      Yes, they fall short of being cryptographically secure hash functions, but the examples given in Python do force each byte to mix with all the other bytes. As long as you have to increase the size of the output (as the table gets bigger), you (eventually) have to increase the number of elementary operations in the hash function.