Java question What properties are desirable in a hashing fun

 Java question.  What properties are desirable in a hashing function? What alternative is there to linear probing to avoid collissions? Be prepared to show the results of inserting given entries into a hash table (you will be given the hash function) using linear probing. 

Solution

1)
Desirable properties of Hash Function:

Consider a hash function H
   – Performance: Easy to compute H(m)
   – One-way property: Given H(m) but not m, it’s computationally infeasible to find m
   – Weak collision resistance (free): Given H(m), it’s computationally infeasible to find m’ such that H(m’) = H(m).
   – Strong collision resistance (free): Computationally infeasible to find m1, m2 such that H(m1) = H(m2)

2)

A problem with the linear probe method is that it is possible for blocks of data to form when collisions are resolved. This is known as primary clustering.This means that any key that hashes into the cluster will require several attempts to resolve the collision.

So to resolve this problem, DOUBLE HASHING is the alternative of Linear Probing.
Double hashing uses the idea of applying a second hash function to the key when a collision occurs. The result of the second hash function will be the number of positions form the point of collision to insert.

There are a couple of requirements for the second function:
   it must never evaluate to 0
   must make sure that all cells can be probed