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 »

Rolling hash. O(1) time to compute queue’s hash

The key idea of rolling hash is to generate hash of n+1 elements in O(1) time, by knowing hash of n elements. Here is a great introduction for rolling hash from TopCoder: https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-string-searching-algorithms/ And here is an application for checking palindrome in a stream rolling hash from g4g: http://www.geeksforgeeks.org/online-algorithm-for-checking-palindrome-in-a-stream/ They are great, and it supports… 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 »