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 must possess the subsequent properties to make sure good search performance:

1. The hashing function must not be sensitive to the symbols utilized in some source program. That is it must perform uniformly well for various source programs.

2. The hashing function h must execute reasonably fast.

The subsequent approaches are adopted to handle collision are: 

Chaining: One easy scheme is to chain all collisions in lists attached to the suitable slot. This allows an unlimited no. of collisions to be handled and doesn't need a priori knowledge of how many components are contained in the collection. The tradeoff is similar as with linked lists versus array implementations of collections: linked list overhead into space and to a lesser extent, in instance.

Rehashing: It schemes utilizes a second hashing operation while there is a collision. If there is a further collision, we re-hash till an empty "slot" in the table is determined. The re-hashing function may either be an original function or a re-application of the new one. As long as the functions are applied to a key in similar order, then a sought key can all the time be located.

h(j) = h(k), so the subsequent hash function, h1 is used, a second collision is arise, so h2 is used

Overflow chaining: The other scheme will divide the pre-allocated table in two sections: the primary area  to that keys  are mapped  and  an  area  for  collisions, usually termed the overflow area. While a collision happens, a slot in the overflow area is utilized for the new component and a link from the primary slot established as into a chained system. It is essentially similar as chaining, except the overflow area that is pre-allocated and therefore possibly faster to access. Along with re-hashing, the maximum number of components must be identified in advance, but in this case, two parameters should be estimated: the optimum size of overflow and the primary areas.