Resolving Collision
Hash collision is the process in which more than one key is mapped to the same memory location in the table. For example if we are using the division reminder hashing with following hash function
H (k) = k % 7
Then key = 8 and key = 15 both mapped to the same location of the table i.e. one
H (k) = 8 % 7 = 1 ß-
Hash collision
H (k) = 15 % 7 = 1 ß
The efficiency of a hash function with a collision resolution procedure is measured by the average number of probes (key comparisons) needed to find the location of the record with a given key k. the efficiency depends mainly on the load factor specifically we are interested in the following quantities.
S (r) = average number of probes for a successful search
U (r) = average number of probes for a unsuccessful search
Load factor ® is the ratio of the number n of key in k to the number m of hash address in L. this ratio R = n/m is called load factor.
Collision Resolution by Separate Chaining
In this method all the elements where keys hash to the same hash - table slot are put in a one inked list. Therefore the slot I in the hash table contains a pointer to the head of the linked list of all the elements that hash to value i. if there is no such elements that hash to value I the slot I contains NULL value.
Collision Resolution by open Addressing
In open addressing the keys to be hashed is to put in the separate location of the hash table. Each location contains some key or the some other character to indicate that the particular location is free.
In this method to insert key into the table we simply hash the key using the hash function. If the space is available then insert the key into the hash table location otherwise, search the location in the forward direction of the table to find the slot in a systematic manner. The process of finding the slot in the hash table is called probing.
Linear Probing
The linear probing uses the following hash function.
H (k,i) = [h' (k) + i] mod m for i = 0, 1, 2,........ M-1
Where m is the size of the hash table and h' (k) = k mod m the basic hash function and I is the probe number.
Quadratic Probing
The quadratic probing uses the following hash function.
H (k, i) = [h' (k) + C1 i + C2i2] mod m for i = 0, 1, 2 ....m-1
Where m is the size of hash table h' (k) = k mod m the basic hash function, c1 and c2 = 0 are auxiliary and is the probe number.
Double Hashing
In double hashing second hashing function H' is used for resolving a collision suppose a record R with key k has the hash addresses H (k) = h and H' (k) =h' = m.
Then we linearly search the location with addresses
If m is prime number then the above sequence will access all the locate ns the table T.
REHASHING
If at any stage the hash table become full or overflow then it will be very difficult to find the free slot and it will increase the execution time. In such a situation create a new hash table of size double then the original hash table. Then scan the previous hash table and for each key. Compute the new hash value and insert into the new hash table. Thereafter free the memory oceryned by the original hash table.
Data Structure & Algorithms Assignment Help, Live Experts
Struggling with data structure problems? Data structure subject is quite tough to learn? Need quick assistance in data structure questions? ExpertsMind.com is right place for you where your search ends, We at ExpertsMind offer online data structure assignment help, data structure homework help and data structure and algorithms question's answers by best online support by qualified tutors.
ExpertsMind.com - Resolving Hash Collision Assignment Help, Resolving Hash Collision Homework Help, Resolving Hash Collision Assignment Tutors, Resolving Hash Collision Solutions, Resolving Hash Collision Answers, Define Hashing Assignment Tutors