In data structures, hash tables and linked lists are often used together. If you’re familiar with Java, you’ll find that LinkedHashMap, a common container, also combines hash tables and linked lists. Follow me to find out how hash tables and linked lists work together and what sparks can come from them.

Let’s start with the question, how do you implement LRU caching using linked lists? If you are not familiar with LRU, you can read this article. Have you learned the page replacement algorithm?

We can maintain an ordered single linked list, where nodes closer to the end of the list are accessed earlier. When a new piece of data is accessed, we iterate sequentially, starting at the head of the list. The result of traversal is one of two cases.

  1. If the data has already been cached in the list, we iterate to the node that corresponds to the data, and then we move it from there to the head of the list.
  2. If the data is not in the list, there are two cases. If the cache is not full at this point, we simply insert the node into the list header. If the cache is full, we remove a node from the end of the list and insert a new data node into the head of the list.

Now that we have implemented an LRU cache with a linked list, let’s examine the time complexity of cache access. Because we need to go through the list whether the cache is full or not, the LRU cache based on the linked list implementation has a cache access time of O(n).

 

 

Is there any way to reduce the time complexity? Let’s first examine the common operations of caching. For a cache, there are three main operations:

  1. Adds an element to the cache.
  2. Removes an element from the cache.
  3. Look up an element in the cache.

 

All three operations involve a lookup operation, and the time complexity would be O(n) if only a linked list was used. We all know that hash table lookup is O(1), so can we combine hash table and linked list to reduce the time complexity of these three common operations in the cache to O(1)? The answer is yes, and let’s see how they fit together.

As shown in the figure, we use bidirectional linked list to store data. In addition to data, pre and next Pointers, a special field hNEXT is added for each node in the linked list. What does this HNEXT do? Because our hash table resolves hash collisions using the linked list method, each node will be in two chains. One chain is the bidirectional list we just mentioned, and the other chain is the zipper in the hash table. The precursor and successor Pointers are used to string nodes in the bidirectional list, and the hNext pointer is used to string nodes in the zip of the hash table.

Now that we have this combined hash table and bidirectional linked list structure, let’s look at how the three operations of the cache that we talked about before can be order one in time.

First, let’s look at how to find a piece of data. As we said earlier, the time to look up data in a hash table is close to O(1), so we can quickly find a data in the cache using a hash table. When the data is found, we need to move it to the end of the two-way list.

Next, let’s look at how to delete data. We need to find the node where the data is, and we need to delete the node. Using the hash table, we can find the node to delete in the O(1) time complexity. Because our linked list is a bidirectional linked list, the bidirectional linked list can obtain the precursor node through the time complexity of the precursor pointer O(1), so in the bidirectional linked list, the deletion of nodes only needs the time complexity of O(1).

Finally, let’s look at how to add data. Adding data to the cache is a bit cumbersome, we need to see if the data is already in the cache. If it is already there, move it to the head of the bidirectional list; If it’s not in there, you need to see if the cache is full. If it is full, delete the nodes at the end of the two-way list, and then put the data at the head of the list; If it’s not full, the data goes directly to the head of the list. All the lookups involved in this process can be done with a hash table.

Other operations, such as deleting header nodes and inserting data at the end of the list, can be done in O(1) time. So, the time complexity of all three operations is order one. So far, we have realized a prototype of an efficient cache system that supports LRU cache elimination algorithm by using a combination of hash tables and two-way linked lists.

Therefore, a time complexity of O(1) LRU cache can be implemented by combining hash table and linked list.

* For more hardcore knowledge, please follow the public account “Programmer Senior”.