PPT: Hashing | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


H a s h i n g
Page 2


H a s h i n g
Introduction
Hashing is a powerful technique that maps data to fixed-size 
indices using a hash function. This enables fast data 
operations with O(1) average time complexity.
Hashing uses a hash function to map data to fixed-size indices 
in a hash table. This enables fast data operations with O(1) 
average time complexity.
Hashing is widely used in databases, caching, symbol tables, 
and password storage due to its efficient O(1) average time 
complexity.
Page 3


H a s h i n g
Introduction
Hashing is a powerful technique that maps data to fixed-size 
indices using a hash function. This enables fast data 
operations with O(1) average time complexity.
Hashing uses a hash function to map data to fixed-size indices 
in a hash table. This enables fast data operations with O(1) 
average time complexity.
Hashing is widely used in databases, caching, symbol tables, 
and password storage due to its efficient O(1) average time 
complexity.
Hash Table
Structure
An array of size m (table 
size) where each slot 
stores a key-value pair or a 
linked list for handling 
collisions.
Insert
Add a key-value pair to the 
table by computing the 
hash and placing the data 
at the corresponding 
index.
Search
Retrieve a value for a given 
key by computing its hash 
and accessing the 
corresponding table 
position.
Delete
Remove a key-value pair 
from the table by finding 
its position and marking it 
as deleted or removing it.
With a good hash function, hash tables provide average-case O(1) time complexity for insert, search, and delete 
operations. In the worst case, these operations may degrade to O(n) if many collisions occur. For example, with a 
table size of 10, inserting key 23 would place it at index h(23) = 23 mod 10 = 3.
Page 4


H a s h i n g
Introduction
Hashing is a powerful technique that maps data to fixed-size 
indices using a hash function. This enables fast data 
operations with O(1) average time complexity.
Hashing uses a hash function to map data to fixed-size indices 
in a hash table. This enables fast data operations with O(1) 
average time complexity.
Hashing is widely used in databases, caching, symbol tables, 
and password storage due to its efficient O(1) average time 
complexity.
Hash Table
Structure
An array of size m (table 
size) where each slot 
stores a key-value pair or a 
linked list for handling 
collisions.
Insert
Add a key-value pair to the 
table by computing the 
hash and placing the data 
at the corresponding 
index.
Search
Retrieve a value for a given 
key by computing its hash 
and accessing the 
corresponding table 
position.
Delete
Remove a key-value pair 
from the table by finding 
its position and marking it 
as deleted or removing it.
With a good hash function, hash tables provide average-case O(1) time complexity for insert, search, and delete 
operations. In the worst case, these operations may degrade to O(n) if many collisions occur. For example, with a 
table size of 10, inserting key 23 would place it at index h(23) = 23 mod 10 = 3.
Collisions in Hashing
Definition
Collisions occur when two or more distinct keys map to 
the same index in the hash table. For example, both 23 
and 33 hash to index 3 when using h(k) = k mod 10.
These collisions are inevitable due to the pigeonhole 
principle 3 when mapping a larger set of possible keys 
to a smaller set of indices, some keys must share the 
same index.
Resolution Techniques
Separate Chaining: Store multiple keys in a linked list 
at the same index, allowing unlimited entries per slot.
Open Addressing: Find alternative slots in the table 
using probing sequences when a collision occurs.
The impact of collisions can significantly degrade hash table performance if not handled properly. The key goal in 
hash table design is to minimize collisions through good hash function selection and implement efficient 
resolution techniques.
Page 5


H a s h i n g
Introduction
Hashing is a powerful technique that maps data to fixed-size 
indices using a hash function. This enables fast data 
operations with O(1) average time complexity.
Hashing uses a hash function to map data to fixed-size indices 
in a hash table. This enables fast data operations with O(1) 
average time complexity.
Hashing is widely used in databases, caching, symbol tables, 
and password storage due to its efficient O(1) average time 
complexity.
Hash Table
Structure
An array of size m (table 
size) where each slot 
stores a key-value pair or a 
linked list for handling 
collisions.
Insert
Add a key-value pair to the 
table by computing the 
hash and placing the data 
at the corresponding 
index.
Search
Retrieve a value for a given 
key by computing its hash 
and accessing the 
corresponding table 
position.
Delete
Remove a key-value pair 
from the table by finding 
its position and marking it 
as deleted or removing it.
With a good hash function, hash tables provide average-case O(1) time complexity for insert, search, and delete 
operations. In the worst case, these operations may degrade to O(n) if many collisions occur. For example, with a 
table size of 10, inserting key 23 would place it at index h(23) = 23 mod 10 = 3.
Collisions in Hashing
Definition
Collisions occur when two or more distinct keys map to 
the same index in the hash table. For example, both 23 
and 33 hash to index 3 when using h(k) = k mod 10.
These collisions are inevitable due to the pigeonhole 
principle 3 when mapping a larger set of possible keys 
to a smaller set of indices, some keys must share the 
same index.
Resolution Techniques
Separate Chaining: Store multiple keys in a linked list 
at the same index, allowing unlimited entries per slot.
Open Addressing: Find alternative slots in the table 
using probing sequences when a collision occurs.
The impact of collisions can significantly degrade hash table performance if not handled properly. The key goal in 
hash table design is to minimize collisions through good hash function selection and implement efficient 
resolution techniques.
Separate Chaining
Implementation
Each slot in the hash table contains a linked list that stores all keys hashing to that index. This approach allows multiple keys 
to coexist at the same index position.
Operations
When inserting, the key-value pair is appended to the linked list at h(key). Searching requires traversing the linked list at 
h(key) to find the target key. Deletion involves removing the key from its linked list.
Example
With table size = 5 and h(k) = k mod 5, inserting 10, 15, and 20 would place all three in a linked list at index 0 (10³15³20), as 
they all hash to the same value.
Separate chaining offers advantages like simple implementation and no limit on collisions, but requires extra memory for linked 
lists and suffers from poor cache performance due to pointer chasing.