Hash tables are a classic data structure that anyone who has written code should be familiar with. Every programming language has its own hash table implementation that’s ready to use out of the box. As a result, while many people have used hash tables, probably not many have implemented one themselves.

Designing a high-performance hash table actually requires considering quite a few details, such as how to handle hash collisions and how to handle hash table expansion. Some mature hash table implementations, like the one in the C++ standard library, have a large codebase and can be difficult to understand.

Fortunately, when implementing LRU Cache, LevelDB also implemented a simple and efficient hash table. The overall code is very concise - small but complete, making it very worth studying. Using LevelDB’s hash table implementation as an example, this article analyzes how to design a high-performance hash table.

Why LevelDB Implements Its Own Hash Table

The C++ standard library already has a hash table implementation, so why did LevelDB implement its own? Here’s what the official documentation says:

We provide our own simple hash table since it removes a whole bunch
of porting hacks and is also faster than some of the built-in hash
table implementations in some of the compiler/runtime combinations
we have tested. E.g., readrandom speeds up by ~5% over the g++
4.4.3’s builtin hashtable.

To summarize, other implementations can be cumbersome, while implementing their own version eliminates third-party dependencies and ensures both code simplicity and performance.

LevelDB Hash Table Implementation Principles

The hash table implementation here is similar to the one in the C++ standard library, using an array to store hash buckets. The average time complexity for insertion, lookup, and deletion operations is O(1) - first locate the specific hash bucket based on the key’s hash value, then perform the corresponding operation on the collision chain. Additionally, if the hash table’s load factor becomes too high during insertion, expansion occurs.

One thing to note is that since LevelDB’s hash table is used to implement LRU Cache, the element type here is LRUHandle. Besides having key and value fields, it also has a next_hash pointer that uses chaining to handle hash collisions. Additionally, it stores the hash value, which is typically generated by the caller and saved. This allows the hash value to be used directly in subsequent lookup, insertion, and deletion operations to locate the specific hash bucket. The other fields of LRUHandle are mainly used in LRU Cache and won’t be discussed here.

FindPointer Implementation

Let’s first look at the operation to find a specified key. LevelDB encapsulates a basic FindPointer() method that returns a double pointer to the key. Here’s the specific implementation:

1
2
3
4
5
6
7
8
9
10
// Return a pointer to slot that points to a cache entry that
// matches key/hash.  If there is no such cache entry, return a
// pointer to the trailing slot in the corresponding linked list.
LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = &list_[hash & (length_ - 1)];
  while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
    ptr = &(*ptr)->next_hash;
  }
  return ptr;
}

Here, it first locates the specific hash bucket based on the key’s hash value. If the bucket is empty, it directly returns the address pointing to the bucket’s nullptr head pointer. If the bucket is not empty, it uses the classic chaining method to handle hash collisions. It traverses the collision chain on the hash bucket, and if it finds the corresponding key, it returns a double pointer pointing to that node. If it traverses the entire list without finding it, it returns the address of the tail pointer.

The clever part here is that it returns a double pointer, allowing the method to be reused in lookup, insertion, and deletion operations. During lookup, directly dereferencing the returned pointer yields the target node. During insertion, this pointer can both check for existing nodes with the same key and directly insert new nodes at the correct position. During deletion, nodes can be removed directly by modifying the value this pointer points to, without needing to record the predecessor node.

Remove Operation

The Remove operation for deleting a key is implemented as follows:

1
2
3
4
5
6
7
8
9
LRUHandle* Remove(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = FindPointer(key, hash);
  LRUHandle* result = *ptr;
  if (result != nullptr) {
    *ptr = result->next_hash;
    --elems_;
  }
  return result;
}

Simple, right? To delete a specified node in a linked list, it first uses FindPointer to find the address of the pointer pointing to the list node, then assigns the address of the next node (result->next_hash) to the original pointer position, completing the deletion operation. This method returns the pointer to the deleted node, allowing the caller to handle subsequent processing (such as memory deallocation). This implementation approach doesn’t need to record the predecessor node, is simple and efficient, and can correctly handle the deletion of head nodes.

This deletion method can elegantly handle all of the following cases:

Case Description Initial State State After Deletion
1 Delete first node A list_[i] –> [A] –> [B] –> [C] –> nullptr list_[i] –> [B] –> [C] –> nullptr
2 Delete middle node B list_[i] –> [A] –> [B] –> [C] –> nullptr list_[i] –> [A] –> [C] –> nullptr
3 Delete last node C list_[i] –> [A] –> [B] –> [C] –> nullptr list_[i] –> [A] –> [B] –> nullptr
4 Delete only node A list_[i] –> [A] –> nullptr list_[i] –> nullptr
5 Key to delete doesn’t exist list_[i] –> [A] –> [B] –> nullptr list_[i] –> [A] –> [B] –> nullptr
6 Hash bucket is empty list_[i] –> nullptr list_[i] –> nullptr

Insert Operation

The Insert method for inserting nodes is similar to deletion, first finding the insertion position and then performing the insertion:

1
2
3
4
5
6
7
8
LRUHandle* Insert(LRUHandle* h) {
  LRUHandle** ptr = FindPointer(h->key(), h->hash);
  LRUHandle* old = *ptr;
  h->next_hash = (old == nullptr ? nullptr : old->next_hash);
  *ptr = h;
  // ...
  return old;
}

Line 4 here uses double pointers to handle all of the following cases at once (we’ll discuss double pointers in detail later):

Case Description Initial State State After Insertion Return Value
1 Insert into empty bucket list_[i] –> nullptr list_[i] –> [H] –> nullptr nullptr
2 Key exists (first node) list_[i] –> [A] –> [B] –> nullptr list_[i] –> [H] –> [B] –> nullptr A
3 Key exists (middle node) list_[i] –> [A] –> [B] –> [C] –> nullptr list_[i] –> [A] –> [H] –> [C] –> nullptr B
4 Key exists (last node) list_[i] –> [A] –> [B] –> nullptr list_[i] –> [A] –> [H] –> nullptr B
5 Insert new key (non-empty bucket) list_[i] –> [A] –> [B] –> nullptr list_[i] –> [A] –> [B] –> [H] –> nullptr nullptr

After insertion, it checks old to determine if this is a new node. If it is, it updates the hash table’s element count and checks if dynamic expansion is needed, which we’ll look at next.

Dynamic Expansion with High Load Factor

For a hash table with a fixed number of buckets, as more elements are inserted, the probability of hash collisions increases. In extreme cases, each key might have a long collision chain, causing hash table lookup and deletion performance to degrade. To measure the severity of hash collisions, we can define the load factor = number of hash table elements / number of hash buckets. Once this value exceeds a threshold, expansion is needed.

Earlier in the Insert method, when inserting elements, it tracks the current hash table element count. Once the load factor exceeds the threshold of 1, it calls Resize() to expand:

1
2
3
4
5
6
7
8
if (old == nullptr) {
    ++elems_;
    if (elems_ > length_) {
    // Since each cache entry is fairly large, we aim for a small
    // average linked list length (<= 1).
    Resize();
    }
}

The first problem to solve in expansion is deciding the new hash bucket count. Here’s LevelDB’s implementation:

1
2
3
4
5
6
7
void Resize() {
    uint32_t new_length = 4;
    while (new_length < elems_) {
      new_length *= 2;
    }
    //...
}

The standard library’s vector also chooses to expand by powers of 2. If the expansion factor is too large, it might waste too much space; if too small, it might cause frequent expansions. In practice, 2 is generally chosen as the expansion factor.

After deciding the new bucket size, it first creates the larger capacity hash buckets, then traverses all old hash buckets, and for each bucket, traverses the collision chain for each key, inserting each key into the new list. Here’s the core implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Resize() {
    // ...
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, 0, sizeof(new_list[0]) * new_length);
    uint32_t count = 0;
    for (uint32_t i = 0; i < length_; i++) {
      LRUHandle* h = list_[i];
      while (h != nullptr) {
        LRUHandle* next = h->next_hash;
        // Head insertion into new hash table
        h = next;
        count++;
      }
    }
    assert(elems_ == count);
    delete[] list_;
    list_ = new_list;
    length_ = new_length;
}

During Resize, each time a key is successfully added to the new hash table, it updates the hash table’s element count. Later, it uses an assert statement to check if the element count is correct after expansion. After all keys are inserted into the new hash table, it can reclaim the old hash table’s memory, then replace list_ with the new hash table and update the hash table capacity.

We skipped the critical insertion logic earlier - in the while loop, it traverses each key in the old hash table’s collision chain, then uses head insertion to insert into the new hash table. Let’s look at the head insertion implementation in detail.

Optimizing List Insertion with Head Insertion

Here’s the core code for head insertion that was omitted from Resize earlier:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 void Resize() {
    // ...
    for (uint32_t i = 0; i < length_; i++) {
      LRUHandle* h = list_[i];
      while (h != nullptr) {
        // ... 
        uint32_t hash = h->hash;
        LRUHandle** ptr = &new_list[hash & (new_length - 1)];
        h->next_hash = *ptr;
        *ptr = h;
        // ...
      }
    }
    // ...
  }
};

The core idea of head insertion is: insert new nodes at the head of the list. Suppose the original list is:

1
list_[i] --> [A] --> [B] --> [C] --> nullptr

The rehashing process will handle nodes A, B, C in sequence, inserting them into the new hash table. If nodes A and B are still in the same bucket in the new hash table, the list state after rehashing will be:

1
2
new_list[hash_a] --> [B] --> [A] --> nullptr
new_list[hash_c] --> [C] -->nullptr

Here A and B are still in the same bucket in the new list, but their order is reversed. Compared to traditional insertion that traverses to the list tail, head insertion is simpler, only needing to insert at the head without traversing to the tail, so the operation time complexity is O(1). Additionally, using head insertion doesn’t require maintaining a tail pointer, making it more space efficient. Furthermore, head insertion has cache locality benefits - recently inserted nodes are at the head of the list, improving lookup efficiency for certain access patterns.

Understanding Double Pointers in C++

The linked list operation code is very concise, without various complex conditional checks, thanks to the good use of double pointers. So how should we understand double pointers in C++? In C++, objects have values and corresponding memory addresses, pointers store object memory addresses, and double pointers store pointer addresses.

Let’s look at a clearer example. Suppose a bucket has a collision chain bucket->A->B->nullptr, which can be represented by this C++ code:

1
2
3
4
LRUHandle *node_a;    // Address: 0x100, Data: {value: "A", next_hash: 0x200}
LRUHandle *node_b;    // Address: 0x200, Data: {value: "B", next_hash: nullptr}
node_a->next_hash = node_b;
LRUHandle* bucket = node_a;   // Address: 0x300, Data: 0x100

Of course, the specific memory address values here are just for understanding - the actual runtime memory addresses will be different. Now there’s a new node node_h with address 0x500. To insert this node into the above list using head insertion, the core code is just 3 lines:

1
2
3
LRUHandle** ptr = &new_list[hash & (new_length - 1)];
h->next_hash = *ptr;    
*ptr = h;

Let’s look at the changes from each line. After the first line executes, the overall memory layout is:

Variable Name Memory Address Stored Value
ptr 0x400 0x300
bucket 0x300 0x100
node_a 0x100 {value: “A”, next_hash: 0x200}
node_b 0x200 {value: “B”, next_hash: nullptr}

Then executing h->next_hash = *ptr points node_h’s next_hash to *ptr, where *ptr gets A’s address. The overall memory layout becomes:

Variable Name Memory Address Stored Value
ptr 0x400 0x300
bucket 0x300 0x100 (*ptr)
node_h 0x500 {value: “H”, next_hash: 0x100}
node_a 0x100 {value: “A”, next_hash: 0x200}
node_b 0x200 {value: “B”, next_hash: nullptr}

At this point we’ve built the H->A->B->nullptr chain. But bucket still points to A, so we need to execute *ptr = h to make bucket point to node_h’s address. After this step, the overall memory layout becomes:

Variable Name Memory Address Stored Value
ptr 0x400 0x300
bucket 0x300 0x500
node_h 0x500 {value: “H”, next_hash: 0x100}
node_a 0x100 {value: “A”, next_hash: 0x200}
node_b 0x200 {value: “B”, next_hash: nullptr}

With this, we’ve completed building p->bucket->H->A->B->nullptr.

Summary

We’ve analyzed LevelDB’s hash table implementation in detail. Here are the key points for designing a high-performance hash table:

  1. Clever Use of Double Pointers - By returning a pointer to the node pointer, the FindPointer method can be reused in lookup, insertion, and deletion operations, greatly simplifying linked list operation code.

  2. Efficient Collision Handling - Uses chaining to handle hash collisions and optimizes list insertion with head insertion, avoiding the overhead of traversing to the list tail.

  3. Dynamic Expansion Mechanism - Monitors the load factor and expands by a factor of 2 at appropriate times, balancing space utilization and performance.

  4. Concise and Elegant Implementation - The entire implementation has minimal code but includes all core hash table functionality, making it an excellent learning example.

While this implementation is primarily used for LevelDB’s LRU Cache, many of its design principles are valuable references for implementing other high-performance data structures. In particular, the use of double pointers demonstrates the power of pointers in C++.