Hashing is a technique used in data structures that efficiently stores and retrieves
data in a way that allows for quick access. It involves mapping data to a specific
index in a hash table using a hash function that enables fast retrieval of
information based on its key. This method is commonly used in databases, caching
systems, and various programming applications to optimize search and retrieval
operations. The great thing about hashing is, we can achieve all three operations
(search, insert and delete) in O(1) time on average.
Basic terminologies in hashing :
1. Hash Function: You provide your data items into the hash function.
2. Hash Code: The hash function crunches the data and give a unique hash code.
This hash code is typically integer value that can be used an index.
3. Hash Table: The hash code then points you to a specific location within the
hash table.
A hashing algorithm is used to convert an input (such as a string or integer) into a
fixed-size output (referred to as a hash code or hash value). ie,Hashing involves
applying a specific mathematical function to the input data, which produces a unique
hash key that is typically of fixed length, regardless of the size of the input. The
resulting hash key is essentially a digital fingerprint of the original data.
The data is then stored and retrieved using this hash value as an index in an array
or hash table. The hash function must be deterministic, which guarantees that it will
always yield the same result for a given input. Hashing is commonly used to create
a unique identifier for a piece of data, which can be used to quickly look up that
data in a large dataset. For example, a web browser may use hashing to store
website passwords securely. When a user enters their password, the browser
converts it into a hash value and compares it to the stored hash value to
authenticate the user.
Importance of Hashing
1. Easy retrieval of required information from large data sets in an efficient
manner.
2. The hash code produced by the hash function serves as the unique identifier
in the data set thus maintaining data integrity.
3. The data is stored in a structured manner as there is an index for every record
in the hash table. This ensures efficient storage and retrieval.
Limitations of Hashing
1. Many a time there leads to a situation of collision where two or more inputs
have the same hash value.
2. The performance of the hashing algorithm depends upon the quality of the
hash function. Sometimes, a not well-thought-of hash function may lead to
collisions thus reducing the efficiency of the algorithm.
Types of Hash Functions
The primary types of hash functions are:
1. Division Method.
2. Mid Square Method.
3. Folding Method.
1. Division Method
The easiest and quickest way to create a hash value is through division. The k-value
is divided by M in this hash function, and the result is used.
Formula:
h(K) = k mod M(where k = key value and M = the size of the hash table)
Advantages:
This method is effective for all values of M.
The division strategy only requires one operation, thus it is quite quick.
Disadvantages:
Since the hash table maps consecutive keys to successive hash values, this
could result in poor performance.
There are times when exercising extra caution while selecting M's value is
necessary.
[Link] Square Method
The following steps are required to calculate this hash method:
k*k, or square the value of k
Using the middle r digits, calculate the hash value.
Formula:
h(K) = h(k x k)
(where k = key value)
3. Folding Method
The process involves two steps:
except for the last component, which may have fewer digits than the other
parts, the key-value k should be divided into a predetermined number of
pieces, such as k1, k2, k3,..., kn, each having the same amount of digits.
Add each element individually. The hash value is calculated without taking
into account the final carry, if any.
Formula:
k = k1, k2, k3, k4, ….., kn
s = k1+ k2 + k3 + k4 +….+ kn
h(K)= s
(Where, s = addition of the parts of key k)
Advantages:
Creates a simple hash value by precisely splitting the key value into equal-
sized segments.
Without regard to distribution in a hash table.
Disadvantages:
When there are too many collisions, efficiency can occasionally suffer.
Example of Folding Method
k = 12345
k1 = 67; k2 = 89; k3 = 12Therefore,s = k1 + k2 + k3
s = 67 + 89 + 12
s = 168
Advantages:
This technique works well because most or all of the digits in the key value
affect the result. All of the necessary digits participate in a process that results
in the middle digits of the squared result.
The result is not dominated by the top or bottom digits of the initial key value.
Disadvantages:
The size of the key is one of the limitations of this system; if the key is large,
its square will contain twice as many digits.
Probability of collisions occurring repeatedly.
Collision Resolution
One of the main challenges in hashing is handling collisions, which occur when two
or more input values produce the same hash value. There are various techniques
used to resolve collisions, including:
1. Open hashing/separate chaining/closed addressing
In this technique, each hash table slot contains a linked list of all the values that
have the same hash value. This technique is simple and easy to implement, but it
can lead to poor performance when the linked lists become too long.
Advantages:
o Implementation is simple and easy
o We can add more keys to the table because the hash table has a lot of empty
places.
o Less sensitive than average to changing load factors
o Typically utilized when there is uncertainty on the number and frequency of
keys to be used in the hash table.
Disadvantages:
o Space is wasted
o The length of the chain lengthens the search period.
o Comparatively worse cache performance to closed hashing.
2. Closed hashing (Open addressing)
Open addressing: In this technique, when a collision occurs, the algorithm
searches for an empty slot in the hash table by probing successive slots until an
empty slot is found. This technique can be more efficient than chaining when the
load factor is low, but it can lead to clustering and poor performance when the
load factor is high.
1. Linear Probing
Linear probing includes inspecting the hash table sequentially from the very
beginning. If the site requested is already occupied, a different one is
searched. The distance between probes in linear probing is typically fixed
(often set to a value of 1).
2. Quadratic Probing
The distance between subsequent probes or entry slots is the only difference
between linear and quadratic probing. You must begin traversing until you find
an available hashed index slot for an entry record if the slot is already taken.
By adding each succeeding value of any arbitrary polynomial in the original
hashed index, the distance between slots is determined.
3. Double hashing: This is a variation of open addressing that uses a second
hash function to determine the next slot to probe when a collision occurs. This
technique can help to reduce clustering and improve performance.
The time between probes is determined by yet another hash function. Double
hashing is an optimized technique for decreasing clustering. The increments for the
probing sequence are computed using an extra hash function.
Formula
(first hash(key) + i * secondHash(key)) % size of the table
[Detailed examples are given in the class. Also refer ppt given in the class. ]