Module-5
(Concept of Searching)
Algorithm for Linear Search
Linear_Search ( Array, size, item )
S1: Read : size
Read : Array
S2: Set Loc := 0
S3: Repeat step 3 for ( i = 1 to size )
if ( item = Array[i] ), then
Set Loc := i
Return
[end of if]
[end of for]
S4: if ( Loc = 0 ), then
Print : ‘Item not found’
Else
Print : loc
[end of if - else]
S5: Exit
Algorithm for Binary Search
Binary_Search ( Array, size, item )
S1: Read : Array
Set Lb := 1
Set Ub := size
S2: Set Loc := 0
S3: Repeat step 3 to step 6 while ( Lb < Ub )
S4: Set mid := ( Lb + Ub ) / 2
if ( Array [ mid ] = Array [i] ), then
Set Loc := i
Return
[end of if]
[end of for]
S4: if ( Loc = 0 ), then
Print : ‘Item not found’
Else
Print : loc
[end of if - else]
S5: Exit
Hashing:
Hashing is a searching or storing technique which helps to map the key into its
corresponding value in the Hash table.
Hashing is a process of mapping large amount of data item to a table using some
hash function.
Hash Table:
Hash Table is a special data structure which stores the values with their
corresponding key as a pair of values.
Hash Key Actual Value
n-1
Hash Function:
It is a special function which assigns a unique key to each value stored inside the
Hash table.
Types of
Hash Function
Division Folding Mid-Square
Method Method Method
Division Method:
In this method the modulo of the item by table size is obtained and the obtained
modulo value is considered as the hash key of the data item.
e.g. H(x) = (a) mod L
H(x) = (b) mod L
H(x) = (c) mod L
where a, b, c are the data items and L represents the size of the Hash table.
Folding Method:
This method breaks the key value into different pieces of equal sizes (where the last
piece mayn’t be equal size).
Obtain the sum of values of all the different pieces.
Obtain the modulo of the sum value by table size and the obtained modulo value is
considered the hash key of the data item.
e.g. H(x) = ( a + b + c ) mod L
where a, b, c are the different pieces of data items and L represents the size of
the Hash table.
What is Collision?
Inside the hash table when more than one value are hashed to a particular hash key,
then such situation is called as collision.
Suppose we want to add a new data item with key ‘k’ in a hash table, but the index
address H(k) is already occupied by another item. This situation is known as a
collision.
Collision Resolution:
Collision
Resolution
Open Closed
Addressing Addressing
Linear Quadratic Double Separate
Probing Probing Hashing Chaining
Closed Hashing (Separate Chaining)
In closed addressing, all the keys are stored inside the hash table. Each slot of the hash
table is linked with linked list. So if a collision occurs the data item stores in the linked
list.
In the chaining approach, the hash table is an array of linked lists.
Q. Consider a hash table with 6 slots. The collisions are resolved by using separate
chaining. The following 9 keys are inserted in the order: 5, 18, 28, 19, 15, 20, 10, 37, 49.
The maximum, minimum, and average chain length respectively in the hash table are
Ans:
Maximum chain length is 3 because 3 elements are stored in Hash key value 1.
Minimum chain length is 1 because every Hash key has at least one element.
Average chain length is (1+3+1+1+2+1) / 6 = 1
0 18
1 19 37 49
2 20
3 15
4 28 10
5 5
Linear Probing
In this technique, if a value is already stored at a location generated by h(k), and
when collision occurs then we do a sequential search to find the empty location.
Here the idea is to place a value in the next available position.
Here array or hash table is considered circular because when the last slot reached an
empty location not found then the search proceeds to the first location of the array.
h(k, i) = [h(k) + i] mod m
Question
Find the index value of each element in the sequence of item 96, 48, 63, 29, 87, 77, 65,
94, 61. Consider the size of the Hash table is 10
Hash Element
Key
0 77
1 61
2
3 63
4 94
5 65
6 96
7 87
8 48
9 29
87 mod 10 = 7
The value present at key 7 is 87
77 mod 10 = 7
But in key 7 already there is an element 87 present, therefore the new key value
obtained as
(7+1) mod 10 = 8 (48 present)
(7+2) mod 10 = 9 (29 Present)
(7+3) mod 10 = 0
Therefore the new key value for the element 77 is 0.
Quadratic Probing
Quadratic probing solves the clustering problem which is in linear probing because
instead of doing a linear search, it does a quadratic search.
In this technique, if a value is already stored at a location generated by h(k), then the
following hash function is used to resolve the collision:
h(k, i) = (h(k) + i^2) mod m
The disadvantage of quadratic probing is it does not search all locations of the list.
Question
Find the index value of each element in the sequence of item 20, 19, 11, 22, 33, 39, 27, 38.
Consider the size of the Hash table is 10.
Hash Element
Key
0 20
1 11
2 22
3 33
4
5
6 39
7 27
8 38
9 19
19 mod 10 = 9
The value present at key 9 is 19
39 mod 10 = 9
But in key 9 already there is an element 19 present, therefore the new key value
obtained as
(9 + 1^2 ) mod 10 = 0 (20 present)
(9 + 2^2) mod 10 = 3 (29 Present)
(7 + 3^2) mod 10 = 6
Therefore the new key value for the element 39 is 6.
Double Hashing
Generally, in hashing technique it consists a hash function to produce an index or key
for the value in the hash table.
However, in double hashing technique it uses two hash functions to obtain an index for
the value, hence it is called as double hashing.
The second hash function provides an offset value if the first hash function produces a
collision.
h(key, i) = (firstHashfunction(key) + i * secondHashFunction(key)) % m
Question
Find the index value of each element in the sequence of item 20, 48, 34, 45, 55, 71.
Consider the size of the Hash table is 11
Hash Element
Key
0 55
1 34
2
3
4 48
5 71
6
7 45
8
9 20
10
Let consider the two hash functions to insert the keys into hash table as:
First hash function : h1(k) = k mod 11
Second hash function : h2(k) = 8 - (k mod 8)
20 mod 11 = 9
34 mod 11 = 1
45 mod 11 = 1
But in key 1 already there is an element 34 present, therefore the new key value
obtained as
h2(45) = 8 - (45 mod 8) = 3
h(45, 1) = (1 + 1 * 3) mod 11 = 4 ( 48 present )
h(45, 2) = (1 + 2 * 3) mod 11 = 7
Therefore the new key value for the element 45 is 7.
Rehashing:
In general, after insertions of some elements into the hash table the number of free spaces
reduces in the hash table, which causes the load factor exceeds a certain threshold (often
set to 0.75), and the possibility of collisions increases.
To avoid this, the hash table needs to be resized and the elements can be rehashed to new
buckets, which decreases the load factor and reduces the number of collisions. This
process is known as rehashing.
𝑵𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝒔
The load factor can be calculated as:
𝑻𝒂𝒃𝒍𝒆 𝑺𝒊𝒛𝒆
If load factor exceeds a threshold (usually 0.7), then rehashing procedure is triggered.
Question
Suppose, we have a hash table of size 6. We want to insert keys 20, 34, 45, 70, 56 in the
hash table using Rehashing procedure.
h(20) = 20 mod 6 = 2
LF = 1/6 = 0.16 < 0.75
h(34) = 34 mod 6 = 4
LF = 2/6 = 0.33 < 0.75
h(45) = 45 mod 6 = 3
LF = 3/6 = 0.5 < 0.75
h(70) = 70 mod 6 = 4
LF = 4/6 = 0.6 < 0.75
4th position already filled, so apply Linear probing here to find the new locations as 5.
Hash Element
Key
0
1
2 20
3 45
4 34
5 70
h(56) = 56 mod 6 = 2
LF = 5/6 = 0.8 > 0.75 (So, here Rehashing is triggered)
As per the rehashing the size will be doubled, so the new size will be 12
h(20) = 20 mod 12 = 8
LF = 1/12 = 0.08 < 0.75
h(34) = 34 mod = 10
LF = 3/12 = 0.25 < 0.75
h(45) = 45 mod 12 = 9
LF = 4/12 = 0.33 < 0.75
h(70) = 70 mod 12 = 10
LF = 5/12 = 0.41 < 0.75
10th position already filled, so apply here Linear probing to find the new locations as 11.
Hash Element
Key
0 56
1
2
3
4
5
6
7
8 20
9 45
10 34
11 70
h(56) = 56 mod 12 = 8
LF = 6/12 = 0.5 < 0.75