Hash Table

Hash Table is a data structure which organizes data using hash functions in order to support quick insertion and search.

There are two different kinds of hash tables: hash set and hash map.

1. The hash set is one of the implementations of a set data structure to store no repeated values.
2. The hash map is one of the implementations of a map data structure to store (key, value) pairs.

HashMaps use a hash function to determine where to store the value.
Identical keys will point to the same value.

HashMap methods:

1. put(): Used to store data in the HashMap

hashMap.put("1","John");

1. get(): Used to retrieve data from the HashMap

hashMap.get("1");

HashFunction:
Hash function uses the key to create a hash value which is used to determine where the data will be stored.

If result of two hash keys are hashed to the same index, then collision occurs.

Consider the below hash function which will create the hash value based on the starting letter:

Here, as key ant is hashed to index 0, the collision occurs.

There are two ways to resolve collision:

1. Linear Probing: When collision occurs, the data is assigned to the next available slot in the table. The drawback of linear probing is that it will cluster the data. For lookup, insert and delete operations, it will take O(n).

1. Separate Chaining: Here the hashtable is an array of pointers to the linked list. For lookup, insert and delete operations, it will take O(n/k).