Hash Table is a Data Structure which is used to store data in the form of key-value pairs. It uses a hash function to calculate the index to the array where data is stored. The process of mapping keys to indexes is called hashing which is done by the hash function. Hash Tables are used for easy insertion and accessing of data.
We can see that through a hash function key maps to an index of the array which contains data stored. This process is called hashing. Let’s discuss all these terms in detail.
It is a function which takes a key and converts it into a hash value is called a hash function. There can be many implementations of hash function depending on the key we have and values stored. The value generated by a hash function is called a Hash Value or Hash code.
It is the process of converting keys in a hash table to an integer using the hash function which is used to store or retrieve data from the array.
Characteristics Of A Good Hashing Technique
- Hash Function should be simple: It should not be a complicated algorithm.
- Uniform Distribution of values: The hashing mechanism should provide a uniform distribution of values in the hash table and should not result in clustering.
- Less Collision: Collision happens when two keys result in the same hash value by the hash function. Though collision is bound to occur. There are various ways to resolve collision with collision resolution techniques.
Applications of Hash Table
- File System: It is used for mapping the file name to the path of the file which makes it easy to search a file using filename.
- Password Verification: When a password is entered on a website, a hash of the password is computed on the client-side which is then sent to the server through the network. At the server, the hash code is matched and the password is verified. This is done to avoid sniffing.
- Compiler Operation: To identify the keywords in a programming language, the compiler uses the hash table to store these keywords and other identifiers to compile the program.
- Algorithms: There are various algorithms such as the Rabin-Karp Algorithm which uses a hash table.