In hashing, large keys are converted into small keys by using hash functions and values are then stored in a data structure called hash table. The idea of hashing is to distribute key-value pairs uniformly across Hash Table using Hash function.
- A hash function can be used to map a data set of an arbitrary size to a data set of a fixed size to store into the hash table.
- Each element is assigned a key and via which you can access the element in O(1) average time complexity. It provides constant time search, insert and delete operations on average. This is why hashing is one of the most used data structure for solving Interview problems.
- To learn hashing technique, It is important to have understanding of good hash functions and collision resolution techniques.
- There are mainly two methods to handle collision:
- Separate Chaining
- Open Addressing