Scribd
Upload
96 views12 pages

Hashing Presentation

Hashing is a technique for converting key values into array indexes, facilitating efficient searching, insertion, and deletion. A hash table maps keys to values using hash functions, which must be deterministic and minimize collisions. Collision handling techniques, such as separate chaining and open addressing, are essential for maintaining performance in hash tables.

Uploaded by

Ayush Kavariya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
96 views12 pages

Hashing Presentation

Hashing is a technique for converting key values into array indexes, facilitating efficient searching, insertion, and deletion. A hash table maps keys to values using hash functions, which must be deterministic and minimize collisions. Collision handling techniques, such as separate chaining and open addressing, are essential for maintaining performance in hash tables.

Uploaded by

Ayush Kavariya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Hashing

Hash Tables, Functions,


and Overflow Handling

Presented By:

 Monika Kavariya
 Sharddha Sharma
 Shivani Lodhi
Introduction to Hashing

 Hashing is a technique to convert a range


of key values into a range of indexes of an
array.
 Efficient for searching, insertion, and
deletion.
 Commonly used in database indexing,
caches, and sets/maps in programming
languages.
What is a Hash Table!!
 A hash table is a data structure that maps keys
to values.
 Uses a hash function to compute an index into
an array.
 Key features:
 - Fast access
 - Efficient memory usage
 - Handles large datasets
Hash Function
 Converts keys into array indices.
 Good hash function properties:
 - Deterministic
 - Uniform distribution
 - Fast computation
 - Minimizes collisions
 Examples:
 - Division Method: h(k) = k mod m
 - Multiplication Method: h(k) = floor(m * (k * A mod 1))
Collision in Hashing

 Collision: When two keys hash to the same index.


 Collisions are inevitable due to pigeonhole principle.
 Collision handling is essential for hash table
performance.
Collision Handling Techniques

 Separate Chaining:
 - Each index stores a linked list of entries.
 - Simple and easy to implement.
 Open Addressing:
 - All elements stored in the hash table array.
 - Types:
 - Linear Probing
 - Quadratic Probing
 - Double Hashing
Separate Chaining

 Handles collisions by maintaining a list at each index.


 Pros:
 - Simple
 - Efficient if load factor is low
 Cons:
 - Extra memory for pointers
 - Degradation to linked list performance if overloaded
Open Addressing

 Linear Probing:
 - h(i) = (h(k) + i) mod m
 Quadratic Probing:
 - h(i) = (h(k) + c1*i + c2*i^2) mod m
 Double Hashing:
 - h(i) = (h1(k) + i * h2(k)) mod m
Performance Considerations

 Load Factor = number of elements / size of hash


table
 Affects performance significantly
 Rehashing: creating a bigger hash table and re-
inserting elements
Applications of Hashing

 Implementing dictionaries/maps
 Caches (e.g., LRU Cache)
 Database indexing
 Cryptographic functions
Summary

 Hashing provides efficient data storage and


retrieval.
 Hash functions are critical to performance.
 Collision resolution techniques ensure robustness.
 Widely used in software systems.
Thank You!!

You might also like