What is Hash Table?
A hash table is a type of data structure that employs a particular function known as a hash function to map a given value to a key in order to retrieve elements more quickly.
A hash table is a data structure that stores information with two major components: key and value. With the help of an associative array, a hash table can be created. The effectiveness of the hash function used for mapping is determined by the efficiency of the hash function used for mapping.
For example, if the key value is John and the value is the phone number, we may use the following hash function to pass the key value:
index = hash(key);
The index is returned when the key is passed to the hash function.
Hash(john) = 3;
The john is added to the index 3 in the example above.
Drawback of Hash function.
- A Hash function assigns a unique key to each value.
- A collision can occur when a hash table has an inaccurate hash function, which generates the same key with two different values.
Hashing
- One of the searching techniques that requires a constant time is hashing. Hashing has an O time complexity (1). We've gone through the two types of search strategies so far: linear search and binary search.
- In linear search, the worst time complexity is O(n), whereas in binary search, it's O(logn).
- The quantity of components affects the search in both strategies, but we want a technique that takes a consistent amount of time. As a result, the hashing technique was developed, which gives a constant time.
- The hash table and hash function are employed in the hashing technique. We can calculate the address at which the value can be stored using the hash function.
- Index = hash(key)
The hash function can be calculated in three different ways:
- Method of division.
- Method of folding.
- The procedure of the middle square.
The hash function can be defined as follows in the division method:
h(ki) = k%m;
where m is the hash table's size.
If the key value is 6 and the hash table size is 10, for example. When we use the hash function on key 6, we get the following index:
h(6) =6%10 = 6
The value is kept at index 6, which is 6.
