are hash functions considered random? considering they are deterministic in their inputs and outputs. With randomised primality testing, you could use a true random number (based on e.g. nuclear decay) every time, and get the same correctness guarantees. With a hash table, you could never retrieve anything if you always used a true random number as a key every time.