Created
June 6, 2015 20:03
-
-
Save rootid/d45ead4707e6eaa7a368 to your computer and use it in GitHub Desktop.
LRU cache design with DLL and HashMap
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class LRUCache { | |
| //Keep track of least recently used elements | |
| class Node { | |
| String key_; | |
| String val_; | |
| Node next; | |
| Node prev; | |
| Node (String key,String val) { | |
| this.key_ = key; | |
| this.val_ = val; | |
| this.next = null; | |
| this.prev = null; | |
| } | |
| } | |
| private final int capacity; | |
| private Map<String,String> _lruMap; | |
| private Node front; | |
| private Node back; | |
| private void addToFront(String key,String val) { | |
| Node tmpNode = new Node(key,val); | |
| if (front == back && front == null) { | |
| front = tmpNode; | |
| back = front; | |
| } else { | |
| //Do not add duplicate key at front | |
| if (front.key_.equals(key) && front.val_.equals(val) ) { | |
| return; | |
| } | |
| front.prev = tmpNode; | |
| tmpNode.next = front; | |
| front = tmpNode; | |
| } | |
| } | |
| private String removeFromBack() { | |
| if (back == null) { | |
| return back.key_; | |
| } | |
| Node tmpNode = back; | |
| back = back.prev ; | |
| back.next = null; | |
| return tmpNode.key_; | |
| } | |
| LRUCache(int capacity) { | |
| this.capacity = capacity; | |
| front = null; | |
| back = null; | |
| _lruMap = new HashMap<String,String>(); | |
| } | |
| public String get(String key,String val) { | |
| if (_lruMap.containsKey(key) ) { | |
| //update the ds | |
| put (key,val); | |
| _lruMap.get(key); | |
| } | |
| return null; | |
| } | |
| public void put(String key ,String val) { | |
| if (capacity == _lruMap.size()) { | |
| //Remove the entry from the map | |
| String rKey = removeFromBack(); | |
| _lruMap.remove(rKey); | |
| } | |
| addToFront(key,val); | |
| _lruMap.put(key,val); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment