There are two strategies for minimizing the number of collisions. The first is simply to choose a hashing function that spreads the possible key values evenly across all the different positions in the hash table. A commonly used form of hashing function, when keys are integers (or easily converted to integers), is:
H(Key) = (P * Key) mod TABLE_SIZE
where P and TABLE_SIZE are different prime numbers. Unless the key values have some unusual properties - for instance, they are all multiples of TABLE_SIZE - a hashing function of this form will distribute them uniformly across all the different array positions.
In the above example, the table should have been of size 101 (a prime) not 100. If the table size is 100, and all the keys are even numbers, none of them will be mapped to an odd hash value.
The second strategy is simply to make the table larger, either by allowing several values to be stored in an array position (the `bucket' method), or by having more positions available. Doubling the size of the table will halve the expected number of collisions.
The latter strategy gives rise to an important property of hash tables that we have not seen in any other data structure. With a hash table, the efficiency of the operations is under our control to a significant extent. We directly control the size of the table, and thereby control the efficiency of our operations. We can easily make the expected number of collisions as small as we like: all we have to do is increase the table's size.
The load factor is defined to be the ratio:
When the load factor is small - i.e. when the table is relatively empty - the chance of a collision is small and the operations are `almost' constant time. When the load factor is high, the operations degrade to log-time, at least, and can even degrade to linear time (if collisions are are resolved in an unsophisticated way). The load factor is directly under our control (because we can choose the size of the table) and this gives us control over the efficiency of our algorithms.
