Hashing in Data Structure | Static Hashing | Collision Resolution Techniques | Separate Chaining | Linear Probing |Quadratic Probing| Double Hashing| Hashing in DBMS

 

Hashing in DBMS

Hashing is a technique used to map data elements (keys) to specific locations in a hash table using a hash function.

It allows insertion and retrieval of data efficiently
  

Hash Function

A hash function converts a key into a hash code (index), which is used to store and retrieve the data from a hash table.

                               h(k)=k mod m

Where:

  • k → Key
  • m → Hash table size
  • h(k) → Hash index 

Hash Table
  • A hash table is a data structure that stores data in an array format.
  • Each position in the table is called a bucket, and the position is accessed using the hash function.

Example

Consider

  • Keys                   (k) = 11, 18, 20, 25, 29, 33
  • Hash table size (m) = 7
Hash function:   h(k)=k mod m
                           h(k)=k mod 7

Key

Hash Calculation

Index

11

11 mod 7

4

18

18 mod 7

4

20

20 mod 7

6

25

25 mod 7

4

29

29 mod 7

1

33

33 mod 7

5

Here, 18 and 25 also map to index 4, creating a collision.



Types of Hashing
Hashing is mainly classified into:

  1. Static Hashing
  2. Dynamic Hashing


Static Hashing:
                       Static hashing uses a fixed-size hash table.

Characteristics

  • The size of the hash table remains fixed.
  • The number of buckets does not change during execution.
  • The hash function remains constant.
  • As data increases, collisions and overflow may occur.
  • Collision resolution techniques are used to handle collisions. 

Collision Resolution Techniques in Static Hashing
The main techniques are:
  1. Separate Chaining
  2. Linear Probing (Open Addressing)
  3. Quadratic Probing (Open Addressing)
  4. Double Hashing (Open Addressing)


Separate Chaining
Separate chaining is a collision resolution technique that uses linked lists.

Working
  • Each hash table index stores a list of elements.
  • Keys that produce the same index are stored in the same linked list.
  • It avoids overflow in the table itself but requires additional memory.

Example

  • Keys                   (k) = 11, 18, 20, 25, 29, 33
  • Hash table size (m) = 7

Key

Hash Calculation

Index(mod remaining value)

11

11 mod 7

4

18

18 mod 7

4

20

20 mod 7

6

25

25 mod 7

4

29

29 mod 7

1

33

33 mod 7

5

For the keys 11, 18 and 25:
11 mod 7=4
18 mod 7=4
25 mod 7=4

Therefore, they are stored in the same chain(Linked List):
Index 4 → 11 → 18 → 25

Index

Values

0

—

1

29

2

—

3

—

4

11 → 18 → 25

5

33

6

20

 


Linear Probing
  • Linear probing is a collision resolution technique based on open addressing.
  • When a collision occurs, the next sequential position is checked until an empty position is found.

Formula
                    h(k,i)=(h(k)+i) mod m
                                                     where i = 0, 1, 2, ...

Key

Hash Calculation

Insert Position

11

11 mod 7 = 4

4

18
18 mod 7 = 4 → next 5
(Index 4 already occupied, so check  
Next empty  position)

5

20

20 mod 7 = 6

6

25

25 mod 7 = 4 → 5 → 6 → 0

0

29

29 mod 7 = 1

1

33

33 mod 7 = 5 → 6 → 0 → 1 → 2

2

 Final Hash Table

Index

Value

0

25

1

29

2

33

3

—

4

11

5

18

6

20



Quadratic Probing
  • Quadratic probing is an open-addressing collision resolution technique.
  • When a collision occurs, positions are checked using square increments.
Formula
                    h(k,i)=(h(k)+i2) mod m

Key

Hash Calculation

Insert Position

11

11 mod 7 = 4

4

18

18 mod 7 = 4 → 4 + 1² = 5

5

20

20 mod 7 = 6

6

25
25 mod 7 = 4 
→ 4 + 1² = 5
→ 4 + 2² = 8 mod 7 = 1

1

29

29 mod 7 = 1 

→ 1 + 1² = 2

2

33

33 mod 7 = 5 

→ 5+ 1² = 6
→ 5+ 2² = 11 mod 7=4
→ 5+ 3² = 14 mod 7=0

0

Final Hash Table

Index

Value

0

33

1

25

2

29

3

—

4

11

5

18

6

20



Double Hashing

  • Double hashing is an open-addressing collision resolution technique.
  • It uses two hash functions to determine the position of a key.

First Hash Function
                                        h1(k)=k mod 7

Second Hash Function
                                         h2(k)=1+(k mod 6)

Final Formula
                                  h(k,i)=(h1​(k)+i×h2​(k)) mod 7


Key

Hash Calculation

Insert Position

11

h₁ = 11 mod 7 = 4

4

18

h₁ = 18 mod 7 = 4;

h₂ = 1+(18 mod 6)=1;
(4+1×1) mod 7 = 5

5

20

h₁ = 20 mod 7 = 6

6

25

h₁ = 25 mod 7=4;

h₂ = 1+(25 mod 6)=2;
(4+1×2) mod 7 = 6 → full;
(4+2×2) mod 7 = 1

1

29

h₁ = 29 mod 7= 1;

h₂ = 1+(29 mod 6)= 6;
(1+1×6) mod 7 = 0

0

33

h₁ = 33 mod 7= 5;

 h₂ = 1+(33 mod 6)= 4;
(5+1×4) mod 7 = 2

2

Final Hash Table

Index

Value

0

29

1

25

2

33

3

—

4

11

5

18

6

20


Handwritten Notes- Download Complete Handwritten Notes PDF

Video Explanation- https://youtu.be/IX5jxVn_Qgk

Comments

Post a Comment

Popular posts from this blog

Queue ADT in Data structure | Enqueue and Dequeue operation

  Queue ADT A  Queue  is a linear data structure in which elements are inserted at one end and removed from the other end.( Insertion → Rear,  Deletion → Front )                                   ↓ FRONT                                 ↓ REAR A B C D E    A queue follows the FIFO (First In, First Out) principle. This means that the element inserted first is removed first. A  Queue can be implemented using: Array Linked List Basic  Queue  Operations: 1. Enqueue - used to insert  a new element into the queue. 2. Dequeue - used to remove an element from the queue. 3. Peek - used to view the first element without removing it. 4. isEmpty - checks whether the queue contains any elements. 5. isFull - checks whether the ...
Read more

Normalization in DBMS,(1NF,2NF,3NF,BCNF,4NF,5NF)

                      Normalization in DBMS Normalization divides a large table into smaller , logically related tables and connects them using appropriate keys. The main purpose of normalization is to reduce unnecessary duplication of data and prevent problems that may occur when data is inserted, updated, or deleted. 1. First Normal Form (1NF) A relation is said to be in First Normal Form (1NF) when every attribute contains a single, indivisible value . Conditions of   1 NF Each cell must contain only one value. Multiple values should not be stored in the same field. ·         Example Customer Items Purchased Gowsi Rice, Dal Tamil Soap ·   Here, the Items Purchased column contains more than one value for Gowsi . ·   Therefore, the table is not in 1 NF . Converting it into 1NF. ...
Read more

Entity-Relationship(ER) Model in DBMS

Image
Entity-Relationship(ER) Model The Entity-Relationship (ER) Model is a conceptual data model. It helps database designers understand the requirements of a system before creating the actual database tables . It describes the important objects in a system, their properties , and the relationships between them. The three basic concepts of the ER model are Entity Attribute Relationship Entity An entity can be any real-world object, person, place, or class about which we want to store information in a database. In a traditional ER diagram, an entity is represented by a rectangle .                        Example: Employee and Department An employee works for a department. Here, Employee and Department are entities , and Works For is the relationship between them. Weak Entity A weak entity is an entity that depends on another entity for its identification of existence. A weak entity is represented by a double rectangle ...
Read more