Hashing : Hashing provides the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing function H which map the key with the corresponding key address or location. It provides the key-to-address transformation.
No a perfect hash function cannot be made because hashing is not perfect.
Occasionally, a collision occurs when two different keys hash into the same hash value and are assigned to the same array element. Programmers have come up with various techniques for dealing with this conflict.Two broad classes of collision resolution techniques are: open addressing and chaining.
Open addressing: The simplest way to resolve a collision is to start with the hash address and do a sequential search through the table for an empty location. The idea is to place the record in the next available position in the array. This method is called linear probing. An empty record is indicated by a special value called null. The major drawback of the linear probe method is clustering.
Chaining: In this technique, instead of hashing function value as location we use it as an index into an array of pointers. Each pointer access a chain that holds the element having same location.
Because two entries cannot be assigned the same array element, the programmer creates a linked list. The first user-defined structure is assigned to the pointer in the array element. The second isn’t assigned to any array element and is instead linked to the first user-defined structure, thereby forming a linked list.
For example: in a table size of 7
42, 56 both are mapped to index 0 as 42%7=0 and 56%7=0.
25, 42, 96, 101, 102, 162, 197 can be mapped as follows:
