Fibonacci Hashing: An optimization that the world forgot (2018)
Multiplication is bad. Knuth actually also describes a hash function using random numbers and XOR. Its 10x faster than the modulo, and I belive Mikkel Thorup proved it optimal.The idea is roughly:Say you have a hashtable of size 1024. You then create x uint arrays of size size 256. These arrays you fill up with random numbers 0-1023.To get your hash value, you take your input and for i=0..x-1 determine byte k=input[i] you lookup the value in array[i][k].
These lookup values are then XORed giving a final random value between  0-1023 ready for inserting into the hash array.No modulos. No multiplications. You only have to redo the random tables when the size changes from say 1024 to 2048. Easy peacy. Superfast.