Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | Re Hashing Collision

Collision occurs when a hash value of a record being inserted hashes to an address that already contain a different record(i.e) when two key values hash to the same position.

**RE-HASHING Collision**:

Collision occurs when a
hash value of a record being inserted hashes to an address that already contain
a different record(i.e) when two key values hash to the same position.

**Collision Resolution**:

The process of finding
another position for the collide record is said to be collision resolution
stategy.

Two categories of
Hashing: ^{à}open Hashing

a) Separate Chaining.
-Linked list ^{à}Closed
Hashing

a)Open
addressing.

i) Linear
Probing. - H_{i}(X) = (HASH(X) +i)
% tablesize

ii) Quadratic
Probing - H_{i}(X) = (HASH(X) +i^{2}) % tablesize iii)Double
hashing. - H_{i}(X) = (HASH(X) +i* HASH_{2}(X) % tablesize

HASH_{2}(X)=R-(X % R) R is a prime number
that is smaller than the table size

If the table gets too
full,then the rehashing method builds new table that is a about twice as big
and scan down the entier original hashtable ,computing the new hash value for
each element and inserting it in the new table .

Rehashing is very
expensive operation, the running time is O(N),since there are N element to
rehashing and the table size roughly 2N.

Rehashing can be implemented in several ways with
quadratic probing such as:

^{à}Rehashing,as
soon as the table is half full;

^{à}Rehashing
only when an insertion fails.

^{à}Rehashing
when the table reaches a certain load factor

Eg:13,15,24,6 ,23are to
be inserted in hash table of size 7.

**The table will be 70% full.**

**A new table is created
as the table is so full. The new hash function is then h(X) =X mod 17**

**ADVANTAGE:**

Programmer does not
worry about the table size.

Simple to implement.

Can be used in other
data structures as well.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.