Hash Table

Preview

1. How does a hash table work?
2. What is a hash function and how is it used in a hash table?
3. What are the advantages and disadvantages of using a hash table?
4. How does collision resolution work in a hash table?
5. How can you resize a hash table?

Explain

A hash table is a data structure that stores key-value pairs, in which an array of fixed size is used to store the data. When a value is stored in the hash table, a hash function is used to generate an index number, which is used to find the appropriate location in the array to store the data.

For example, let’s say we want to create a hash table to store the ages of a group of people. We could use their names as keys, and their ages as values.

To store the data, we would first define an array of a certain size, such as 10. We would then use a hash function to generate an index number for each name. The hash function might simply add up the ASCII values of the characters in the name, and then take the remainder of that sum when divided by 10 (since our array is of size 10).

So if we wanted to store the age of someone named “John”, the hash function might generate an index of 6. We would then store John’s age in the 6th location of the array.

To retrieve John’s age later on, we would use the same process - generate an index using the hash function (which would again be 6 for John’s name), and then retrieve the age stored at that location in the array.

Keypoint

1. Hash tables are a data structure that store data in key-value pairs.
2. They use a hash function to map the key to an index in an array.
3. This allows for fast retrieval of values based on their keys, with an average time complexity of O(1).
4. Collision resolution techniques such as chaining or open addressing must be used to handle situations where multiple keys map to the same index.
5. Hash tables can be used for a variety of applications, such as implementing dictionaries or counting occurrences of elements in a dataset.
6. They are commonly used in programming languages and databases to store and access large datasets efficiently.

Review

1. What is the difference between separate chaining and open addressing in hash tables?

Answer: Separate chaining involves creating linked lists at each index of the hash table to store any elements that hash to that index. Open addressing, on the other hand, involves probing for an empty slot in the hash table when a collision occurs, and then storing the element in that slot.

2. In a hash table with linear probing, what is the danger of having a low “load factor”?

Answer: A low load factor means that the hash table is not fully utilized, and there are many empty slots. In a hash table with linear probing, if all the elements are clustered towards one end of the table, it can lead to a phenomenon called clustering, where successive collisions are more likely to fall in the same cluster, making the hash table inefficient.

3. How does a hash table handle collisions?

Answer: When a hash table encounters a collision, it uses a collision resolution mechanism to resolve it. Common methods include separate chaining (keeping linked lists at each index), open addressing (probing for an empty slot), and double hashing (using a second hash function to compute a different index).

4. What is the time complexity of inserting an element in a hash table?

Answer: The time complexity of inserting an element in a hash table is O(1) on average, assuming a good choice of hash function and a low load factor. However, in the worst case of all elements hashing to the same index, the time complexity can be O(n), where n is the number of elements in the hash table.

5. What happens if two elements have the same hash code in a hash table?

Answer: If two elements have the same hash code in a hash table, then a collision occurs. This means that both elements are trying to be stored at the same index. The hash table uses a collision resolution mechanism to resolve this, such as separate chaining or open addressing, as mentioned earlier.