UNIT V
HASHING & ALGORITHM ANALYSIS
Different hashing techniques, address calculation techniques, common hashing
functions, Collision resolution, rehashing
Dynamic Programming : Traveling Salesperson Problem (TSP), Backtracking: The
8 –Queens Problem, Branch and Bound: TSP
-------------------------------------------------------------------------------------------
Hashing
It is the process of storing and retrieving data from the database in the orfer of 1
time.
That is, storing and retrieving happens in a constant time,
It is also referred to as mapping process.
It is the process of mapping larger values to smaller values with the help of a
process called as hashing.
Terminologies used in hashing are,
Search Key – Search keys are keys using which the data can be searched.
For example : Student’s register number. A student possess multiple data such as
register number, name, address, parent name, date of birth, degree, marks, higher
secondary school details, marks, High school details and marks etc.,
Such long details cannot be stored in hash table but are stored in database.
These data can be easily searched using a search key – register number.
The search key is stored in hash table.
Hash Table – Hash table is a data structure that provides provisions like an array to
store data.
It consists of search keys that helps in searching data faster.
Hash table has indices similar to an array.
Hash Function – There are different methods of Hash function like K mod 10, K
mod n, Mid Square, Folding Method etc.
0 91
, Search Key ( 24,52,91,67,48,83)
1
2 52
3
4 24
5
6
7 67
8
9
Find out the hash value using K mod n hashing function.
Take the first value,
24 : K mod 10 = 24 mod 10 = 4
52 : K mod 10 = 52 mod 10 = 2
91: K mod 10 = 91 mod 10 = 1
67: K mod 10 = 67 mode 10 = 7
48 : K mod 10 = 48 mode 10 = 8
Different Hashing Techniques
1) Direct Hashing
2) Module Division Hashing
3) Mid-Square Hashing
4) Folding Hashing - Fold Shift hashing , Fold boundary hashing
5) Pseudo Random Hashing
6) Subtraction Hashing
Collision Resolution Technique
Creating a hash table for values
(24, 19,32,44)
Step 1: Create a hash table (if hash function K mod 6 is used)
That is, if K mod n hash function is used, hash table need to be created for n-1
index.
HASHING & ALGORITHM ANALYSIS
Different hashing techniques, address calculation techniques, common hashing
functions, Collision resolution, rehashing
Dynamic Programming : Traveling Salesperson Problem (TSP), Backtracking: The
8 –Queens Problem, Branch and Bound: TSP
-------------------------------------------------------------------------------------------
Hashing
It is the process of storing and retrieving data from the database in the orfer of 1
time.
That is, storing and retrieving happens in a constant time,
It is also referred to as mapping process.
It is the process of mapping larger values to smaller values with the help of a
process called as hashing.
Terminologies used in hashing are,
Search Key – Search keys are keys using which the data can be searched.
For example : Student’s register number. A student possess multiple data such as
register number, name, address, parent name, date of birth, degree, marks, higher
secondary school details, marks, High school details and marks etc.,
Such long details cannot be stored in hash table but are stored in database.
These data can be easily searched using a search key – register number.
The search key is stored in hash table.
Hash Table – Hash table is a data structure that provides provisions like an array to
store data.
It consists of search keys that helps in searching data faster.
Hash table has indices similar to an array.
Hash Function – There are different methods of Hash function like K mod 10, K
mod n, Mid Square, Folding Method etc.
0 91
, Search Key ( 24,52,91,67,48,83)
1
2 52
3
4 24
5
6
7 67
8
9
Find out the hash value using K mod n hashing function.
Take the first value,
24 : K mod 10 = 24 mod 10 = 4
52 : K mod 10 = 52 mod 10 = 2
91: K mod 10 = 91 mod 10 = 1
67: K mod 10 = 67 mode 10 = 7
48 : K mod 10 = 48 mode 10 = 8
Different Hashing Techniques
1) Direct Hashing
2) Module Division Hashing
3) Mid-Square Hashing
4) Folding Hashing - Fold Shift hashing , Fold boundary hashing
5) Pseudo Random Hashing
6) Subtraction Hashing
Collision Resolution Technique
Creating a hash table for values
(24, 19,32,44)
Step 1: Create a hash table (if hash function K mod 6 is used)
That is, if K mod n hash function is used, hash table need to be created for n-1
index.
