What makes a good hash function?
Hash functions convert arbitrary strings or other data structures down to fixed size numbers. Hash functions are fundamentally a many to one mapping, meaning that hash equality doesn’t imply the underlying objects are equal, but hash inequality definitely means the underlying objects are different. Hash functions often go hand-in-hand with hash tables, which means we can immediately see that it’s not enough just to have this many-to-one relationship. We also would like to have a notion of spreading, such that the output of the hash function on an object has a near equal chance of landing anywhere in the hash table. As such, it’s easy to imagine some very bad hash functions on strings. How about we just take the individual bytes of a string and add them up as 32-bit numbers? That’s a hash function that’s going to be biased toward small numbers, which will result in an unbalanced hash table. There are other properties we might want from a hash function while we’ll talk about below, when
