Hash table: An old classic data structure

The Hash table is an ancient data structure implemented using the chaining method in 1953. It allows direct retrieval of values based on keys.

The Hash table is one of computer science's most important data structures. This is not only because it has excellent read and write performance of O(1) but also because it provides a mapping between keys and values. Two key points need to be considered to implement a high-performance hash table: the hash function and the collision resolution method.

Hash Function

The key point in implementing a hash table lies in selecting the hash function. The choice of the hash function largely determines the read and write performance of the hash table. Ideally, a hash function should map different keys to different indices, which requires the output range of the hash function to be larger than the input range. However, since the number of keys can be much larger than the range of mapping, it is impossible to achieve this ideal effect in practical use.

A more practical approach is to make the hash function’s results distribute as evenly as possible and then solve the problem of hash collisions through engineering means. The result of the hash function mapping must be as evenly distributed as possible. An uneven hash function will lead to more hash collisions and poorer read and write performance.

If a hash function with a relatively uniform result distribution is used, the time complexity of hash operations such as insertion, deletion, and search will be O(1). However, if the result distribution of the hash function is uneven, the time complexity of all operations may reach O(n). Therefore, it is crucial to use a good hash function.

Collision Resolution

As mentioned earlier, in most cases, the input range of the hash function will be much larger than the output range, so collisions will occur when using a hash table, even if a perfect hash function is used. However, most hash functions are not perfect enough, so the possibility of hash collisions still exists. In such cases, methods are needed to resolve hash collisions, and the common methods are open addressing and chaining.

It is important to note that the hash collision mentioned here does not mean that multiple keys have exactly the same hash. It could be that some parts of the hash values for multiple keys are the same, for example, the first four bytes of the hash for two keys are the same.

Open Addressing

Open addressing is a method to resolve hash collisions in a hash table. The core idea of this method is to sequentially probe and compare elements in the array to determine whether the target key-value pair exists in the hash table. If we use open addressing to implement a hash table, the underlying data structure of the hash table will be an array. However, because the length of the array is limited when writing the key-value pair to the hash table, it will start traversing from the following index:

index := hash("author") % array.len

When writing new data to the current hash table and a collision occurs, the key-value pair will be written to the next available position in the index:

As shown in the above diagram, when Key3 collides with the two key-value pairs Key1 and Key2 already stored in the hash table, Key3 will be written to the next available position after Key2. When we want to retrieve the value corresponding to Key3, we first calculate the hash of the key and take the modulus, which helps us find Key1. After finding Key1, if it does not match Key3, we continue searching for the next element until we find an empty memory or the target element.

When searching for the value corresponding to a key, the array is linearly probed starting from the index position. Finding the target key-value pair or an empty memory indicates the end of the search operation.

The maximum impact on performance in open addressing is the load factor, which is the ratio of the number of elements to the size of the array. As the load factor increases, the average time for linear probing gradually increases, affecting the read and write performance of the hash table. When the load factor exceeds 70%, the performance of the hash table sharply declines, and once the load factor reaches 100%, the entire hash table becomes completely ineffective. At this point, the time complexity of searching and inserting any element becomes O(n) because all elements in the array need to be traversed. Therefore, it is important to pay attention to changes in the load factor when implementing a hash table.

Chaining

Compared to open addressing, chaining is the most common implementation method for hash tables, and most programming languages use chaining to implement hash tables. It is slightly more complex than open addressing, but it has a shorter average search length, and the memory used for storing nodes can be dynamically allocated, saving a significant amount of storage space.

To implement chaining, an array combined with linked lists is usually used. However, some programming languages introduce red-black trees in the hash table based on chaining to optimize performance. Chaining uses an array of linked lists as the underlying data structure for the hash table, which can be seen as an expandable two-dimensional array:

As shown in the above diagram, when we need to write a key-value pair (Key5, Value5) to the hash table, the key Key5 will first go through a hash function, and the hash returned by the hash function will help us select a bucket. Similar to open addressing, the bucket is selected by directly taking the modulus of the hash result:

After selecting bucket 7, we can traverse the linked list in the current bucket. During the traversal of the linked list, we will encounter the following two situations:

1. Find a key-value pair with the same key — update the corresponding value.
2. No key-value pair with the same key is found — append the new key-value pair to the end of the linked list.

To retrieve the value corresponding to a key in the hash table, the following process is followed:

Key6 demonstrates an example where a key does not exist in the hash table. When the hash table finds that it hits bucket 5, it will sequentially traverse the linked list in the bucket. However, even after traversing to the end of the linked list, the desired key is not found, indicating that the hash table does not have a corresponding value for that key.

In a well-performing hash table, each bucket should contain 0 to 1 elements, and sometimes 2 to 3 elements, but rarely more than that. The main costs of read and write operations in the hash table are the three processes of calculating the hash, locating the bucket, and traversing the linked list. The hash implemented using chaining also has the concept of a load factor:

Like open addressing, a higher load factor in chaining leads to poorer read and write performance of the hash table. Generally, the load factor of a hash table using chaining does not exceed 1. When the load factor of a hash table is high, hash table resizing is triggered to create more buckets to store elements, ensuring that performance does not significantly degrade. If a hash table with 1000 buckets stores 10000 key-value pairs, its performance is 1/10 of storing 1000 key-value pairs, but still 1000 times better than directly reading and writing in a linked list.

Summary

This article explains the basic working principle of Hash table. Hashtable is a fundamental data structure that can provide fast key-value mapping and has good read-write performance. The performance of the hash table mainly depends on two key points: the choice of hash function and the conflict resolution method.

There are still many engineering problems that have not been answered, such as the performance of the hash function, how to dynamically expand and shrink capacity in hashing, and optimizing bucket performance based on red-black tree, etc., these are all engineering issues that do not affect our understanding of hashtable’s working principles.

In the next article, we will delve into the Go language map design and implementation based on basic knowledge about the Hash table.