Tag Archives: hash

LRU Cache by hashmap and doubly-linked-list

LRU can be implemented by map and doubly-linked-list. The key idea is that: 1. Maintain a head and tail, which is not null initially, 2. In Node, we store both key and value, 3. Create pickUp and setHead functions. public class LRUCache { class Node { int key; int val; Node pre; Node next; public… Read More »

Consistent Hashing Algorithm

I’ve been thinking this problem for a long time. HashMap brings an amortized O(1) time for insertion/lookup data. But let’s say we do rehash when we have million records already. We can’t neglect this rehash process, and say it is amortized O(1) time. This will lead a remapping disaster to whole server. So, I found… Read More »

Cuckoo hashmap

Cuckoo hashmap is an improved hashmap. It uses the cuckoo bird habit to get rid of other bird’s egg if he found it. Accordingly, we define 2 hashtables. We can either put in table1 or table2. Assume we want to put a (key1, value1) in table1. But the hash-calculated position of (key1, value1) in table1… Read More »