What are Hash Tables

Hash Tables are data structures that store data in the form of key value pairs.

Hash Tables are abstract data structures since they internally use Arrays for their implementation.

Hash Tables aim to perform the main data structure operations - insert, lookup, and delete - in constant time O(1).

Describe the structure of Hash Tables

Hash Tables are data structures that store data in the form of key value pairs.

Hash Tables internally use Arrays for their implementation.

Keys are converted into integers using a hash function, and these hashed keys are represented by the indices of the Array. Values are stored as elements of the Array at indices that equals the corresponding hashed key.

Look-ups by key on the Hash Table are performed by hashing the key and then retrieving the element of the Array at the index that equals the hashed key.

What is the role of a hash function in the implementation of Hash Tables?

Hash functions convert the key which could be a primitive data type (int, char, boolean, float, ...), Strings, or any Object type into a 32 bit int.

This converted int is used as the Array index at which the corresponding value is put.

When the value for a key has to be retrieved from the Hash Table, the key is converted into int using the same hash function, and then the value is retrieved by retrieving the element of the array at the index equal to the hashed key.

What are some common hashing techniques used the implementation of Hash Tables?

Following are some common hashing techniques used in the implementation of Hash Tables.

Division (Modulus):Hash code is generated by dividing the key by a prime number, which is also usually the size of the Array, and using the remainder as the hash code.

h(k) = k % m
Where h(k) is the hash code, k is the key, m is size of array

Multiplication: h(k)=⌊m(kAmod1)⌋

What do you understand by collision in Hash Tables?

Collisions happen in Hash Tables when two or more different keys result in the same int after going through the hash function. Hence these keys point to the same array index.

How do you resolve collisions in Hash Tables?

Collisions in Hash Tables can be resolved using following different techniques.

Open addressing

• Linear Probing
• Double Hashing
• Quadratic probing

Separate Chaining

What is load factor in Hash Tables?

Load Factor is the ratio between the number of elements present in the Hash Table to the size of Hash Table.

What is dynamic resizing in Hash Tables?

Dynamic resizing is the ability of the Hash Table to expand or contract based on the number of elements in the Hash Table.