List the properties which a hashing function should possess to ensure a good search performance. What approaches are adopted to handle collision?

A hashing function h should possess the following properties to ensure good search performance:

  1. The hashing function should not be sensitive to the symbols used in some source program. That is it should perform equally well for different source programs. 
  2. The hashing function h should execute reasonably fast.
The following approaches are adopted to handle collision are:


One simple scheme is to chain all collisions in lists attached to the appropriate slot. This allows an unlimited number of collisions to be handled and doesn't require a priori knowledge of how many elements are contained in the collection. The tradeoff is the same as with linked lists versus array implementations of collections: linked list overhead in space and, to a lesser extent, in time. 


Re-hashing schemes use a second hashing operation when there is a collision. If there is a further collision, we re-hash until an empty "slot" in the table is found. The re-hashing function can either be a new function or a re-application of the original one. As long as the functions are applied to a key in the same order, then a sought key can always be located.

Overflow chaining:  

Another scheme will divide the pre-allocated table into two sections: the primary area to which keys are mapped and an area for collisions, normally termed the overflow area. When a collision occurs, a slot in the overflow area is used for the new element and a link from the primary slot established as in a chained system. This is essentially the same as chaining, except that the overflow area is pre-allocated and thus possibly faster to access. As with re-hashing, the maximum number of elements must be known in advance, but in this case, two parameters must be estimated: the optimum size of the primary and overflow areas. 
Overflow chaining


Feel free to contact the admin for any suggestions and help.