4 ms·
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
by 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 agoIn 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 agoThe 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 agoYes, 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.