3 ms·
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 m
by 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 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.