Unique identifiers such as IDs, passports, and school registration numbers are real-life examples of how hash tables work. This is where a unique identifier is used to retrieve all information about a person or an object in a particular context.
Hash tables are data structures that store elements in key-value pairs. Hash tables may be confused with Dictionaries since they also hold elements in key-value pairs.
The difference between the hash tables and dictionaries is that hash tables are non-generic collections while dictionaries are generic. Generic means that dictionaries store key-value pairs of specific data types while non-generic collection means that it stores key-value pairs of any data type.
Structure of Hash Tables
Hash tables contain:
-
Key: unique integers used for indexing values.
-
Value: data associated with the keys.
In some scenarios, the keys may be large and cannot be used directly as an index, this is where hashing comes in.
Hashing is the process of converting a key into another value. A hash function generates the new value according to a mathematical algorithm, which results in a hash.
A good hash function is one way where it cannot be converted to the original key.
Hash Collision
Hash collision is where two keys generate the same hash. This causes a conflict of what value to be stored.
This is resolved using the following techniques:
1. Collision resolution by chaining
If two keys generate the same hash, the elements are stored in the same index using a doubly-linked list.
2. Open Addressing
In this case, if two keys generate the same hash the element is stored in one key or left Nil.
Techniques involved in open addressing include:
-
Linear probing
-
Quadratic probing
-
Double hashing
Good Hash Functions
Good hash functions always reduce the probability of having many hash collisions.
They are implemented using the following methods:
-
Division method
-
Multiplication method
-
Universal hashing