Hash table is a data structure, it maps keys to values for a highly efficient look up. In other words, it is a technique using which we can identify a specific element from a group of similar elements.
Insertion, deletion and retrieval occur in constant time (In the best case scenario).
If we want to assign a key to an object to make searching easy, we can make use of array like data structure where keys can be directly used as an index to store values. However, in cases where keys are large and cannot be used directly as index, we should use hashing algorithm (or) hashing function, which is nothing but a calculation applied to this key in order to generate the index number.
A hash table of key/value pair can be referred to as hash map. For example, Ada and DOB are the properties in an object, where, Ada is the key used for identifying the index and DOB is the value.
Collisions
Sometimes, A hash function may generate same index number to two different keys which will result in collision(s). This can be resolved in the following ways.
1.Open addressing: In open addressing technique, we resolve the collision by placing an item somewhere other than its calculated address.
– One common technique is “Linear probing”.
– Another technique is to make the hash table bigger than needed.
2.Closed addressing: In closed addressing technique, we use an array of linked lists to resolve collisions. However, fetching an item is not as quick as open addressing.
Summary
1. Hash table is used to index large amounts of data.
2. Address of each key is calculated by the key itself.
3. Collisions are resolved with open/close addressing.
4. Hashing is widely used in database indexing, compiles cacheing, password authentication and more.
5. Insertion, deletion and retrieval occur in constant time (In best case scenario).
References:
1. https://www.youtube.com/watch?v=KyUTuwz_b7Q
2. https://www.youtube.com/watch?v=mFY0J5W8Udk
sachidanandanaik 