Hash tables

A hash table is a completely different kind of searchable structure. The idea starts from what is called a hash function. It is a function that gives an integer for any value of the desired type. For example, the hash function for strings must return an integer for every string. Java requires every class to have a hashcode() method. The object class has one method implemented by default, but we must override the default implementation whenever we override the equals method. The hash function holds the following properties:

• Same values must always return the same hash value. This is called consistency of the hash. In Java, this means if x and y are two objects and x.equals(y) is true, then x.hashcode() == y.hashcode().

• Different values may return the same hash, but it is preferred that they don't.

• The hash function is computable in constant time.

A perfect hash function will always provide a different hash value for different values. However, such a hash function cannot be computed...