CREATE OWN LIBRARY
Hash Search
Back to ProgrammingDescription
Overview:
Hash Search: In hash search algorithm, a hash table is created which stores data in a key value pair. A given key is the search item. Each data has a unique index (also called hash code) generated by hashing the key by a hash function.
Collision:It is a situation where two distinct data has the same index. There are multiple collision resolution techniques in hashing such as chaining and open addressing. Here, we use linear probing open addressing technique to resolve a collison. If a collision occurs, we move sequentially in the hash table from collision location until an empty slot in the hash table is found.
Prerequisites:
● Hashing
Procedure:
Consider an hash table of size 5 with the following hash function
HashFunction(key) = key % size
We insert data into the hash table as shown in the figure below.
Let us consider the search key as 18. We get the index of the key using the function HashFunction(18) = 18 % 5 = 3. We check and find that the key is present in index 3 of the hash table and the search is successful.
Algorithm
Algorithm:
Input:
1. Key & Value pairs
Output:
1.Perform insert, search, display operation on Hash Table
Algo:
Step 1: Start
Step 2: Set size <= 5
Step 3: Define user defined datatype Data with int key &int value
Step 4:Defining hashFunction function
inthashFunction(int key)
Return (key mod size)
Step 5:Defining insert function
void insert(Data*hashTable[], int key, int value)
Set intidx <= Call hashFunction(key)
While (hashTable[idx] ≠ NULL) do
Display “idx =” idx
Set idx<=idx + 1
Set idx <= idx mod size
End While
Set hashTable[idx] <= GetNode(Data)
Set hashTable[idx].key <= key
Set hashTable[idx].value <= value
Step 6: Defining search function
void search(Data*hashTable[], int key)
Set int flag <= 0
Set intidx <= Call hashFunction(key)
While (hashTable[idx] ≠ NULL) do
Check if (hashTable[idx].key = key)
Set flag <= 1
Break
End If
Set idx <= idx + 1
Set idx <=idx mod size
End While
Check if (flag = 1)
Display “Data Found”
Display “Search Value:” hashTable[idx].value
Else
Display “Data Not Found”
End If
Step 7: Defining display function
void display(Data* hashTable[])
Display “Hash Table:”
fori = 0 to i< size repeat
Check if (hashTable[i] ≠ NULL)
Display hashTable[i].key “à” hashTable[i].value
Else
Display “null”
End If
Set ißi + 1
Step 8: Defining main function
Set int flag <= 1
Set intch <= null
Set int key <=null
Set int value <= null
Set Data* hashTable[size] <= null
While (flag) do
Display “1. Insert data into hash table”
Display “2. Search data”
Display “3. Display hash table”
Display “4. Exit”
Read ch
Switch(ch)
Case 1:
Display “Enter key value pair”
Read key
Read value
Call insert(hashTable, key, value)
Break
Case 2:
Display “Enter key”
Read key
Call search(hashTable, key)
Break
Case 3:
Call display(hashTable)
Break
Case 4:
Set flag <= 0
Break
Default:
Display “Wrong Choice”
End Switch
End While
Step 9: Stop
Code
Characteristics:
● Insertion, delete and update operation in a hash table require O(1) time.
● Linear probing collision resolution technique has been used.
● As the number of collisions increases, the complexity of the algorithm increases.
Application:
● In Internet search engines [link]
● Implementing password in a multi-user system. Hashing allows faster retrieval of passwords [link]
Advantage:
● Insertion, delete and update operation in a hash table require O(1) time complexity.
● Searching an element requires O(1) time complexity.
Disadvantage:
● The complexity of the algorithm increases with the increase in number of collisions.
Complexity:
Time Complexity:
Assuming no collisions, the time complexity of the algorithm is O(1), In the insert() function a single memory reference for each insertion. The search() function also requires a single memory reference. However, as the number of collisions increases, the complexity of the algorithm increases.
Space Complexity:
The algorithm requires a hash table as an extra space. Hence, the space complexity of the algorithm is O(n) where n is the size of the hash table.
