Advanced Data Structure and

Algorithms
1

 Trees

 Graphs

 Hashing

 Search trees, Indexing, and multiways trees

 File Organization
 2

UNIT 3 HASHING
Supports very fast retrieval via a
key
 Contents
3

1. Hash Table
◻ Hash function, Bucket, Collision, Probe
◻ Synonym, Overflow, Open hashing, Closed hashing
◻ Perfect hash function, Load density, Full table, Load factor,
rehashing
2. Issues in hashing
◻ Hash functions- properties of good hash function
◻ Division, Multiplication, Extraction, Mid-square, Folding and
universal, Collision
3. Collision resolution strategies-
◻ Open addressing and chaining
4. Hash table overflow - extended hashing
5. Dictionary- Dictionary as ADT, ordered dictionaries
6. Skip List- representation, searching and operations- insertion,
removal.
 Searching - most frequent and prolonged tasks
4

 Searching for a particular data record from a large amount of data.

 Consider the problem of searching an array for a given value.
 If the array is not sorted, the search requires O(n) time

 If the value ISN’T there, we need to search all n elements

 If the value IS there, we search n/2 elements on average
 If the array is sorted, we can do a binary search
 A binary search requires O(log n) time

 About equally fast whether the element is found or not

 More better performance ?

 How about an O(1), that is, constant time search?

 We can do it if the array is organized in a particular way

 Search performance
5

 Binary search tree helps to improve the efficiency of

searches.
 From linear search to binary search, the search
efficiency improved from O(n) to O(log n) .
 Another data structure, called a hash table, which
helps to increase the search efficiency to O(1), or
some constant time.
 HASHING - is a method of directly computing the
address of the record through key by using a suitable
mathematical function called the hash function.
 Hash Table – Data structure for hashing
6

 A hash table is an array-based structure used to store <key,

information> pairs.
 It is a data structure that stores elements and allows insertions,
lookups, and deletions in O(1) time.
 Is an alternative method for dictionary representation.
 A hash function is used to map keys into their positions in the
table – Hashing.
 Hash table operations:
 Search – Compute hash function f(k) & CHECK if a pair exists.
 Insert – Compute function f(k) & PLACE it in appropriate position.
 Delete – Compute function f(k) & DELETE the pair in that position.
 In an ideal scenario, hash table search/insert/delete takes θ(1).
 Hash Table = Array + Hash function
7

 A hash table is made up of two parts:

 an array (the actual table where the data to be searched is
stored) and
 a mapping function, known as a hash function.
 The hash function - is a mapping from the input space to
the integer space that defines the indices of the array.

Maps input space to

indices
 Hashing
8

 The hash function provides a way for assigning numbers to the input
such that the data can be stored at the array index corresponding to
the assigned number.
 Hashing is similar to indexing as it involves associating a key with a
relative record address.
 With hashing the address generated appears to be random —
 No obvious connection between the key and the location of the
corresponding record.
 Sometimes referred to as randomizing.
 With hashing, two different keys may be transformed to the same
address
 Two records may be sent to the same place in a file – Collision
 Two or more records that result in the same address are known as
Synonyms.
 Hash Function
9

 A hash function is a mathematical function

that converts a numerical input value into
another compressed numerical value.
 The input to the hash function is of arbitrary
length but output is always of fixed length.
 Values returned by a hash function are called
message digest or simply hash values.

For Key, 100 → (100 % 10) = 0 (index)

Hash function
 Hashing - Example
10

 Let's take a simple example. First, we

start with a hash table array of strings
(Strings are used as the data being
stored and searched).
B
U
C
 Hash table size is 12 K
 Hash table is an array [0 to Max − 1] E
T
S
 Hashing - Hash function
11

 Next we need a hash function.

 There are many possible ways to construct a hash function.
 Let’s take a simple hash function that takes a string as input. The
returned hash value will be the sum of the ASCII characters that make
up the string mod the size of the table:

Hash
String ∑ASCII characters % table_size
Value

int hash (char *str, int table_size)

{
int sum = 0;
for( ; *str; str++) sum += *str; //sum of all characters
return sum % table_size;
}
 Example
12

 Let's store a string into the table:

"Steve".
 We run "Steve" through the hash
function, and find that
hash("Steve",12) yields 3:
 S:83 t:116 e:101 v:118
 83+116+101+118+101 = 519
 519 % 12 = 3

Steve ∑ascii character

3
of Steve
 Example
13

 Let's store a string into the table:

“Spark".
 We run “Spark" through the hash
function, and find that
hash(“Spark",12) yields 6:

Spark ∑ascii character

6
of Spark

 This method is known as “Division Hash Method”

 Key Terms used in Hashing
14

Key
Definition
Term
Hash Hash table is an array [0 to Max − 1]
Table of size Max
For better performance – keep table
size as prime number.
Hash A hash function is a mathematical
Functio function that maps an input value into
n an index / address.
(i.e. transforms a key into an address)

Bucket A bucket is an index position in a

hash table that can store more than one
record.
 When the same index is mapped with two keys, both the records are stored
in the same bucket - This is called as collision for bucket size 1.
 Alternative – Buckets with multiples sizes.
15
 Key Terms
16

 Probe - Each action of address

calculation and check for success
is called as a probe.
 Running “Spark" through the
hash function, and finding an
index 6 is a probe.

Spark ∑ascii character 6

of Spark
 Key Terms
17

 Collision - The result of two keys

hashing into the same address is
called collision.
 With bucket size =1

25 Key % Table_size 5
25 % 10

55 Key % Table_size
5
55 % 10
COLLISION
 Key Terms
18

 Synonym - Keys that hash to the same

address are called synonyms.
 For e.g. “25” and “55” are synonyms.
 “Alka” and “Abhay” are synonyms.
 Key Terms
19

 Overflow - The result of

 Many keys hashing to a single
address and
 Lack of room in the bucket is known
as an overflow.

 Collision and overflow are synonymous

when the bucket is of size 1.
 Key Terms
20

 Open / External Hashing- Allowing the records to be stored in

potentially unlimited space, it is called as open or external hashing.
 How to handle bucket with size 1 for unlimited space?
 Each bucket in the hash table is the head of a linked list.
 All elements that hash to a particular bucket are placed on that bucket’s
linked list.

Collisions
Key % 10 are stored
outside the
table.
 Application - Open / External Hashing
21

 Hashing for disk files is called external hashing.

 The target address space is made of buckets
 Each of which holds multiple files.
 A bucket is either one disk block or a cluster of contiguous disk

blocks.

Inode – Index node

A reference (index) about the
file and directory on the
System.

LINUX
 Key Terms
22

 Closed/ Internal Hashing- When we use fixed space for storage

eventually limiting the number of records to be stored, it is called
as closed or internal hashing.

How to handle multiple

records ?

Collisions result in
storing one of the
records at another
slot in the table.
Limits the table size.
 Key Terms used in Hashing
23

Key Term Definition

Perfect The hash function that transforms different keys into
Hash different addresses with NO Collisions is called a perfect
Function hash function.
The worth of a hash function depends on how well it avoids
collision.
Load The maximum storage capacity, i.e. the maximum number
density of records that can be accommodated, is called as loading
density.
Full Table All locations in the table are occupied.
(Based on the characteristics of hash function; a hash function
should not allow the table to get filled in more than 75%) – To
handle collisions.
 Key Terms
24

 LOAD FACTOR- the number of

records stored in a table divided by
the maximum capacity of the table.
 Expressed in terms of percentage.

Load Factor % = (# of records / Max) * 100

Load Factor = (2 / 10) *100 = 20%

 Key Terms
25

 RE-HASHING- Rehashing is with respect to closed hashing.

 When we try to store the record with Key1 at the bucket position
Hash(Key1) and find that it already holds a record, it is collision
situation.
 We can use a new hash function or the same hash function to
place the record with Key1.
OR
 If the table gets full, then build another table that is about
twice as big with an associated NEW hash function.
 The original table is scanned, and the elements are re-
inserted into the new table with new hash function.

Rehashing maintains reasonable Load factor

 Key Terms
26

 RE-HASHING- Example with same hash function

 Key Terms
27

 RE-HASHING- Example with different hash function

Consider table size as 7
Hash function Key % 7 • NEW Table size
Elements - 13, 15, 24, 14, 23, 19 17 (7*2=14 &
next prime is 17)
14 • New hash
If 19 is inserted; function = key %
table will be 85% 17
full & will affect Re-
the search • Old table is
hashing
performance. scanned and all
the elements are
inserted into new
After inserting 13, 15, 24, 14, 23 table.
 Issues in Hashing
28

 Need of good hashing function that minimizes the number

of collisions.
 Need of an efficient collision resolution strategy so as to
store or locate synonyms.
 Features of a good hash function
29

 Easy and quick to compute.

 Addresses generated from the key are uniformly and randomly
distributed.
 Small variations in the value of the key will cause large variations in
the record addresses to distribute records (with similar keys) evenly.
 The hashing function must minimize the occurrence of collision.
 The hash function should use all input data.
 The hash function should generate different hash values for similar
strings.
 The resultant index must be within the table index range.
 Methods for implementing hash
30
functions
1. Direct Hashing
2. Division method
3. Multiplication method
4. Extraction Method
5. Mid-square Hashing
6. Folding Technique
7. Rotation
8. Universal Hashing
 Direct hashing
31

 The key is the address without any algorithmic manipulation.

 It is limited and powerful as it guarantees that there are no synonyms
and therefore no collision.
 The data structure contains an
element for every possible key.
 Records are placed using their
key values directly as indexes.
 They facilitate fast searching,
insertion and deletion operations
in O(1) time.
Limitations:
 Large key value.
 Causes wastage of memory space if there is a significant difference
between total records and maximum value.
 Direct Hashing
32
 Division Hash method / modulo division method
33

 Key is divided by some number M, and the remainder is used as

the hash address of Key K.
Hash(Key) = Key % M
 This function gives the bucket addresses in the range of 0
through (M - 1); so the hash table should at least be of size M.
 The choice of M is critical.
 A good choice of M is that it should be a prime number greater
than 20.
 A uniform hash function is designed to distribute the keys
roughly evenly into the available positions within the hash table.
 Modulo-Division
34

 Modulo-Division Also known as

Division-remainder.
 Address = Key % Table size

 This algorithm works with any

table size, a list size that is a prime
number produces fewer collisions
than other list sizes.
 Multiplication Method
35

 Multiply the key ‘K’ by a constant A in the range 0<A<1 and

extract the fractional part of K * A.
 Then multiply this value by M and take the floor of the result.

 Hash(Key) =

 Where, K * A % 1 is the fractional part of K * A

 Donald Knuth suggested to use A = 0.61803398987

 Assuming M = 50, K = 107;

KA = 66.126
Hash (K) = Hash(107) = floor(M * (KA %1)) Taking fractional
part give 0.126
= floor(6.3) = 6 0.126*50 = 6.3

107 will be placed at index 6 in hash table.

 Multiplication Method – alternate method
36

 (Multiply every single digits in the key) % table_size

 Example –
 Hash(131135) for table size 10
 = (1 * 3 * 1 * 1 * 3 * 5) %10
 = 45 % 10
 =5
 Hash key for “Cat” on 10 buckets of size 1
 Hash(Cat) for table size 10 is Hash(67+97+116)
 = 280
 = (2 * 8 * 0 ) %10
 =0
 Digit Extraction Method
37

 When a portion of the key is used for address calculation, the

technique is called as the extraction method.
 A few digits are selected, extracted from the key and are used as
the address.
 For example - For 6 digits book accession number; we can have 3
digits address by selecting odd number digits – 1st, 3rd, and 5th digit.
 This address can be used as the address for the hash table.
 Very fast; but digits/characters distribution in keys may not be
even.
 Digit Extraction Method
38

 Another way is to extract the first two and the last one or two
digits.
 For example, for key 345678, the address is 3478 if the first two
and the last two digits are extracted or 348 if the first two and the
last digit are extracted.
 OR
 For 6-digit employee number get 3-digit hash address(000-999)
 Select the first, third. and fourth digits (from left) and use them
as the address.
 140145=101
 137456=174
 214562=456
 Mid-Square (middle of Square)
39

 The key is squared and the middle part of the result is extracted as
the hash value.
 For e.g. To map the key 3121 into a hash table of size 1000 , we
square it 3121= “9740641” and extract 406 as the hash value.

 Disadvantage-
 For large key, it is very difficult to store its square as it should

not exceed the storage limit.

 Preferred to be used when the key size ≤ 3 digits.
 Variation on the mid-square method
40

 Use fewer digits of the key for squaring.

 i.e. select a portion of the key, such as the middle three digits,
and then use them rather than the whole key.
 This allows the method to be used when the key is too large to
square.
 379452: 379 * 379 = 143641 = 364
 121267: 121 * 121 = 014641 = 464
 Works well if the keys
do not contain a lot of
leading or trailing zeros.
 Non-integer keys have
to be preprocessed to
obtain corresponding
integer values.
 Folding Method
41

 The key is partitioned into a number of parts, each of which has the
same size.
 The size of the subparts of the key is the same as that of the address.
 The parts are then added together, ignoring the final carry, to form
an address.
 For a key with digits, we can subdivide the digits into three parts,
add them up, and use the result as an address.
 Example: If key = 356942781 and address slots are of 3 digits.
 Part1 = 356, Part2 = 942, Part 3 = 781
 Add them to get the sum as 2079 → ignore the final carry.
 Hash value = 079
 Folding Method
42

 It involves splitting keys into two or more parts and

then combining the parts to form the hash addresses.

 To map the key 25936715 to a range between 0 and

9999 (i.e. 4 digit address), we can:
 split the number into two as 2593 and 6715 &
 Add these two to obtain 9308 as the hash value

 Very useful if we have keys that are very large.

 Types of folding method
43

There are 2 folding methods -

 Fold shift, the key value is divided
into parts whose size matches the
size of the required address. Then Offset
the left and right parts are shifted
and added with the middle part.

 Fold boundary, the left and right

numbers are folded on a fixed
boundary between them and the
center number.
 Universal Hashing
44

 N keys all of which hash to the same slot, yields an average

retrieval time of O(n).
 Fixed hash function is helpless for this worst-case behavior.
 Solution – Universal Hashing (choose the hash function
randomly)
 The main idea behind universal hashing is to select the hash
function at random at runtime from a carefully designed set of
functions.
 Because of randomization, the algorithm behaves differently on
each execution; even for the same input.
 This approach guarantees good average case performance, no
matter what keys are provided as input.
 Quiz
45

In a hash table of size 13 which index positions would the

following two keys map to?
27, 130
(A) 1, 10
(B) 13, 0
(C) 1, 0
(D) 2, 3
A hash table has space for 100 records. What is the probability of
collision before the table is 10% full?
(A) 0.45
(B) 0.5
(C) 0.3
(D) 0.34
 Quiz
46

A hash table has space for 100 records. What is the probability of
collision before the table is 10% full?
(A) 0.45
(B) 0.5
(C) 0.3
(D) 0.34

For the first time there will be no collision because all the slot is empty.
Now, once the first slot is filled, after then to fill the next key in the slot
there is chances of collision by 1/100.
For the next key, 2/100.
So 1/100 + 2/100+.............+9/100.
= 0.01+0.02+0.03+.......+0.08+0.09= 0.45
 Forms of Hashing - revisited
47

 There are 2 different forms of hashing

 Open hashing or external hashing
 Close hashing or internal hashing

 Open Hashing:
 It allows records to be stored in unlimited space (could be Hard Disk).
 It place no limitation on the size of the table.
 Close Hashing:
 It uses fixed space to store data.
 It limits the size of the table.
 Collision in Hashing - revisited
48

 When 2 values hash to the same

array location, this is called a
COLLISION
 A collision occurs when hashing
algorithm produced an address for
an insertion key and that address is
already occupied.
 Collisions are normally treated as
“first come, first served”—the first
value that hashes to the location
gets the location.
 What if the second and subsequent John Smith & Sandra Dee hash to
values hash to this same location ? the same location 02 - Collision
 Collision resolution strategies
49

 No hash function is perfect.

 If Hash(Key1) = Hash(Key2), then Key1 and Key2 are
synonyms and if bucket size is 1, we say that collision
has occurred.
 Need to store the record Key2 at some other location.
 Storing Key2 into another location known as
COLLISION RESOLUTION.
 Collision Resolution methods
50

Collision Resolution
Q
L u
P Linked
i a
Opens List
n d K Bucket
e
addressing (Separate
e r e
u chaining)
a a y
d
r t
o
P i O
r c f
R
o P f
a
b r s
n
Data CANNOT i o be Resolution
d
e
stored in then home b
o
t
g i
address or demanded m
n
address (i.e. collision)?
g
 Open addressing
51

 Collisions are resolved by finding an available empty location other than the
home address (original address).
 If Hash(Key) is not empty, the positions are probed in the following sequence
until an empty location is found.
 End of table ?
 The search is wrapped around to start and the search continues till the current collision
location.
 Open addressing resolve collisions in the primary area i.e. the area that contain
all of the home addresses.
 Large space is required for open addressing.
 There are 4 methods used in open addressing i.e.
 Linear probing
 Quadratic Probing
 Double hashing
 Key Offset
 Linear Probing
52

 A hash table in which a collision is resolved by putting the

item in the next empty place is called linear probing.
 This strategy looks for the next free location until it is
found.
 Function - ( Hash(x) + i ) MOD Max
 Where i = 1,2,3,4….till empty location is found
 Example insert 76, 93, 40,47,10 and 55 into hash table of
size 7.
53

 Initially hash table with size 7

 Key insertion method

 Hash Address = key % size_of_hashtable
 Function - ( Hash(x) + i ) MOD Max
Linear Probing Where i = 1,2,3,4,….

54

 Keys- 76, 93, 40, 47, 10, 55

Index Key
76 % 7 = 6 (FREE)
0 47
93 % 7 = 2 (FREE) 1 55
(Hash(47) + I ) % 7 2 93
40 % 7 = 5 (FREE) ( 5 + 1 ) % 7 = 6 (Occupied)
( 5 + 2 ) % 7 = 0 (FREE) 3 10
47 % 7 = 5
(OCCUPIED) 4

10 % 7 = 3 (FREE) 5 40
(Hash(55) + I ) % 7
( 6 + 1 ) % 7 = 0 (Occupied) 6 76
55 % 7 = 6
( 6 + 2 ) % 7 = 1 (FREE)
(OCCUPIED)
 Function - ( Hash(x) + i ) MOD Max
Linear Probing
55

 Keys- 76, 93, 40, 47, 10, 55

Index Key
76 % 7 = 6 (FREE)
0 47
93 % 7 = 2 (FREE) 1 55
(Hash(47) + i ) % 7 2 93
40 % 7 = 5 (FREE) ( 5 + 1 ) % 7 = 6 (Occupied)
( 5 + 2 ) % 7 = 0 (FREE) 3 10
47 % 7 = 5
(OCCUPIED) 4

10 % 7 = 3 (FREE) 5 40
(Hash(55) + i ) % 7
( 6 + 1 ) % 7 = 0 (Occupied) 6 76
55 % 7 = 6
( 6 + 2 ) % 7 = 1 (FREE)
(OCCUPIED)
 Function - ( Hash(x) + i ) MOD Max
Linear Probing
56
 Linear Probing
57

 Advantages:
 It quite simple to implement.

 Synonyms are stored nearer to the home address resulting in

faster searches.
 Disadvantages:
 Problem with linear probing is primary clustering.

 When many synonyms are clustered (i.e. mapped to the same

location) around the home address.
 High degree of clustering increases the number of probes for
locating data, increasing the average search time.
 The secondary clustering occurs when data is widely distributed
in the hash table and have formed clusters throughout the table.
 Linear Probing
58

 With Replacement:

 Without Replacement :
 Linear Probing – with replacement
59

 Address index is already occupied by the key?

 There are two possibilities –
 Either it is home address (collision)
 Or not key’s home address

 If the existing key’s actual address is different, then the NEW KEY

having the address of that slot is placed at that position; and

 The key with other address is placed in the next empty position.
 Linear Probing – with replacement
60

 Example
 Linear Probing – without replacement
61

 Address index is already occupied by the key?

 There are two possibilities –
 Either it is home address (collision)
 Or not key’s home address
 In both the cases; the without replacement strategy empty
position is searched for the key that is to be stored.
 Another empty location is searched for a new record.
 Linear Probing – Example
62

Store the following data into a hash table of size 10 and bucket size 1. Use linear
probing for collision resolution.
12, 01, 04, 03, 07, 08, 10, 02, 05, 14 Hashing function is key % 10

Linear probing with

replacement
 Linear Probing – with replacement and chaining
Chaining is linking the synonyms – for faster search
63

12, 01, 04, 03, 07, 08, 10, 02, 05, 14 Hashing function is key % 10
Index Key Chain Index Key Chain
0 10 -1 0 10 -1
1 1 -1 1 1 -1
Chain for
2 12 5 the key 2 2 12 6
3 3 -1 3 3 -1
4 4 -1
Add 4 4 9
key 5
5 2 -1 and 5 5 -1
6 -1 14 6 2 -1
7 7 -1 7 7 -1
8 8 -1 8 8 -1
9 -1 9 14 -1
 Linear Probing – Example
64

Store 12, 01, 04, 03, 07, 08, 10, 02, 05, 14 Hashing function is key % 10

Linear probing without replacement

 Linear Probing – Function
65

//hash function to get position //function for inserting a record using linear probe
int linear_prob(int Hashtable[], int key) {
int hash(int key)
int pos, i;
{ pos = Hash(Key);
return( key % MAX); if(Hashtable[pos] == 0) // empty slot
} {
Hashtable[pos] = key;
return pos;
}
Else { // slot is not empty
for(i = pos + 1; i % MAX != pos; i++) {
if(Hashtable[i] == 0) {
Hashtable[i] = key;
return i;
}
}//for
}//else
return -1;
}
 Question
66

 Suppose you are given the following set of keys to insert into a
hash table that holds exactly 11 values:
 113 , 117 , 97 , 100 , 114 , 108 , 116 , 105 , 99
 Which of the following best demonstrates the contents of the
has table after all the keys have been inserted using linear
probing?

 (A) 100, __, __, 113, 114, 105, 116, 117, 97, 108, 99
(B) 99, 100, __, 113, 114, __, 116, 117, 105, 97, 108
(C) 100, 113, 117, 97, 14, 108, 116, 105, 99, __, __
(D) 117, 114, 108, 116, 105, 99, __, __, 97, 100, 113
 Quadratic Probe
67

 It is a one way to reduced primary clustering.

 Add the offset as the square of the collision probe number.
 Quadratic probing operated by taking original hash value and
adding successive values of an arbitrary quadratic polynomial
to the starting value.
 Hash function = ( Hash(key) + i2 ) % M
 M = Table size or any prime number.
 i = integer number from 1 to (M-1)/2

As the offset added is NOT 1, quadratic probing SLOWS down the growth of
primary clusters.
 Function - ( Hash(x) + i2 ) % M
Quadratic Probing Where i = 1,2,3,4,…. (M-1)/2

68

 Keys- 22, 17, 32, 16, 5, 24

Index Key
22 % 7 = 1 (FREE)
0 24
17 % 7 = 3 (FREE) 1 22
2 16
32 % 7 = 4 (FREE)
3 17
16 % 7 = 2 (FREE) 4 32

5 % 7 = 5 (FREE) 5 5
(Hash(24) + i2 ) % 7
( 3 + 12 ) % 7 = 4 (Occupied) 6
24 % 7 = 3
( 3 + 22 ) % 7 = 0 (FREE)
(OCCUPIED)
 Example 
69
 Example 
70
 Quadratic Probe
71

 Disadvantages:
 Time required to square the probe number.
 Impossible to generate a new address for every element in the
list.
 Quadratic Probing – Function
72

//hash function to get position //function for inserting a record using quadratic probe
int quadratic_prob(int Hashtable[], int key) {
int hash(int key)
int pos, i;
{ pos = Hash(Key);
return( key % MAX); if(Hashtable[pos] == 0) // empty slot
} {
Hashtable[pos] = key;
return pos;
}
Else { // slot is not empty
for(i = 1; i % MAX != pos; i++){
pos = (pos + i * i ) % MAX;
if(Hashtable[pos] key == 0) {
Hashtable[pos] = key;
return pos;
}
}//for
} // Else return -1;
}
73

 Open Hashing
 Closed Hashing
 Open Addressing
 Linear Probing
 Quadratic Probing
 Primary and secondary clustering
74

 When many synonyms are clustered around the home address,

it is known as PRIMARY clustering.
 The SECONDARY clustering occurs when data is widely
distributed in the hash table and have formed clusters
throughout the table.
 High degree of clustering increases the number of probes for
locating data, increasing the average search time.
 Secondary clustering
75

 A related phenomenon, secondary clustering, occurs

more generally with open addressing modes including
linear probing and quadratic probing in which the probe
sequence is independent of the key, as well as in hash
chaining.

 A low-quality hash function may cause many keys to

hash to the same location, after which they all follow the
same probe sequence or are placed in the same hash chain
as each other, causing them to have slow access times.
 Elimination of Primary & Secondary
Clustering- DOUBLE HASHING
76

 All types of clustering can be eliminated by double hashing,

which involves the use of 2 hash function h1(key) and h2(key).
 One for accessing the home address (position) of a Key.
 The other for resolving the conflict.
 Sequence-

[ (Hash1(Key), (Hash1(Key) + i * Hash2(Key)), ….] % MAX

Where, i = 1, 2, 3, 4, …
 Pseudorandom collision resolution
77

 The last two method are collectively known as

double hashing
 Following rules are used for double hashing:
 Hash1(key) = key % M
 M is Hash_table_size
 Hash2(key) = R - (Key % R)
 R = any prime number < M
 Keys - 12, 01, 18, 56, 79, 49
Example


 Hash1 function – Key % 10

78

[ (Hash1(Key), (Hash1(Key) + i * Hash2(Key)), ….] % Index Key

MAX 0
12 % 10 = 2 (FREE) (Hash(49) = [Hash1(49) + 1 01
Hash2(49)] % 10
2 12
01 % 10 = 1 (FREE) (Hash2(49) = R – (Key % R) 3 49
= 7 – (Key % 7)
= 7 – (49% 7) 4
18 % 10 = 8 (FREE) =7–0=7 5
(Hash(49) 6 56
56 % 10 = 6 (FREE) = [Hash1(49) + Hash2(49)] % 10
= (9 + 7 ) % 10 = 6 (OCCUPIED) 7
79 % 10 = 9 (FREE) (Hash(49) 8 18
= [Hash1(49) + 2 * Hash2(49)] % 10 9 79
49 % 10 = 9 = (9 + 14 ) % 10 = 3 (FREE)
(OCCUPIED)
 Example
79

 Create a hash table for 37,90,45,22,17,49

 Hash table size =10
Index Value
0 90
1
Insert 37,90,45,22,49
2 22
3
Key % 10 4
5 45
6
7 37
8
9 49
80

Index Value
0 90
1
Insert 17
2 22
3
Key % 10
4
M-(key%M)
5 45
6
7 37
Insert 17 8
H1(17)=17%10 but it already occupied
9 49
 Calculate H2
81

 H2(key)=M-(key%M)
 H2(17)=7-(17%7)=7-3=4

 Hash(17) = (7 + 4)%10 = 1 Index Value

0 90
1 17
Insert 17
2 22
3
Key % 10
4
M-(key%M)
5 45
6
7 37
8
9 49
 example
82
83
 Linear Probing
84
 Quadratic Probing
85

Hash function = ( Hash(key) + i2 ) % M

 Double Hashing
86

[ (Hash1(Key), (Hash1(Key) + i * Hash2(Key)), ….] %

MAX
 Chaining – (Separate chaining)
87

 This technique is used to handle

synonym.
 It chains together all the records
that hash to the same address.
 A linked list of synonyms is
created whose head is home
address of synonyms.
 Pointers are handled to form a
chain of synonyms.
 The EXTRA memory is needed
for storing pointers.
 Separate Chaining

88

 The idea here is to resolve a collision by creating a linked list of

elements as shown below.
 Chaining Vs. Rehashing
89

Chaining Rehashing
Unlimited number of synonyms can A limited but good number of
be synonyms are taken care of.
handled.
Additional cost to be paid is an The table size is doubled but no
overhead of multiple linked lists. additional fields of links are to be
maintained.

Sequential search through the chain Searching is faster when compared to

takes more time. chaining.
 Open Addressing Vs. Closed Addressing
Closed Addressing Open Addressing
90
Records are stored in potentially Records are stored in fixed space is called
unlimited space – (open or external as closed or internal hashing.
hashing).
Each bucket in the hash table is the head The fixed storage space eventually limits
of a linked list. the number of records to be stored.
All elements that hash to a particular All elements that hash to a particular
bucket are placed on bucket’s linked list. bucket are re-probed or rehashed.
Collisions are stored outside the table. Collisions result in storing one of the
records at another slot in the table.
 Hash table overflow
91

 Collisions will occur !!

 An overflow is said to occur when a new identifier(key) is
mapped or hashed into a full bucket.
 With the bucket size as one, collision and overflow occur
simultaneously.
 Techniques for handling overflow of records –
 Overflow handling with Open Addressing
 On collision; find the closest unfilled bucket through linear probing or
linear open addressing
 Overflow handling with Chaining
 On collision, append new key in the bucket’s chain.
 Each chain has a head node.
 Hash table overflow – Linear probing revisited
92

1. Compute Hash(I)

2. Examine identifiers position

3. Table[Hash(I)], Table[Hash(I) + 1], …, Table[Hash[I]

+ i], in order until key is mapped to the index.

4. If we return to the start position Hash(I), then the

table is full and I is not in the table.
 Extendible Hashing
93

 On collisions, with linear probing or separate chaining; several

blocks are required to be examined to search a key.
 On table overflow/full; rehashing is needed.
 For fast searching and less disk access, EXTENDIBLE
hashing is used.
 It is a type of hash system, which treats a hash as a bit
string, and uses a trie (prefix or digital tree) for bucket
lookup.
 It minimizes Re-hashing.
 Widely used in databases.
 Extendible Hashing - Example
94

 Hash function Hash(Key) returns a binary number.

With bucket size as 1

No space for Key 3

First 2 most significant bits

 Extendible Hashing - Example
95

 Hash function Hash(Key) returns a binary number.

Global Local depth - 2 means 3 values (0, 1, 2)

depth – 2
right To add 9 ; binary value is 1001
most bits Take 2 right most bits i.e. 01

9
To add 20 ; binary value is 10100
Take 2 right most bits i.e. 00
In bucket, 00- local depth is 2 i.e.
overflow & global depth is also 2 –
then double the table ie.
000, 001, 010, ………………..111
DICTIONARY By: Aditya Solanki
Aditya Nair
Dictionary – Basic Information
 An Abstract Data Structure which stores data in
form of Key|Value pairs.
 Each Key has a Value associated/paired with it.
 A dictionary with duplicates is a dictionary which
Value
allows two or more (key, value) pairs with the
same key. Key

 For Example, your Aadhar card

Dictionary - Properties
 The Keys and Values in the Dictionary can be of
any data type :
 Dictionary - Implementation

 Dictionaries are built upon Hash Tables, and the keys in the key/value pairs are
stored in memory inside these hash tables at indexes which are determined by a
Hash Function.
 Now, we can be using Open Addressing or Separate Chaining Approach for the hash
table to implement our Dictionary.
 Open Addressing: (In case of Collision ) Put the key in some other index location
separate from the one returned to us by the hash function.
 Separate Chaining: (also Closed Addressing) In case of collision, uses Linked Lists to chain together
keys which result in the same Hash Values.

 The length of the chain of nodes corresponding to a bucket decides the complexity of separate
chained hash tables.
 Separate Chaining Advantages over Open Addressing :

• Collision resolution is simple and efficient.

• The hash table can hold more elements without the large performance
deterioration of open addressing (the load factor can be 1 or greater).
• The performance of chaining declines much more slowly than open
addressing.
• Deletion is easy—no special flag values are necessary.
• Table size need not be a prime number.
• The keys of the objects to be hashed need not be unique.

Some Disadvantages :
• It requires the implementation of a separate data structure for chains,

and a code to manage it.

• The main cost of chaining is the extra space required for the linked lists.
Dictionary as ADT

 A dictionary D supports the following operations:

 size(): It gives the number of elements in D
 isEmpty(): Returns true if D is empty
 elements(): Returns the elements of D
 keys(): Returns the keys of D
 search(k): Returns the position of the item to be searched if found. If not return null position
 searchAll(k): Returns the position of all items whose key matches with k
 insert(k, v): Inserts an item v with the key k into D
 delete(k): Deletes an item whose key matches with k from D
 deleteAll(k): Deletes all items whose key matches with k from D
Dictionary – ADT Operations
Insert(key, value) :
 Inserting an element e into the hash

table also requires computing hash

function on the element to determine
the bucket. After finding the
corresponding bucket it is similar to
inserting an element into a singly
linked list.
 If the elements in each chain are

maintained in either ascending or

descending order, then it will be less
expensive to perform all the
operations.
 Dictionary – ADT Operations
Search(key) :
Hash function of the element
that is to be searched should
be computed. Access the
bucket with corresponding
hash value and proceed to
search the chain of nodes
sequentially. If the element
is found, then search is
successful, else it is an
unsuccessful search.
 Dictionary – ADT Operations
Remove(key):
Removing an element e from
the hash table also requires
computing hash function on
the element to determine the
bucket. After finding the
corresponding bucket it is
similar to deleting an
element from a singly linked
list.
Dictionary – ADT Operations
 Display():
Dictionary – Time Complexity
 The length of the chain of nodes corresponding to a
bucket decides the complexity of separate chained hash
tables.
 Its best case complexity of search operation is O(1). The
worst case complexity is O(n). This occurs when all
the n elements are mapped to the same bucket and the
searched element is the last element in the chain
of n nodes.
Thank you.
 SKIP LIST
Can we search, insert or delete a node in a sorted linked list in better than O(n)?
Important Points:
● The worst case search time for sorted linked list is O(n) as we
can only linearly traverse list and cannon skip nodes while
searching.
● The idea is simple we create multiple layers in a sorted list so
that we can skip some nodes.
Skip List Fundamentals :
 A Skip list is a probabilistic data structure. The skip list is used to
score the sorted list of elements or data with linked list.
 It allows the process of the elements or data to view efficiently. In one
single step, it skips several element of entire list, that’s why it is
known as skip list.
 The skip list is the extended version of linked list. It allows user to
search, remove and insert the element very quickly.
 It consists of a base list that includes a set of elements which
maintains the link hierarchy of subsequent elements.
Skip List Structure:

Built in two layers: The lowest layer and Top layer.

The lowest layer of the skip list is a common sorted
linked list, and the top layer of skip list are like an
‘Express Line’ where the elements are skipped.
Skip List Operations:

1. Insertion Operation -
We will start from highest level in the list and compare key of next
node of the current node with the key to be inserted.
Key of next node is less than key to be inserted then we keep on
moving forward on the same level.
Key of next node is greater than the key to be inserted then we
store the pointer to current node i at update[i] and move one level
down and continue our search.
At the level 0, we will definitely find the position to insert given key.
Skip List: Insertion
Implementation (Pseudo Code):
Insert(list, searchKey)

local update[0...MaxLevel+1]

x := list -> header

for i := list -> level downto 0 do

while x -> forward[i] -> key forward[i]

update[i] := x

x := x -> forward[0]

lvl := randomLevel()

if lvl > list -> level then

for i := list -> level + 1 to lvl do

Implementation (contd.)

update[i] := list -> header

list -> level := lvl

x := makeNode(lvl, searchKey, value)

for i := 0 to level do

x -> forward[i] := update[i] -> forward[i]

update[i] -> forward[i] := x

Skip List Operation:

2. Searching Operation-
 Searching an element is very similar to approach for searching a spot for inserting an
element in Skip list. The basic idea is if –
 Key of next node is less than search key then we keep on moving forward on the same
level
 Key of next node is greater than the key to be inserted then we store the pointer to current
node i at update[i] and move one level down and continue our search.
 At the lowest level (0), if the element next to the rightmost element (update[0]) has key
equal to the search key, then we have found key otherwise failure.
Skip List Searching:
Implementation(Pseudo code):
Search(list, searchKey)
x := list -> header
-- loop invariant: x -> key level downto 0 do
while x -> forward[i] -> key forward[i]
x := x -> forward[0]
if x -> key = searchKey then return x -> value
else return failure
Skip List Operation:

3. Deletion Operation-
 Deletion of an element k is preceded by locating element in the Skip list
using above mentioned search algorithm.
 Once the element is located, rearrangement of pointers is done to remove
element form list just like we do in singly linked list.
We start from lowest level and do rearrangement
until element next to update[i] is not k.
After deletion of element there could be levels with no elements, so we will
remove these levels as well by decrementing the level of Skip list.
Skip List Deletion:
Implementation(Pseudo code):
Delete(list, searchKey)
local update[0..MaxLevel+1]
x := list -> header
for i := list -> level downto 0 do
while x -> forward[i] -> key forward[i]
update[i] := x
x := x -> forward[0]
Implementation(contd.):
if x -> key = searchKey then
for i := 0 to list -> level do
if update[i] -> forward[i] ≠ x then break
update[i] -> forward[i] := x -> forward[i]
free(x)
while list -> level > 0 and list -> header -> forward[list ->
level] = NIL do
list -> level := list -> level – 1
Asymptotic Analysis (Time Complexity):

Algorithms Average Case Worst Case

Insert O(logn) O(n)

Search O(logn) O(n)

Delete O(log n) O(n)

Space O(n) O(n logn)

Applications
● Skip list are used in distributed applications. In distributed systems, the nodes of
skip list represents the computer systems and pointers represent network
connection.
Lucene search engine uses skip lists to
search in logarithmic time.

It power applications world over, ranging from mobile devices to sites like Twitter, Apple
and Wikipedia.
Leveldb is a fast key-value storage library written at
Google that provides an ordered mapping which uses
skip lists.
backend database for Google Chrome .
Bitcoin Core and go-ethereum stores the blockchain
metadata using a Leveldb database.
Minecraft
Autodesk AutoCAD 2016
Thank You :)
 Dictionaries
129

 It is a collection of the forms (k, v) where k is the key and v is the

value associated with the key (equivalently, v is the value whose key
is k).
 An unordered collection of distinct elements.
 No two pairs in dictionary have the same key.
 Multiset is a set whose members are not necessarily distinct.

 Operations are performed on dictionary

 Determine whether dictionary is empty or not
 Determine the dictionary size.
 Find the pair with specific key.
 Insert pair into the dictionary.
 Delete the pair from dictionary.
 Cont..
130

 The word dictionary is a collection of pairs; each pair

comprises a word and its value.

 The value of the world include the meaning of the

world, the pronunciation, verbal nouns, and so on.

 Examples :
 Webster’s dictionary
 Telephone dictionary
 Dictionary ADT
131
 Hashing - Applications
132

 In compilers – (as symbol table) to keep track of declared

variables/functions/class/keywords, etc.
 Online spelling checking.
 Game playing programs – to store the moves made.
 In browser programs – for caching the web pages.
 Security – cryptography in form of hash functions.
 Password verifications
 Programming-
 HashSet and HashMap in Java
 Dict in Python
 Skip List
133

 A balanced tree is one of the most popular data structures used for
searching.
 One of the variants of balanced trees is the skip list.
 The skip list is a probabilistic data structure.
 Used by many search-based applications instead of balanced trees.
 A skip list stores the sorted data in the form of a linked list.
 Items are stored as a hierarchy of linked lists where each list links
increasingly sparse subsequences of the items.
 These supplementary lists result in an item search that is as efficient
as that of balanced binary search trees.
 Since each link of the sparser lists skips over many items of the full
list in one step, the list is called skip list.
 Skip List
134

 These forward links are added on the basis of the probability of the
element search.
 Hence, insert, search, and delete operations are performed in
logarithmic expected time.
 Skip list algorithms are simpler, faster, and use less space.
 Diagrammatic representation of a skip list-
135

 Skip List- representation, searching and operations-

insertion, removal. (refer attached ppt by student’s
group)