why not just use a random number generator as a hash function?

Problem Detail: 

I guess at the heart of this is that I don't really understand hash functions.

One article says any function mapping objects to an object of fixed size:

A hash function usually means a function that compresses, meaning the output is shorter than the input. Often, such a function takes an input of arbitrary or almost arbitrary length to one whose length is a fixed number, like 160 bits.

Why not just use a random number generator to generate the hash keys? Wikipedia suggests SHA1 which maps to $2^{160}\approx 10^{48}$ possible outputs has never experienced a "collision".

I was trying to understand why the hash is necessary in a probabilistic counting algorithm:

class LinearCounter():     def __init__(self, m, h):         self.array =  [False for x in range(m)]         self.hash = h      def add(value):         self.array(self.hash[ value ]) = True 

Is the hash necessary? Why can't we use a random number generator right away?

def add(value):     self.array(int(m*random.random())) 

Asked By : john mangual

Answered By : Patrick87

If I understand the question correctly, the answer is simple: if Hash(object) returns 27 when you call it this afternoon, we want Hash(object) to return 27 if we call it next week, on a different computer. If you use a random number generator in such a way that this is guaranteed, then go for it. Consider that a key use case for hash functions is implementing hash tables, and we want to be able to access what we put into a hash table tomorrow with the key we used today.

In your example, you might want to add a contains(value) method; using the hash, this would be as easy as checking self.hash[value] =? value. Otherwise, you'd need to iterate through the entire array to see if some position contains value.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14601