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 »
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 »
b, base p, prime hash(ABC) = (A * b^3 + B * b^2 + C * b) % p hash(ABCD) = (A * b^4 + B * b^3 + C * b^2 + D * b) % p = ([hash(ABC) + D] * b) % p hash(BCD) = (B * b^3 + C * b^2… Read More »
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 »