UNIT IV :

Non-Linear Data Structures

Graphs: Graph Implementation Methods, Graph Traversal Methods – BFS and DFS
Hash Table Representation: hash functions, collision resolution-separate chaining,
open addressing-linear probing, quadratic probing, double hashing, and rehashing,
extendible hashing.

Introduction to Graphs
Graph is a non-linear data structure. It contains a set of points known as nodes (or vertices) and a
set of links known as edges (or Arcs). Here edges are used to connect the vertices. A graph is
defined as follows...

Graph is a collection of vertices and arcs in which vertices are connected with arcs

Graph is a collection of nodes and edges in which nodes are connected with edges

Generally, a graph G is represented as G = ( V , E ), where V is set of vertices and E is set of

edges.
Example
The following is a graph with 5 vertices and 6 edges.
This graph G can be defined as G = ( V , E )
Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.

Graph Terminology
We use the following terms in graph data structure...

Vertex
Individual data element of a graph is called as Vertex. Vertex is also known as node. In above
example graph, A, B, C, D & E are known as vertices.

Edge
An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is
represented as (startingVertex, endingVertex). For example, in above graph the link between
vertices A and B is represented as (A,B). In above example graph, there are 7 edges (i.e., (A,B),
(A,C), (A,D), (B,D), (B,E), (C,D), (D,E)).

Edges are three types.

1. Undirected Edge - An undirected egde is a bidirectional edge. If there is undirected edge

between vertices A and B then edge (A , B) is equal to edge (B , A).
 2. Directed Edge - A directed egde is a unidirectional edge. If there is directed edge
between vertices A and B then edge (A , B) is not equal to edge (B , A).
3. Weighted Edge - A weighted egde is a edge with value (cost) on it.

Undirected Graph
A graph with only undirected edges is said to be undirected graph.

Directed Graph
A graph with only directed edges is said to be directed graph.

Mixed Graph
A graph with both undirected and directed edges is said to be mixed graph.

End vertices or Endpoints

The two vertices joined by edge are called end vertices (or endpoints) of that edge.

Origin
If a edge is directed, its first endpoint is said to be the origin of it.

Destination
If a edge is directed, its first endpoint is said to be the origin of it and the other endpoint is said to
be the destination of that edge.

Adjacent
If there is an edge between vertices A and B then both A and B are said to be adjacent. In other
words, vertices A and B are said to be adjacent if there is an edge between them.

Incident
Edge is said to be incident on a vertex if the vertex is one of the endpoints of that edge.

Outgoing Edge
A directed edge is said to be outgoing edge on its origin vertex.

Incoming Edge
A directed edge is said to be incoming edge on its destination vertex.

Degree
Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree
Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Outdegree
Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Parallel edges or Multiple edges

If there are two undirected edges with same end vertices and two directed edges with same origin
and destination, such edges are called parallel edges or multiple edges.

Self-loop
Edge (undirected or directed) is a self-loop if its two endpoints coincide with each other.

Simple Graph
A graph is said to be simple if there are no parallel and self-loop edges.

Path
A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other vertex such
that each edge is incident to its predecessor and successor vertex.

Trivial Graph
A graph G= (V, E) is trivial if it contains only a single vertex and no edges.

Null Graph
It's a reworked version of a trivial graph. If several vertices but no edges connect them, a graph
G= (V, E) is a null graph.

Complete Graph
If a graph G= (V, E) is also a simple graph, it is complete. Using the edges, with n number of
vertices must be connected. It's also known as a full graph because each vertex's degree must be
n-1.
Pseudo Graph
If a graph G= (V, E) contains a self-loop besides other edges, it is a pseudograph.

Weighted Graph
A graph G= (V, E) is called a labeled or weighted graph because each edge has a value or
weight representing the cost of traversing that edge.
Cyclic Graph
If a graph contains at least one graph cycle, it is considered to be cyclic.

Acyclic Graph
When there are no cycles in a graph, it is called an acyclic graph.

Directed Acyclic Graph

It's also known as a directed acyclic graph (DAG), and it's a graph with directed edges but no
cycle. It represents the edges using an ordered pair of vertices since it directs the vertices and
stores some data.
Subgraph
The vertices and edges of a graph that are subsets of another graph are known as a subgraph.

Graph Representations
Graph data structure is represented using following representations...
1. Adjacency Matrix
2. Incidence Matrix
3. Adjacency List

[Link] Matrix
In this representation, the graph is represented using a matrix of size total number of vertices by
a total number of vertices. That means a graph with 4 vertices is represented using a matrix of
size 4X4. In this matrix, both rows and columns represent vertices. This matrix is filled with
either 1 or 0. Here, 1 represents that there is an edge from row vertex to column vertex and 0
represents that there is no edge from row vertex to column vertex.

For example, consider the following undirected graph representation...

Directed graph representation...

Incidence Matrix

In this representation, the graph is represented using a matrix of size total number of vertices by
a total number of edges. That means graph with 4 vertices and 6 edges is represented using a
matrix of size 4X6. In this matrix, rows represent vertices and columns represents edges. This
matrix is filled with 0 or 1 or -1. Here, 0 represents that the row edge is not connected to column
vertex, 1 represents that the row edge is connected as the outgoing edge to column vertex and -1
represents that the row edge is connected as the incoming edge to column vertex.

For example, consider the following directed graph representation...

Adjacency List

In this representation, every vertex of a graph contains list of its adjacent vertices.

For example, consider the following directed graph representation implemented using linked
list...
This representation can also be implemented using an array as follows..

Graph Traversal
Graph traversal is a technique used for a searching vertex in a graph. The graph traversal is also
used to decide the order of vertices is visited in the search process. A graph traversal finds the
edges to be used in the search process without creating loops. That means using graph traversal
we visit all the vertices of the graph without getting into looping path.

There are two graph traversal techniques and they are as follows...
1. DFS (Depth First Search)
2. BFS (Breadth First Search)
DFS (Depth First Search)
DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph
without loops. We use Stack data structure with maximum size of total number of vertices in the
graph to implement DFS traversal.

We use the following steps to implement DFS traversal...

 Step 1 - Define a Stack of size total number of vertices in the graph.
 Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to
the Stack.
 Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top
of stack and push it on to the stack.
 Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is
at the top of the stack.
  Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex
from the stack.
 Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
 Step 7 - When stack becomes Empty, then produce final spanning tree by removing
unused edges from the graph
Back tracking is coming back to the vertex from which we reached the current vertex.

Example
Program
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v) {
int i;
reach[v]=1;
for (i=1;i<=n;i++)
if(a[v][i] && !reach[i]) {
printf("\n %d->%d",v,i);
dfs(i);
}
}
void main()
{
int i,j,count=0;
printf("\n Enter number of vertices:");
scanf("%d",&n);
for (i=1;i<=n;i++) {
reach[i]=0;
for (j=1;j<=n;j++)
a[i][j]=0;
}
printf("\n Enter the adjacency matrix:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for (i=1;i<=n;i++) {
if(reach[i])
count++;
 }
if(count==n)
printf("\n Graph is connected"); else printf("\n
Graph is not connected");
}
OUTPUT:

Let's consider the below graph for the Depth First Search traversal.

Consider node 0 as a root node.

First, we insert the element 0 in the stack as shown below:

The node 0 has two adjacent nodes, i.e., 1 and 3. Now we can take only one adjacent node, either 1 or 3,
for traversing. Suppose we consider node 1; therefore, 1 is inserted in a stack and gets printed as shown
below:

Now we will look at the adjacent vertices of node 1. The unvisited adjacent vertices of node 1 are 3, 2, 5
and 6. We can consider any of these four vertices. Suppose we take node 3 and insert it in the stack as
shown below:

Consider the unvisited adjacent vertices of node 3. The unvisited adjacent vertices of node 3 are 2 and 4.
We can take either of the vertices, i.e., 2 or 4. Suppose we take vertex 2 and insert it in the stack as shown
below:
The unvisited adjacent vertices of node 2 are 5 and 4. We can choose either of the vertices, i.e., 5 or 4.
Suppose we take vertex 4 and insert in the stack as shown below:

Now we will consider the unvisited adjacent vertices of node 4. The unvisited adjacent vertex of node 4
is node 6. Therefore, element 6 is inserted into the stack as shown below:

After inserting element 6 in the stack, we will look at the unvisited adjacent vertices of node 6. As there
is no unvisited adjacent vertices of node 6, so we cannot move beyond node 6. In this case, we will perform
backtracking. The topmost element, i.e., 6 would be popped out from the stack as shown below:
The topmost element in the stack is 4. Since there are no unvisited adjacent vertices left of node 4;
therefore, node 4 is popped out from the stack as shown below:
The next topmost element in the stack is 2. Now, we will look at the unvisited adjacent vertices of node
2. Since only one unvisited node, i.e., 5 is left, so node 5 would be pushed into the stack above 2 and
gets printed as shown below:
Now we will check the adjacent vertices of node 5, which are still unvisited. Since there is no vertex left
to be visited, so we pop the element 5 from the stack as shown below:

We cannot move further 5, so we need to perform backtracking. In backtracking, the topmost element
would be popped out from the stack. The topmost element is 5 that would be popped out from the stack,
and we move back to node 2 as shown below:
Now we will check the unvisited adjacent vertices of node 2. As there is no adjacent vertex left to be
visited, so we perform backtracking. In backtracking, the topmost element, i.e., 2 would be popped out
from the stack, and we move back to the node 3 as shown below:
Now we will check the unvisited adjacent vertices of node 3. As there is no adjacent vertex left to be
visited, so we perform backtracking. In backtracking, the topmost element, i.e., 3 would be popped out
from the stack and we move back to node 1 as shown below:
After popping out element 3, we will check the unvisited adjacent vertices of node 1. Since there is no
vertex left to be visited; therefore, the backtracking will be performed. In backtracking, the topmost
element, i.e., 1 would be popped out from the stack, and we move back to node 0 as shown below:
We will check the adjacent vertices of node 0, which are still unvisited. As there is no adjacent vertex
left to be visited, so we perform backtracking. In this, only one element, i.e., 0 left in the stack, would
be popped out from the stack as shown below:

BFS (Breadth First Search)

BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph
without loops. We use Queue data structure with maximum size of total number of vertices in
the graph to implement BFS traversal.
We use the following steps to implement BFS traversal...

25
 Step 1 - Define a Queue of size total number of vertices in the graph.
 Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it
into the Queue.
 Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the
Queue and insert them into the Queue.
 Step 4 - When there is no new vertex to be visited from the vertex which is at front of the
Queue then delete that vertex.
 Step 5 - Repeat steps 3 and 4 until queue becomes empty.
 Step 6 - When queue becomes empty, then produce final spanning tree by removing
unused edges from the graph
EXAMPLE

26
27
28
Let's consider the below graph for the breadth first search traversal.

Suppose we consider node 0 as a root node. Therefore, the traversing would be started from node 0.

Once node 0 is removed from the Queue, it gets printed and marked as a visited node.
Once node 0 gets removed from the Queue, then the adjacent nodes of node 0 would be inserted in a
Queue as shown below:

Now the node 1 will be removed from the Queue; it gets printed and marked as a visited node
Once node 1 gets removed from the Queue, then all the adjacent nodes of a node 1 will be added in a
Queue. The adjacent nodes of node 1 are 0, 3, 2, 6, and 5. But we have to insert only unvisited nodes
in a Queue. Since nodes 3, 2, 6, and 5 are unvisited; therefore, these nodes will be added in a Queue
as shown below:

The next node is 3 in a Queue. So, node 3 will be removed from the Queue, it gets printed and marked
as visited as shown below:

29
Now, the next node in the Queue is 2. So, 2 would be deleted from the Queue. It gets printed and
marked as visited as shown below:

Once node 2 gets removed from the Queue, then all the adjacent nodes of node 2 except the visited
nodes will be added in a Queue. The adjacent nodes of node 2 are 1, 3, 5, 6, and 4. Since the nodes 1
and 3 have already been visited, and 4, 5, 6 are already added in the Queue; therefore, we do not need
to insert any node in the Queue.

The next element is 5. So, 5 would be deleted from the Queue. It gets printed and marked as visited
as shown below:

Once node 5 gets removed from the Queue, then all the adjacent nodes of node 5 except the visited
nodes will be added in the Queue. The adjacent nodes of node 5 are 1 and 2. Since both the nodes
have already been visited; therefore, there is no vertex to be inserted in a Queue.

The next node is 6. So, 6 would be deleted from the Queue. It gets printed and marked as visited as
shown below:

Once the node 6 gets removed from the Queue, then all the adjacent nodes of node 6 except the visited
nodes will be added in the Queue. The adjacent nodes of node 6 are 1 and 4. Since the node 1 has
already been visited and node 4 is already added in the Queue; therefore, there is not vertex to be
inserted in the Queue.

The next element in the Queue is 4. So, 4 would be deleted from the Queue. It gets printed and marked
as visited.
Once the node 4 gets removed from the Queue, then all the adjacent nodes of node 4 except the visited
nodes will be added in the Queue. The adjacent nodes of node 4 are 3, 2, and 6. Since all the adjacent
nodes have already been visited; so, there is no vertex to be inserted in the Queue.

30
PROGRAM :
#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
visited[v]=1;
for (i=1;i<=n;i++)
{
if(a[v][i] && !visited[i])
{
printf("%d-%d\n",v,i);
q[++r]=i;
}
}
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}

31
}
void main()
{
int v;
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
// GRAPH IS GIVEN AS ADJACENCY MATRIX
printf("\n Enter graph data in matrix form:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
printf("BFS visiting order is\n");
bfs(v);
printf("\n The node which are reachable are:\n");
for (i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i); else
printf("\n Bfs is not possible");
}
OUTPUT :

32
 Applications of Breadth First Search Algorithm

1. Minimum spanning tree for unweighted graphs:In Breadth-First Search we can reach from any
given source vertex to another vertex, with the minimum number of edges, and this principle can
be used to find the minimum spanning tree which is the path covering all vertices in the shortest
paths.
2. Peer-to-peer networking: In Peer-to-peer networking, to find the neighboring peer from any other
peer, the Breadth-First Search is used.
3. Crawlers in search engines: Search engines need to crawl the internet. To do so, they can start
from any source page, follow the links contained in that page in the Breadth-First Search manner,
and therefore explore other pages.
4. GPS navigation systems: To find locations within a given radius from any source person, we can
find all neighboring locations using the Breadth-First Search, and keep on exploring until those
are within the K radius.
5. Broadcasting in networks: While broadcasting from any source, we find all its neighboring peers
and continue broadcasting to them, and so on.
6. Path Finding: To find if there is a path between 2 vertices, we can take any vertex as a source,
and keep on traversing until we reach the destination vertex. If we explore all vertices reachable
from the source and cannot find the destination vertex, then that means there is no path between
these 2 vertices.
7. Finding all reachable Nodes from a given Vertex: All vertices that are reachable from a given
vertex can be found using the BFS approach in any disconnected graph. The vertices that are
marked as visited in the visited array after the BFS is complete contain all those reachable vertices.

Applications of Depth First Search Algorithm

1. Finding any path between two vertices u and v in the graph.

2. Finding the number of connected components present in a given undirected graph.
3. For doing topological sorting of a given directed graph.
4. Finding strongly connected components in the directed graph.
5. Finding cycles in the given graph.
6. To check if the given graph is bipartite.

Complexity Analysis of BFS and DFS Algorithms

Time Complexity Space Complexity

BFS O(V + E) O(V)

DFS O(V + E) O(V)

Here, V is the number of nodes and E is the number of edges.

33
Differences between BFS and DFS

BFS DFS
Full form BFS stands for Breadth First DFS stands for Depth First Search.
Search.

Technique It a vertex-based technique to It is an edge-based technique because the

find the shortest path in a graph. vertices along the edge are explored first
from the starting to the end node.

Definition BFS is a traversal technique in DFS is also a traversal technique in which

which all the nodes of the same traversal is started from the root node and
level are explored first, and then explore the nodes as far as possible until we
we move to the next level. reach the node that has no unvisited adjacent
nodes.

Data Structure Queue data structure is used for Stack data structure is used for the BFS
the BFS traversal. traversal.

Backtracking BFS does not use the DFS uses backtracking to traverse all the
backtracking concept. unvisited nodes.
Number of BFS finds the shortest path having In DFS, a greater number of edges are
edges a minimum number of edges to required to traverse from the source vertex to
traverse from the source to the the destination vertex.
destination vertex.

Optimality BFS traversal is optimal for those DFS traversal is optimal for those graphs in
vertices which are to be searched which solutions are away from the source
closer to the source vertex. vertex.

Speed BFS is slower than DFS. DFS is faster than BFS.

Suitability for It is not suitable for the decision It is suitable for the decision tree. Based on
decision tree tree because it requires exploring the decision, it explores all the paths. When
all the neighboring nodes first. the goal is found, it stops its traversal.

Memory efficient It is not memory efficient as it It is memory efficient as it requires less

requires more memory than DFS. memory than BFS.

34
 Hash Table Representation
Why Hashing?
 Hashing is used to index and retrieve items in a database because it is faster to find the
item using the shorter hashed key than to find it using the original value.
 Hashing allows to update and retrieve any data entry in a constant time O(1) i.e the
operation does not depend on the size of the data.

Hashing in Data Structure

 In data structures, Hashing is a well-known technique to search any particular element
among several elements.
 It minimizes the number of comparisons while performing the search.
 Hash table is one of the most important data structures that uses a special function known
as a hash function that maps a given value with a key to access the elements faster.
HASHING:
 Hashing is the process of converting a given key into another value.
 A hash function is used to generate the new value according to a mathematical algorithm.
 The result of a hash function is known as a hash value or simply, a hash.
 This hash values are stored in a table called Hash Table.
 If h is a hash function and k is a key then h(k) is called the hash of k and is the index at
which a record with key k should be placed.

Hashing Mechanism
 In hashing, an array data structure called as Hash table is used to store the data items.
 Based on the hash key value, data items are inserted into the hash table.

To achieve a good hashing mechanism, It is important to have a good hash function with the
following basic requirements:
1. Easy to compute: It should be easy to compute and must not become an algorithm in
itself.

2. Uniform distribution: It should provide a uniform distribution across the hash table and
should not result in clustering.

3. Less collisions: Collisions occur when pairs of elements are mapped to the same
hash value. These should be avoided.

 h(key)=hash value

35
 HASH FUNCTIONS
Various hashing functions that can be used are:
1. Division Method
2. Midsquare Method
3. Folding Method
4. Multiplication Method

1. Division Method: This method takes a key and divides it by the table size and returns
the remainder as its hash value.

Hash value = Key % Size of HashTable

h (K) = K mod M
K is the key value for which hash value has to be calaulated.
M is the size of hash table

Example: let the Hash table is Array of size 10

2. Midsquare Method: Key multiplied with itself and mid of that key square is taken as the
index /hasv value.
h(k) = K2 and get middle digits(based on size of table)
 Assume table size is 1000, so no. mid digits to be taken is 3

36
  0-999 will be array index i.e max index value is 3 digit long

Key: 1234 4321 5000

key square: 1522756 18684004 25000000

Index: 227 840 000

[Link] Shift method/Folding Method:

 Divide the element into a number of parts (digits), where each part contains same
number of digits except the last part may have lesser digits than the other parts.
 The hash value is generated by adding individual parts, ignoring the last carry.
 Divide the key in parts whose size matches the size of required address.
 Note that the number of digits in each part of the key will vary depending upon the
size of the hash table. For example, if the hash table has a size of 1000, then there
are 1000 locations in the hash table. To address these 1000 locations, we need at
least three digits; therefore, each part of the key must have three digits except the
last part which may have lesser digits.


Example:
Key: 123456789 and size of required address is 3 digits (size 1000).

123
+
456
+
789
= = 1368
----368 is the hash value after discarding 1
• Ex: 53218097 is divided as 532 180 97 and added to get 809 as index

[Link] Method:
 Choose a constant 'a' such that 0<a<1
 Multiply the key with 'a'
 Extract the fractional part of 'ka' by doing modulus operation with 1
 Multiply the result of step 3 by size of Hash Table.

h(k) = [size*(key*a mod 1)]

Ex: key=123

n=100

37
 a=0.618033

h(123) = 100 *(123 * 0.618033 mod 1)

= 100 (76.018059 mod 1)

= 100 (0.018059)

= 1 (hash value)

Collision Resolution Techniques:

Collision:
 No matter what the hash function, there is a possibility that two different keys could
resolve to the same hash value. This situation is known as Collision.
 This is the problem with Hashing, because practically it is not possible to avoid
collisions unless you have perfect hash function knowing the elements beforehand.

Collision Resolution:

38
The following techniques can be used to handle the collisions:
• Open Addressing (Array based implementation)
• Separate Chaining (Linked list based implementation)

[Link] Addressing
1. In open addressing, instead of in linked lists, all entry records are stored in the
array.
2. When a new entry has to be inserted, the hash index of the hashed value is
computed and then the array is examined (starting with the hashed index).
a. If the slot at the hashed index is unoccupied, then the entry record is
inserted in slot at the hashed index
else i.e if there is a collision then it proceeds in some probe sequence until
it finds an unoccupied slot.

39
Methods of Open Addressing:

a) Linear Probing:
 When collision occurs, we linearly probe for the next free bucket.
 Linear probing is when the interval between successive probes is fixed (usually to 1).
 Let’s assume that the hashed index for a particular entry is index.
 the following hash function is used to resolve the collision: h(k, i) = [h’(k) + i] mod m
 Where
 m is the size of the hash table,
 h’(k) = (k mod m), and i is the probe number that varies from 0 to m–1.
 The probing sequence for linear probing will be:
 index = index % hashTableSize
 index = (index + 1) % hashTableSize
 index = (index + 2) % hashTableSize
 index = (index + 3) % hashTableSize and so on...

Example-1: Company with 12 employees

• Applying division method choosing a prime number M close to 12 such as M=13

• So hash value=key%13

• Employee codes 40 and 66 give a hash value 1;as both can’t be stored at same location
the next vacant position is to be given i.e 3 is given.

40
Example-2:

Let us consider a simple hash function as "key mod 7" and the sequence of keys as 50, 700,
76, 85, 92, 73, 101. The probing is done as follows:

41
The disadvantages of linear probing are as follows −

 Linear probing causes a scenario called "primary clustering" in which there are large
blocks of occupied cells within the hash table.
 The values in linear probing tend to cluster which makes the probe sequence longer and
lengthier.
 Primary Clustering: The main problem with linear probing is clustering, many
consecutive elements form groups and it starts taking time to find a free slot or to search
an element. [ as they go through same path for finding free slots]

b) Quadratic Probing: to avoid primary clustering caused by linear probing

 Quadratic probing is similar to linear probing ; the only difference is the interval between
successive probes.
 Here, when the slot at a hashed index for an entry record is already occupied, you must
start traversing until you find an unoccupied slot.
 The interval between slots is computed by adding the successive value of an arbitrary
polynomial with the original hashed index.
 the following hash function is used to resolve the collision:
 h(k, i) = [h’(k) + c1 i + c2 i2 ] mod m
 where m is the size of the hash table, h’(k) = (k mod m),
 i is the probe number that varies from 0 to m–1, and
 c1 and c2 are constants such that c1 and c2 ≠ 0.
 For example, Instead of moving one cell each time, move 'i 2 ' cells from the point of
collision.

let hash(x) be the slot index computed using hash function.

• If slot [hash(x) % Size] is full, then we try [(hash(x) + 1*1) % Size]

• If [(hash(x) + 1*1) % Size] is also full, then we try [(hash(x) + 2*2) % Size]
• If [(hash(x) + 2*2) % Size] is also full, then we try [(hash(x) + 3*3) % Size]

42
 Simply
• In linear probing if a collision occurs then the value is inserted at the next vacant
position searching as x+1,x+2,x+3 and so on.

• In quadratic probing the next position is calculated as x+12 , x+22 ,x+32 etc

i.e first adjacent cell is picked ,if that is occupied, then it tries 4 cells away.
• This also creates clusters as all the collision keys pass through the same path.
This is called secondary clustering

c) Double Hashing

 Double hashing is a collision resolving technique in Open Addressed Hash tables.

 Double hashing is applying a second hash function to key when a collision occurs.

Double hashing can be done using :

(hash1(key) + i * hash2(key)) % size of the hash table

Here hash1() and hash2() are hash functions

 Even after doing Double Hashing if there is a collision then it has to be repeated
by incrementing i

 Generally first hash function is hash1(key) = key % TABLE_SIZE

 A second hash function hash2() should fill all the cells in the table
 A popular second hash function is hash2(key) = PRIME – (key % PRIME) where PRIME
is a prime number which should be less than size of the table

 (hash1(key) + i * hash2(key)) % size of the hash table

43
d) Rehashing:

Load Factor:
 Load factor or λ= n/M
where n is no. of entries in the hash table and M is the size of the table
 λ < 1 (should be always less than one) i.e. no. of entries cannot exceed table size
and if λ is equal to 1 then there is no space left for inserting new keys into the
hash table. So we can say M>n
 so if λ ==1 then we should increase the hash table size [ the standard λ value to
start Rehashing is by default 0.75 ]
 Rehashing
o the hash table size should be doubled and the nearest prime number of it
should be considered as new table size
o let say new hash table size is M`;
so M`=nearest prime number > 2M
o the first hash function key % M is modified as key % M`
o now apply the hash function again on the keys and fill the entries in the
hash table
o Ex:

44
 Let say h(key)=key mod 3
Keys = (6,7,8)
6%3=0
7%3=1
8%3=2
6 7 8
0 1 2
n=3([Link] entries)
M=3(tablesize)
λ =1 so perform Rehashing
choose M` as nearest prime to 2M so M` is 7
applying the hash function on keys again with new table size
6%7=6
7%7=0
8%7=1
7 8 6
0 1 2 3 4 5 6

Now n=3 ; M`=7

λ =3/7 <1

[Link] Chaining:
• Second method of collision resolution

• The idea is to make each cell of hash table point to a linked list of records that have same
hash function value.

• The approach is to install a linked list at each index in the hash table

• A data item’s key is hashed to the index in the usual way and the item is inserted into the
linked list at that index

• Other items that hash to the same index are simply added to the linked list ; there is no
need to search for empty cells in the primary array

• In chaining, each location in a hash table stores a pointer to a linked list that contains all
the key values that were hashed to that location. That is, location l in the hash table points
to the head of the linked list of all the key values that hashed to l. However, if no key value
hashes to l, then location l in the hash table contains NULL. Figure below shows how the
key values are mapped to a location in the hash table and stored in a linked list that
corresponds to that location.

45
 •

Ex:1
Let us consider a simple hash function as “key mod 7” and sequence of keys as
50, 700, 76, 85, 92, 73, 101

Ex-2:

46
 0 52
X
1 40 66
X
2 28 X
3

4 17 43 69 X

Advantages:

1. Simple to implement.
2. Hash table never fills up, we can always add more elements to the chain.
3. Less sensitive to the hash function or load factors.
4. It is mostly used when it is unknown how many and how frequently keys may be
inserted or deleted.

Disadvantages:

1. 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.
2. Wastage of Space (Some Parts of hash table are never used)
3. If the chain becomes long, then search time can become O(n) in the worst case.
4. Uses extra space for links.

Extendible Hashing (Dynamic approach):

 Extendible Hashing is a dynamic hashing method wherein directories and buckets are
used to hash data.

 Directories:
 The directories store addresses of the buckets in pointers.
 An id is assigned to each directory which may change each time when
Directory Expansion takes place.
 Buckets: The buckets are used to hash the actual data.
 Global Depth:
 It is associated with the Directories.

47
  they denote the number of bits which are used by the hash function to
categorize the keys.
 Global Depth = Number of bits in directory id.
 Local Depth:
 It is the same as that of Global Depth except for the fact that Local Depth is
associated with the buckets and not the directories.
 Local Depth is always less than or equal to the Global Depth.
 Bucket Splitting: When the number of elements in a bucket exceeds a particular size,
then the bucket is split into two parts.
 Directory Expansion:
 Directory Expansion Takes place when a bucket overflows.
 Directory Expansion is performed when the local depth of the overflowing
bucket is equal to the global depth.
 Steps
o Step 1 – Analyze Data Elements
o Step 2 – Convert into binary format
o Step 3 – Check Global Depth of the directory
o Step 4 – Identify the Directory
 Eg. If the binary obtained is: 110001 and the global-depth is 3. So, the hash
function will return 3 LSBs of 110001 i.e 001.
o Step 5 – Navigation: Now, navigate to the bucket pointed by the directory with
directory-id 001

o Step 6 –
 Insertion and Overflow Check: Insert the element and check if the bucket
overflows.
 If an overflow is encountered, go to step 7 followed by Step 8, otherwise,
go to step 9.

48
 o Step 7 – Tackling Over Flow Condition during Data
 Insertion: While inserting data in the buckets, Bucket may overflow.
 Then first check if the local depth is less than or equal to the global depth.
Then choose one of the cases below.
 Case1: If the local depth of the overflowing Bucket is equal to the
global depth, then Directory Expansion, as well as Bucket Split,
needs to be performed. Then increment the global depth and the
local depth value by 1. And, assign appropriate pointers. Directory
expansion will double the number of directories present in the hash
structure.
 Case2: In case the local depth is less than the global depth, then
only Bucket Split takes place. Then increment only the local depth
value by 1. And, assign appropriate pointers.

o Step 8 – Rehashing of Split Bucket Elements: The Elements present in the

overflowing bucket that is split are rehashed w.r.t the new global depth of the
directory.

Ex: let us consider the following elements: 16,4,6,22,24,10,31,7,9,20,26.

Bucket Size: 3 (Assume)

Solution: First, calculate the binary forms of each of the given numbers.

16- 10000

49
 4- 00100
6- 00110
22- 10110
24- 11000
10- 01010
31- 11111
7- 00111
9- 01001
20- 10100
26- 01101

 Initially, the global-depth and local-depth is always 1

Inserting 16:
The binary format of 16 is 10000 and global-depth is 1. The hash function returns 1 LSB of
10000 which is 0. Hence, 16 is mapped to the directory with id=0.

Inserting 4 and 6:
Both 4(100) and 6(110)have 0 in their LSB.

50
Inserting 22: The binary form of 22 is 10110. Its LSB is 0. The bucket pointed by directory 0 is
already full. Hence, Over Flow occurs.

Step 7-Case 1, Since Local Depth = Global Depth, the bucket splits and directory expansion takes
place. Also, rehashing of numbers present in the overflowing bucket takes place after the split.
And, since the global depth is incremented by 1, now,the global depth is 2. Hence, 16,4,6,22
are now rehashed w.r.t 2 LSBs.[ 16(10000),4(100),6(110),22(10110) ]

the bucket which was underflow has remained untouched. But, since the number of directories has

51
 doubled, we now have 2 directories 01 and 11 pointing to the same bucket. This is because the
local-depth of the bucket has remained 1. And, any bucket having a local depth less than the
global depth is pointed-to by more than one directories.

Inserting 24 and 10: 24(11000) and 10 (1010) can be hashed based on directories with id 00 and
10. Here, we encounter no overflow condition

inserting 31,7,9: All of these elements[ 31(11111), 7(111), 9(1001) ] have either 01 or 11 in their
LSBs. Hence, they are mapped on the bucket pointed out by 01 and 11. We do not encounter
any overflow condition here.

Inserting 20: Insertion of data element 20 (10100) will again cause the overflow problem

52
20 is inserted in bucket pointed out by 00. Step 7-Case 1----- since the local depth of the bucket
= global-depth, directory expansion (doubling) takes place along with bucket splitting.
Elements present in overflowing bucket are rehashed with the new global depth. Now, the new
Hash table looks like this
16-10000, 4-0100,24-11000,20-10100

Inserting 26: Global depth is 3. Hence, 3 LSBs of 26(11010) are considered. Therefore 26 best
fits in the bucket pointed out by directory 010.

53
Bucket overflow----Step 7-Case 2, since the local depth of bucket < Global depth (2<3),
directories are not doubled but, only the bucket is split and elements are rehashed.
Finally, the output of hashing the given list of numbers is obtained.
6-00110,22-10110,10-01010,26-11010

o 11 numbers hashing is successful

54
Ex-2 for practice

APPLICATIONS OF HASHING

Hash tables are widely used in situations where enormous amounts of data have to be
accessed to quickly search and retrieve information.

A few typical examples where hashing is used are given here.

 Databases: Hashing is used to index and search large databases efficiently.
 Cryptography: Hash functions are used to generate message digests, which are used to
verify the integrity of data and protect against tampering.
 Caching: Hash tables are used in caching systems to store frequently accessed data and
improve performance.
 Spell checking: Hashing is used in spell checkers to quickly search for words in a
dictionary.

55