A hash table is a structure that maps keys to values.
Let’s first understand the term hash.
Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects.
Some examples of how hashing is used in our lives include:
• University students are assigned a unique ID that is used to store and retrieve information about them.
• Libraries assign each book a unique number that is used to determine its shelf location.
In both these examples the students and books were hashed to a unique number.
A hash function is any function that maps a data set of an arbitrary size to a data set of a fixed size that falls into the hash table. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes.
The hash function should be able to get a unique hash for each element in the data set to prevent collisions.
Consider 4 books: “Harry Potter”, “War and Peace”, “Twilight”, and “Jane Eyre”. We have 13 positions in the shelf and want to assign each book a unique number that can be used to determine its exact position.
Our hash function will take the book title, sum its character values (a is 1 , b is 2,…, z is 26), and modulo with 13 to get a unique value for the position.
For our books we get:
Harry Potter: (8+1+…+18)%13=8
War and Peace: (23+1+..+5)%13=0
Jane Eyre: (10+1+…+ 5)%13=5
A hash table is a data structure that is used to store the hashes and their associated data.
The books in our example will be stored in the following way:
Now, if somebody asked for “Harry Potter”, we could just pass the title though our hash function and retrieve the position, without having to search for the book in the entire collection.
Each element is assigned a key (hash). The key can be used to find the desired element directly.
Hash tables don’t remember the order in which items are inserted. Thus, hash tables are not efficient at ordering or sorting data.