{"id":6237,"date":"2018-08-04T09:59:59","date_gmt":"2018-08-04T04:29:59","guid":{"rendered":"https:\/\/java2blog.com\/?p=6237"},"modified":"2021-04-13T20:58:51","modified_gmt":"2021-04-13T15:28:51","slug":"lru-cache-implementation-java","status":"publish","type":"post","link":"https:\/\/java2blog.com\/lru-cache-implementation-java\/","title":{"rendered":"LRU cache implementation in java"},"content":{"rendered":"<blockquote><p>If you want to practice data structure and algorithm programs, you can go through\u00a0<a href=\"https:\/\/java2blog.com\/java-coding-interview-questions\/\" target=\"_blank\" rel=\"noopener noreferrer\">Java coding interview questions<\/a>.<\/p><\/blockquote>\n<p>In this post, we will see\u00a0LRU cache implementation in java.<br \/>\n<div id=\"toc_container\" class=\"toc_light_blue no_bullets\"><p class=\"toc_title\">Table of Contents<\/p><ul class=\"toc_list\"><li><a href=\"#Problem\">Problem<\/a><\/li><li><a href=\"#Solution\">Solution<\/a><ul><li><a href=\"#Using_HashMap_and_Doubly_linked_list\">Using HashMap and Doubly linked list<\/a><\/li><li><a href=\"#Using_LinkedHashMap\">Using LinkedHashMap<\/a><\/li><\/ul><\/li><\/ul><\/div>\n\n<hr \/>\n<h2><span id=\"Problem\"><span style=\"color: #f89820;\">Problem<\/span><\/span><\/h2>\n<p>Design a Least recently used cache implementation in java. It should have below properties.<\/p>\n<p><code>bounded size:<\/code> It should have bounded size to take care of memory limits.<\/p>\n<p><code>Fast access:<\/code> As we are designing cache, we should be able to fetch or update entries faster.<\/p>\n<p><code>Evict least recently used entry:<\/code> Cache should evict least recently used entry if capacity is reached.<\/p>\n<hr \/>\n<h2><span id=\"Solution\"><span style=\"color: #f89820;\">Solution<\/span><\/span><\/h2>\n<h3><span id=\"Using_HashMap_and_Doubly_linked_list\"> Using HashMap and Doubly linked list<\/span><\/h3>\n<p>As we need to do lookup in <code>O(1)<\/code> time then\u00a0<a href=\"https:\/\/java2blog.com\/hashmap-in-java-with-examples\/\" target=\"_blank\" rel=\"noopener noreferrer\">HashMap<\/a> is obvious choice but we need to take care of least recently used entry as well.<\/p>\n<p>We need to find a data structure\u00a0which can remove\/add in O(1) time if we already know the node. We can use a <a href=\"https:\/\/java2blog.com\/doubly-linked-list-java\/\" target=\"_blank\" rel=\"noopener noreferrer\">double linked list<\/a> for this purpose because it provides removal\/addition in O(1) time if already know about the node.<\/p>\n<p><code>HashMap<\/code> will make get operation in <code>O(1) time<\/code> and <code>Doube linked list<\/code> will make\u00a0removal\/addition in <code>O(1) time<\/code>.<\/p>\n<p><img decoding=\"async\" loading=\"lazy\" class=\"aligncenter wp-image-6247 size-full\" src=\"https:\/\/java2blog.com\/wp-content\/uploads\/2018\/08\/LruCache-1.jpg\" alt=\"LRU cache\" width=\"900\" height=\"519\" srcset=\"https:\/\/java2blog.com\/wp-content\/uploads\/2018\/08\/LruCache-1.jpg 900w, https:\/\/java2blog.com\/wp-content\/uploads\/2018\/08\/LruCache-1-300x173.jpg 300w, https:\/\/java2blog.com\/wp-content\/uploads\/2018\/08\/LruCache-1-768x443.jpg 768w\" sizes=\"(max-width: 900px) 100vw, 900px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Here is simple program for\u00a0LRU cache implementation in java.<\/p>\n<pre class=\"java\" name=\"code\">package org.arpit.java2blog;\n\nimport java.util.HashMap;\n\nclass Node{\n    int key;\n    int value;\n    Node prev;\n    Node next;\n\n    public Node(int key, int value){\n        this.key = key;\n        this.value = value;\n    }\n}\npublic class LRUCache {\n    int capacity;\n    HashMap&lt;Integer, Node&gt; map = new HashMap&lt;Integer, Node&gt;();\n    Node head=null;\n    Node end=null;\n\n    public LRUCache(int capacity) {\n        this.capacity = capacity;\n    }\n\n    public int get(int key) {\n        if(map.containsKey(key)){\n            Node n = map.get(key);\n            delete(n);\n            setHead(n);\n            return n.value;\n        }\n\n        return -1;\n    }\n\n    \/*This method will delete node*\/\n    public void delete(Node node){\n        if(node.prev!=null){\n            node.prev.next = node.next;\n        }else{\n            head = node.next;\n        }\n\n        if(node.next!=null){\n            node.next.prev = node.prev;\n        }else{\n            end = node.prev;\n        }\n\n    }\n\n    \/*This method will make passed node as head*\/\n    public void setHead(Node node){\n        node.next = head;\n        node.prev = null;\n\n        if(head!=null)\n            head.prev = node;\n\n        head = node;\n\n        if(end ==null)\n            end = head;\n    }\n\n    public void set(int key, int value) {\n        if(map.containsKey(key)){\n            \/\/ update the old value\n            Node old = map.get(key);\n            old.value = value;\n            delete(old);\n            setHead(old);\n        }else{\n            Node newNode = new Node(key, value);\n            if(map.size()&gt;=capacity){\n\n                map.remove(end.key);\n                \/\/ remove last node\n                delete(end);\n                setHead(newNode);\n\n            }else{\n                setHead(newNode);\n            }    \n\n            map.put(key, newNode);\n        }\n    }   \n\n    public static void main(String[] args) throws java.lang.Exception {\n        LRUCache lrucache = new LRUCache(4);\n        lrucache.set(1, 100);\n        lrucache.set(10, 99);\n        lrucache.set(15, 98);\n        lrucache.set(10, 97);\n        lrucache.set(12, 96);\n        lrucache.set(18, 95);\n        lrucache.set(1, 94);\n\n        System.out.println(lrucache.get(1));\n        System.out.println(lrucache.get(10));\n        System.out.println(lrucache.get(15));\n\n    }\n}\n<\/pre>\n<p>When you run above program, you will get below output:<\/p>\n<div class=\"content-box-green\">94<br \/>\n97<br \/>\n-1<\/div>\n<p>As you can see, in last 4 entries, we do not have <code>15<\/code> as key. That&#8217;s the reason we are getting <code>-1<\/code> for it.<\/p>\n<h3><span id=\"Using_LinkedHashMap\"> Using LinkedHashMap<\/span><\/h3>\n<p>We can use <a href=\"https:\/\/java2blog.com\/linkedhashmap-in-java-with-example\/\" rel=\"noopener noreferrer\" target=\"_blank\">LinkedHashMap<\/a> to create LRU cache as well. LinkedHashMap has a <a href=\"https:\/\/java2blog.com\/constructor-java\/\" rel=\"noopener noreferrer\" target=\"_blank\">constructor<\/a> in which you can specify access order. If you pass <code>accessOrder<\/code> as true, LinkedHashMap will work on the basis of access order rather than insertion order.<\/p>\n<pre class=\"lang:java decode:1 \" >\n\/**\n     * Constructs an empty <tt>LinkedHashMap<\/tt> instance with the\n     * specified initial capacity, load factor and ordering mode.\n     *\n     * @param  initialCapacity the initial capacity\n     * @param  loadFactor      the load factor\n     * @param  accessOrder     the ordering mode - <tt>true<\/tt> for\n     *         access-order, <tt>false<\/tt> for insertion-order\n     * @throws IllegalArgumentException if the initial capacity is negative\n     *         or the load factor is nonpositive\n     *\/\n    public LinkedHashMap(int initialCapacity,\n                         float loadFactor,\n                         boolean accessOrder) {\n        super(initialCapacity, loadFactor);\n        this.accessOrder = accessOrder;\n    }\n<\/pre>\n<p>We will also override a method named <code>removeEldestEntry()<\/code> and it will return <code>true<\/code> in case <code>size()<\/code> is greater than <code>capacity<\/code>.<\/p>\n<p>Let&#8217;s create a class Named <code>LRUCache<\/code><\/p>\n<pre class=\"lang:java decode:1 \" >\npackage org.arpit.java2blog;\nimport java.util.LinkedHashMap; \nimport java.util.Map; \n\nclass LRUCache { \n    private LinkedHashMap&lt;Integer, Integer&gt; cacheMap; \n    public LRUCache(int capacity) \n    { \n        cacheMap = new LinkedHashMap&lt;Integer, Integer&gt;(capacity, 0.75f, true) { \n            protected boolean removeEldestEntry(Map.Entry eldest) \n            { \n                return size() &gt; capacity; \n            } \n        }; \n    } \n\n    \/\/ This method works in O(1) \n    public int get(int key) \n    { \n        return cacheMap.getOrDefault(key, -1); \n    } \n\n    \/\/ This method works in O(1) \n    public void set(int key, int value) \n    { \n        cacheMap.put(key, value); \n    } \n} \n\npublic class LRUUsingLinkedHashMapMain { \n\n    public static void main(String[] args) \n    { \n        LRUCache lrucache = new LRUCache(4);\n        lrucache.set(1, 100);\n        lrucache.set(10, 99);\n        lrucache.set(15, 98);\n        lrucache.set(10, 97);\n        lrucache.set(12, 96);\n        lrucache.set(18, 95);\n        lrucache.set(1, 94);\n\n        System.out.println(lrucache.get(1));\n        System.out.println(lrucache.get(10));\n        System.out.println(lrucache.get(15));\n\n    } \n} \n<\/pre>\n<p>When you run above program, you will get output:<\/p>\n<div class=\"content-box-purple\">\n94<br \/>\n97<br \/>\n-1\n<\/div>\n<p>As you can see, in last 4 entries, we do not have <code>15<\/code> as key. That&#8217;s the reason we are getting <code>-1<\/code> for it.<\/p>\n<p>That&#8217;s all about LRU cache implementation in java.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Table of ContentsProblemSolutionUsing HashMap and Doubly linked listUsing LinkedHashMap If you want to practice data structure and algorithm programs, you can go through\u00a0Java coding interview questions. In this post, we will see\u00a0LRU cache implementation in java. Problem Design a Least recently used cache implementation in java. It should have below properties. bounded size: It should [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"_mi_skip_tracking":false},"categories":[13,12],"tags":[],"_links":{"self":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/posts\/6237"}],"collection":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/comments?post=6237"}],"version-history":[{"count":0,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/posts\/6237\/revisions"}],"wp:attachment":[{"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/media?parent=6237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/categories?post=6237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/java2blog.com\/wp-json\/wp\/v2\/tags?post=6237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}