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

Question

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()))

Answer 1

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.

Answer 2

To expand Patrick87's comment and help you better understand the probabilistic counting algorithm : Linear Counting is used to get an approximate value of the number of distinct elements in a big set $S$ using a small amount of space.

Suppose that you have a set of 1000 of names and you want to know how many distinct names are present in it. In the worst case (all names are distinct) you should use an array of 1000 names. But if you only want an approximation, then you can use a hash function to map the names to a much shorter bitmask of $m$ bits.

Suppose that $d$ is the number of distinct names. $L = d/m$ is the load factor.

• If $L$ is low ($L < 1$) then few distinct names will be mapped (by the hash function) to the same bit, and the number of $1s$ in the final bitmask will be a good approximation of the "density" of distinct names in $S$;

• If $L$ is greater than 1 ($L > 1$), then certainly (pigeonhole principle) some distinct names will be mapped to the same bit; but nevertheless the number of $1s$ in the final bitmask can still be used to approximate the number of distinct elements in $S$;

• If $L$ is high ($L \gg 1$) then many distinct names will be mapped (by the hash function) to the same bit, and probably all bits of the mask will be set to 1; in this case you cannot recover the number of distinct items in $S$ from the bitmask (and you should increase $m$).

If you use a random function instead of the hash function, you'll always end with all bits set to 1 (like in the case $L \gg 1$), and you cannot use it to approximate the number of distinct elements.

Returning to our example, suppose that there are only 2 distinct names, and $m$ = 10.

Using a hash function, the 1000 names will set 2 bits in the mask (or less probably 1 bit if they collide) and the approximate number of distinct names is $-10 \ln (8 /10) = 2.23$

Using a random function, the 1000 names will set all 10 bits in the mask, and the formula cannot be even applied.