Module III: Hashing

Hashing: Implementation of Dictionaries, Hash Function, Collisions in Hashing,

Separate Chaining, Open Addressing, Analysis of Search Operations Priority
Queues: Priority Queue ADT, Binary Heap Implementation and Applications of
Priority Queues.

Hashing:
Suppose we want to design a system for storing employee records with phone numbers
(as keys). And we want the following queries to be performed efficiently:
1. Insert a phone number and corresponding information.
2. Search a phone number and fetch the information.
3. Delete a phone number and related information.
We can think of using the following data structures to maintain
information about different phone numbers.
1. Array of phone numbers and records.
2. Linked List of phone numbers and records.
3. Balanced binary search tree with phone numbers as keys.
4. Direct Access Table.
For arrays and linked lists, we need to search in a linear fashion, which can be
costly in practice. If we use arrays and keep the data sorted, then a phone
number can be searched in O(Logn) time using Binary Search, but insert and
delete operations become costly as we have to maintain sorted order.

With balanced binary search tree, we get moderate search, insert and delete
times. All of these operations can be guaranteed to be in O(Logn) time.
Another solution that one can think of is to use a direct access table where we
make a big array and use phone numbers as index in the array. An entry in array
is NIL if phone number is not present, else the array entry stores pointer to
records corresponding to phone number. Time complexity wise this solution is
the best among all, we can do all operations in O(1) time. For example to insert
a phone number, we create a record with details of given phone number, use
phone number as index and store the pointer to the created record in table.
This solution has many practical limitations. First problem with this solution is
extra space required is huge. For example if phone number is n digits, we need
O(m * 10n) space for table where m is size of a pointer to record. Another
problem is an integer in a programming language may not store n digits.

Due to above limitations Direct Access Table cannot always be

used. Hashing is the solution that can be used in almost all such situations
and performs extremely well compared to above data structures like
Array, Linked List, and Balanced BST in practice. With hashing we get O
(1) search time on average (under reasonable assumptions) and O (n) in
worst case. Now let us understand what hashing is.
Hashing: Hashing is a popular technique for storing and retrieving data as fast
as possible. The main reason behind using hashing is that it gives optimal
results as it performs optimal searches.
Why to use Hashing?
If you observe carefully, in a balanced binary search tree, if we try to search ,
insert or delete any element then the time complexity for the same is O(logn).
Now there might be a situation when our applications want to do the same
operations in a faster way i.e. in a more optimized way and here hashing comes
into play. In hashing, all the above operations can be performed in O(1) i.e.
constant time. It is important to understand that the worst case time complexity
for hashing remains O(n) but the average case time complexity is O(1).
Now let us understand a few basic operations of hashing.
Basic Operations:
 Hash Table: This operation is used in order to create a new hash table.
 Delete: This operation is used in order to delete a particular key-value pair
from the hash table.
 Get: This operation is used in order to search a key inside the hash table and
return the value that is associated with that key.
 Put: This operation is used in order to insert a new key-value pair inside the
hash table.
 Delete Hash Table: This operation is used in order to delete the hash table

Hashing Components:

1) Hash Table: An array that stores pointers to records corresponding to a

given phone number. An entry in hash table is NIL if no existing phone number
has hash function value equal to the index for the entry. In simple terms, we
can say that hash table is a generalization of array. Hash table gives the
functionality in which a collection of data is stored in such a way that it is easy
to find those items later if required. This makes searching of an element very
efficient.
2) Hash Function: A function that converts a given big phone number to a
small practical integer value. The mapped integer value is used as an index in
hash table. So, in simple terms we can say that a hash function is used to
transform a given key into a specific slot index. Its main job is to map each and
every possible key into a unique slot index. If every key is mapped into a unique
slot index, then the hash function is known as a perfect hash function. It is very
difficult to create a perfect hash function but our job as a programmer is to
create such a hash function with the help of which the number of collisions are
as few as possible. Collision is discussed ahead.
A good hash function should have following properties:
1. Efficiently computable.
2. Should uniformly distribute the keys (Each table position equally likely for
each).
3. Should minimize collisions.
4. Should have a low load factor(number of items in table divided by size of the
table).
For example for phone numbers a bad hash function is to take first three digits.
A better function is consider last three digits. Please note that this may not be
the best hash function. There may be better ways.
3) Collision Handling: Since a hash function gets us a small number for a big
key, there is possibility that two keys result in same value. The situation where a
newly inserted key maps to an already occupied slot in hash table is called
collision and must be handled using some collision handling technique.
Following are the ways to handle collisions:
 Chaining: The idea is to make each cell of hash table point to a linked list of
records that have same hash function value. Chaining is simple, but requires
additional memory outside the table.
 Open Addressing: In open addressing, all elements are stored in the hash
table itself. Each table entry contains either a record or NIL. When searching
for an element, we examine the table slots one by one until the desired
element is found or it is clear that the element is not in the table.

Separate Chaining Collision Handling

Technique in Hashing

What is Collision?
Since a hash function gets us a small number for a key which is a big integer or
string, there is a possibility that two keys result in the same value. The situation
where a newly inserted key maps to an already occupied slot in the hash table is
called collision and must be handled using some collision handling technique.
What are the chances of collisions with the large table?

Collisions are very likely even if we have a big table to store keys. An important
observation is Birthday Paradox. With only 23 persons, the probability that two
people have the same birthday is 50%.

How to handle Collisions?

There are mainly two methods to handle collision:

 Separate Chaining
 Open Addressing
Separate Chaining:
The idea behind separate chaining is to implement the array as a linked list
called a chain. Separate chaining is one of the most popular and commonly used
techniques in order to handle collisions.
The linked list data structure is used to implement this technique. So what
happens is, when multiple elements are hashed into the same slot index, then
these elements are inserted into a singly-linked list which is known as a chain.
Here, all those elements that hash into the same slot index are inserted into a
linked list. Now, we can use a key K to search in the linked list by just linearly
traversing. If the intrinsic key for any entry is equal to K then it means that we
have found our entry. If we have reached the end of the linked list and yet we
haven’t found our entry then it means that the entry does not exist. Hence, the
conclusion is that in separate chaining, if two different elements have the same
hash value then we store both the elements in the same linked list one after the
other.
Example: Let us consider a simple hash function as “key mod 7” and a
sequence of keys as 50, 700, 76, 85, 92, 73, 101

Advantages:
 Simple to implement.
 Hash table never fills up, we can always add more elements to the chain.
 Less sensitive to the hash function or load factors.
 It is mostly used when it is unknown how many and how frequently keys may be
inserted or deleted.
Disadvantages:
 The cache performance of chaining is not good as keys are stored using a
linked list. Open addressing provides better cache performance as everything
is stored in the same table.
 Wastage of Space (Some Parts of the hash table are never used)
 If the chain becomes long, then search time can become O(n) in the worst
case
 Uses extra space for links.

Open Addressing:
Like separate chaining, open addressing is a method for handling collisions. In
Open Addressing, all elements are stored in the hash table itself. So at any
point, the size of the table must be greater than or equal to the total number of
keys (Note that we can increase table size by copying old data if needed). This
approach is also known as closed hashing. This entire procedure is based upon
probing. We will understand the types of probing ahead:
 Insert(k): Keep probing until an empty slot is found. Once an empty slot is
found, insert k.
 Search(k): Keep probing until the slot’s key doesn’t become equal to k or
an empty slot is reached.
 Delete(k): Delete operation is interesting. If we simply delete a key,
then the search may fail. So slots of deleted keys are marked specially as
“deleted”.
The insert can insert an item in a deleted slot, but the search doesn’t
stop at a deleted slot.
Different ways of Open Addressing:
1. Linear Probing:
In linear probing, the hash table is searched sequentially that starts from the
original location of the hash. If in case the location that we get is already
occupied, then we check for the next location.
The function used for rehashing is as follows: rehash(key) = (n+1)%table-size.
For example, The typical gap between two probes is 1 as seen in the example
below:
Let hash(x) be the slot index computed using a hash function and S be the table
size
If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S
…………………………………………..
…………………………………………..
Let us consider a simple hash function as “key mod 7” and a sequence of keys
as 50, 700, 76, 85, 92, 73, 101.
Challenges in Linear Probing:

 Primary Clustering: One of the problems with linear probing is Primary

clustering, many consecutive elements form groups and it starts taking time
to find a free slot or to search for an element.
 Secondary Clustering: Secondary clustering is less severe, two records only
have the same collision chain (Probe Sequence) if their initial position is the
same.
Example: Let us consider a simple hash function as “key mod 5” and a
sequence of keys that are to be inserted are 50, 70, 76, 93.
 Step1: First draw the empty hash table which will have a possible range of
hash values from 0 to 4 according to the hash function provided.

Hash table
 Step 2: Now insert all the keys in the hash table one by one. The first key is
50. It will map to slot number 0 because 50%5=0. So insert it into slot
number 0.

Insert key 50 in the hash table

 Step 3: The next key is 70. It will map to slot number 0 because 70%5=0 but
50 is already at slot number 0 so, search for the next empty slot and insert it.

Insert key 70 in the hash table

 Step 4: The next key is 76. It will map to slot number 1 because 76%5=1 but
70 is already at slot number 1 so, search for the next empty slot and insert it.
 Insert key 76 in the hash table

 Step 5: The next key is 93 It will map to slot number 3 because 93%5=3, So
insert it into slot number 3.

Insert key 93 in the hash table

2. Quadratic Probing
If you observe carefully, then you will understand that the interval between
probes will increase proportionally to the hash value. Quadratic probing is a
method with the help of which we can solve the problem of clustering that was
discussed above. This method is also known as the mid-square method. In this
method, we look for the i2‘th slot in the ith iteration. We always start from the
original hash location. If only the location is occupied then we check the other
slots.
let hash(x) be the slot index computed using hash function.
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S
…………………………………………..
…………………………………………..
Example: Let us consider table Size = 7, hash function as Hash(x) = x % 7 and
collision resolution strategy to be f(i) = i2 . Insert = 22, 30, and 50.
 Step 1: Create a table of size 7.

Hash table

 Step 2 – Insert 22 and 30

 Hash(22) = 22 % 7 = 1, Since the cell at index 1 is empty, we can
easily insert 22 at slot 1.
 Hash(30) = 30 % 7 = 2, Since the cell at index 2 is empty, we can
easily insert 30 at slot 2.

Insert keys 22 and 30 in the hash table

  Step 3: Inserting 50
 Hash(50) = 50 % 7 = 1
 In our hash table slot 1 is already occupied. So, we will search for
slot 1+12, i.e. 1+1 = 2,
 Again slot 2 is found occupied, so we will search for cell 1+22,
i.e.1+4 = 5,
 Now, cell 5 is not occupied so we will place 50 in slot 5.

Insert key 50 in the hash table

3. Double Hashing
 The intervals that lie between probes are computed by another hash
function. Double hashing is a technique that reduces clustering in an
optimized way. In this technique, the increments for the probing
sequence are computed by using another hash function. We use another
hash function hash2(x) and look for the i*hash2(x) slot in the ith rotation.
 let hash(x) be the slot index computed using hash function.
 If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S
If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x))
%S
If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x))
%S
…………………………………………..
…………………………………………..
Example: Insert the keys 27, 43, 92, 72 into the Hash Table of size 7. where
first hash-function is h1(k) = k mod 7 and second hash-function is h2(k) = 1 + (k
mod 5)
 Step 1: Insert 27
 27 % 7 = 6, location 6 is empty so insert 27 into 6 slot.
 Insert key 27 in the hash table

 Step 2: Insert 43
 43 % 7 = 1, location 1 is empty so insert 43 into 1 slot.

Insert key 43 in the hash table

Step 3: Insert 92
92 % 7 = 6, but location 6 is already being occupied and this is a collision
So we need to resolve this collision using double hashing.
hnew = [h1(92) + i * (h2(92)] % 7
= [6 + 1 * (1 + 92 % 5)] % 7
=9%7
=2
Now, as 2 is an empty slot,
so we can insert 92 into 2nd slot.

Insert key 92 in the hash table

Step 4: Insert 72
72 % 7 = 2, but location 2 is already being occupied and this is a collision.
So we need to resolve this collision using double hashing.
hnew = [h1(72) + i * (h2(72)] % 7
= [2 + 1 * (1 + 72 % 5)] % 7
=5%7
= 5,
Now, as 5 is an empty slot,
so we can insert 72 into 5th slot.
 Insert key 72 in the hash table

See this for step-by-step diagrams:

Comparison of the above three:
Linear probing has the best cache performance but suffers from clustering.
One more advantage of Linear probing is easy to compute.
Quadratic probing lies between the two in terms of cache performance and
clustering.
Double hashing has poor cache performance but no clustering. Double hashing
requires more computation time as two hash functions need to be computed.
[Link]. Separate Chaining Open Addressing

Open Addressing requires more

1. Chaining is Simpler to implement. computation.

In chaining, Hash table never fills

up, we can always add more In open addressing, table may
2. elements to chain. become full.

Open addressing requires extra

Chaining is Less sensitive to the care to avoid clustering and
3. hash function or load factors. load factor.

Open addressing is used when the

frequency and number of keys is
Chaining is mostly used when it is
4. known.
unknown how many and how
 [Link]. Separate Chaining Open Addressing

frequently keys may be inserted or

deleted.

Cache performance of chaining is not Open addressing provides better

good as keys are stored using linked cache performance as everything is
5. list. stored in the same table.

In Open addressing, a slot can be

Wastage of Space (Some Parts of hash used even if an input doesn’t map
6. table in chaining are never used). to it.

7. Chaining uses extra space for links. No links in Open addressing

Implementation of Dictionaries:-
Dictionary Data Structure
 Dictionary is one of the important Data Structures that is usually used to store data in
the key-value format. Each element presents in a dictionary data structure
compulsorily have a key and some value is associated with that particular key. In other
words, we can also say that Dictionary data structure is used to store the data in key-
value pairs. Other names for the Dictionary data structure are associative array, map,
and symbol table but broadly it is referred to as Dictionary.
 A dictionary or associative array is a general-purpose data structure that is used for
the storage of a group of objects.
 Many popular languages add Dictionary or associative array as a primitive data type in
their languages while other languages which don't consider Dictionary or associative
array as a primitive data type have included Dictionary or associative array in their
software libraries. A direct form of hardware-level support for the Dictionary or
associative array is Content-addressable memory.
 In Dictionary or associative array, the relation or association between the key and the
value is known as the mapping. We can say that each value in the dictionary is mapped
to a particular key present in the dictionary or vice-versa.
 The various operations that are performed on a Dictionary or associative array are:

o Add or Insert: In the Add or Insert operation, a new pair of keys and values is
added in the Dictionary or associative array object.
o Replace or reassign: In the Replace or reassign operation, the already existing
value that is associated with a key is changed or modified. In other words, a new
value is mapped to an already existing key.
 o Delete or remove: In the Delete or remove operation, the already present
element is unmapped from the Dictionary or associative array object.
o Find or Lookup: In the Find or Lookup operation, the value associated with a
key is searched by passing the key as a search argument.

Priority Queue?
 A priority queue is an abstract data type that behaves similarly to the normal
queue except that each element has some priority, i.e., the element with the
highest priority would come first in a priority queue. The priority of the
elements in a priority queue will determine the order in which elements are
removed from the priority queue.
 The priority queue supports only comparable elements, which means that the
elements are either arranged in an ascending or descending order.
 For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a
priority queue with an ordering imposed on the values is from least to the
greatest. Therefore, the 1 number would be having the highest priority while
22 will be having the lowest priority.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following characteristics:

o Every element in a priority queue has some priority associated with it.
o An element with the higher priority will be deleted before the deletion of the
lesser priority.
o If two elements in a priority queue have the same priority, they will be arranged
using the FIFO principle.

Let's understand the priority queue through an example.

We have a priority queue that contains the following values:

1, 3, 4, 8, 14, 22

All the values are arranged in ascending order. Now, we will observe how the priority
queue will look after performing the following operations:

o poll(): This function will remove the highest priority element from the priority
queue. In the above priority queue, the '1' element has the highest priority, so
it will be removed from the priority queue.
o add(2): This function will insert '2' element in a priority queue. As 2 is the
smallest element among all the numbers so it will obtain the highest priority.
 o poll(): It will remove '2' element from the priority queue as it has the highest
priority queue.
o add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8, so
it will obtain the third highest priority in a priority queue.

Types of Priority Queue

There are two types of priority queue:

o Ascending order priority queue: In ascending order priority queue, a lower priority
number is given as a higher priority in a priority. For example, we take the numbers
from 1 to 5 arranged in an ascending order like 1,2,3,4,5; therefore, the smallest
number, i.e., 1 is given as the highest priority in a priority queue.

o Descending order priority queue: In descending order priority queue, a higher

priority number is given as a higher priority in a priority. For example, we take the
numbers from 1 to 5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest
number, i.e., 5 is given as the highest priority in a priority queue.
Representation of priority queue
Now, we will see how to represent the priority queue through a one-way list.

We will create the priority queue by using the list given below in which INFO list
contains the data elements, PRN list contains the priority numbers of each data
element available in the INFO list, and LINK basically contains the address of the next
node.

Let's create the priority queue step by step.

In the case of priority queue, lower priority number is considered the higher
priority, i.e., lower priority number = higher priority.

Step 1: In the list, lower priority number is 1, whose data value is 333, so it will be
inserted in the list as shown in the below diagram:

Step 2: After inserting 333, priority number 2 is having a higher priority, and data values
associated with this priority are 222 and 111. So, this data will be inserted based on
the FIFO principle; therefore 222 will be added first and then 111.

Step 3: After inserting the elements of priority 2, the next higher priority number is 4
and data elements associated with 4 priority numbers are 444, 555, 777. In this case,
elements would be inserted based on the FIFO principle; therefore, 444 will be added
first, then 555, and then 777.

Step 4: After inserting the elements of priority 4, the next higher priority number is 5,
and the value associated with priority 5 is 666, so it will be inserted at the end of the
queue.
Implementation of Priority Queue
The priority queue can be implemented in four ways that include arrays, linked list,
heap data structure and binary search tree. The heap data structure is the most efficient
way of implementing the priority queue, so we will implement the priority queue using
a heap data structure in this topic. Now, first we understand the reason why heap is
the most efficient way among all the other data structures.

Analysis of complexities using different implementations:-

Implementation add Remove peek

Linked list O(1) O(n) O(n)

Binary heap O(logn) O(logn) O(1)

Binary search tree O(logn) O(logn) O(1)

What is Heap?
 A heap is a tree-based data structure that forms a complete binary tree, and
satisfies the heap property.
 If A is a parent node of B, then A is ordered with respect to the node B for all nodes
A and B in a heap.
 It means that the value of the parent node could be more than or equal to the value
of the child node, or the value of the parent node could be less than or equal to
the value of the child node. Therefore, we can say that there are two types of heaps:
 Max heap: The max heap is a heap in which the value of the parent node is greater
than the value of the child nodes.

 Min heap: The min heap is a heap in which the value of the parent node is less
than the value of the child nodes.

Both the heaps are the binary heap, as each has exactly two child nodes.

Priority Queue Operations

The common operations that we can perform on a priority queue are insertion,
deletion and peek. Let's see how we can maintain the heap data structure.
 o Inserting the element in a priority queue (max heap)

If we insert an element in a priority queue, it will move to the empty slot by looking
from top to bottom and left to right.

If the element is not in a correct place then it is compared with the parent node; if it is
found out of order, elements are swapped. This process continues until the element is
placed in a correct position.

o Removing the minimum element from the priority queue

As we know that in a max heap, the maximum element is the root node. When we
remove the root node, it creates an empty slot. The last inserted element will be added
in this empty slot. Then, this element is compared with the child nodes, i.e., left-child
and right child, and swap with the smaller of the two. It keeps moving down the tree
until the heap property is restored.

Applications of Priority queue

The following are the applications of the priority queue:

o It is used in the Dijkstra's shortest path algorithm.

o It is used in prim's algorithm
o It is used in data compression techniques like Huffman code.
o It is used in heap sort.
o It is also used in operating system like priority scheduling, load balancing and interrupt
handling.