• Home
  • About

Snippet IT

IT News, Programming, Internet and Blogging

  • Programming and Scripting
  • Tips and Tricks
  • Software and Hardware
  • New and Happening
You are here: Home / Programming and Scripting / Java: Least Recently Used (LRU) Cache

Java: Least Recently Used (LRU) Cache

May 14, 2009 by Sze Hau Leave a Comment

Least Recently Used or in short LRU is an performance optimizing algorithm. LRU algorithm is widely used in software programming as well as in hardware instructions (e.g. CPU).

In many case, in programming, we may want to cache some data from physical disk, for example database and files, but we cannot load all the data into memory due to the memory limitation on the server or PC. In those cases, you may want to consider to use LRU algorithm to solve the memory limitation problem.

The LRU algorithm is very simple, it keeps a list of read items in memory and discards the least recently used items first when the define LRU cache size is reach.

Java collections does not have a class for LRU but implementing a LRU by yourself is not difficult. You just need to declare a class the inherits LinkedHashMap and override its removeEldestEntry() function.

Here is the code that makes it works:

public class LeastRecentlyUsedCache<K,V> extends LinkedHashMap<K,V> {
    private int lrucSize;

    public LeastRecentlyUsedCache(int size) {
        lrucSize = size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > lrucSize;
    }
}

The following example show how you can use the LRU cache in your program or to solve your problem:

  // Create LRU cache of 500 customer
  LeastRecentlyUsedCache<Integer,Customer> lru =
    new LeastRecentlyUsedCache<Integer,Customer>(500);

  while (/* looping a big list of items */)

    // Need refer customer, so try to get
    // the customer from LRU cache
    customer = lru.get(id);

    // Customer not in LRU cache
    if (customer == null) {

      // Load customer from database
      customer = ...

      // Put it into LRU cache
      lru.put(customer.id, customer);
    }

    // Use the customer object
    ...
  }

Pretty simple right? From the above example, let say we are looping a big list of items (say one millions for sales records) and having 1000 of customer. Some customers have many sales records and some customers have no sales record. Instead of reading each customer record for each sales record from database (file access is slower than memory), by using LRU cache, it will reuse the loaded customer data in LRU cache whenever possible and therefore increase the overall performance.

This because a most recently used data will be likely to be used again and therefore will be stayed in cache;  and a least recently used item will not be used again and therefore will be unloaded when the cache reaches the maximum cache size.

Note: The is <K,V> (key and value) for generic declaration purpose.

More from my site

  • Java: Loading Large Data into JTable or JListJava: Loading Large Data into JTable or JList
  • Java: How To Select Top N Objects From A ListJava: How To Select Top N Objects From A List
  • Java: Format Integer Into Fixed Width StringJava: Format Integer Into Fixed Width String
  • Java: Randomly sort values in a array (the generic way) in single passJava: Randomly sort values in a array (the generic way) in single pass
  • Java: Format integer into number of decimal places and performanceJava: Format integer into number of decimal places and performance
  • Java: Unlimited Strength Jurisdiction PolicyJava: Unlimited Strength Jurisdiction Policy

Filed Under: Programming and Scripting Tagged With: algorithm, cache, Java, LRU, performance

About Sze Hau

Geek. Love programming. Coffee addicted. Married with two children. Working towards financial freedom.

Leave a Reply Cancel reply

Advertisement

  • Facebook
  • Google+
  • Instagram
  • Twitter

Email News Letter

Sign up to receive updates daily and to hear what's going on with us

Software and Hardware

MD5 and SHA1 Checksum Using Windows

July 5, 2017 By Sze Hau Leave a Comment

Blog Network

  • Personal Fincance Personal Finance – Personal Money Tips, Stock Investment, Small Business and Make Money Online
  • szehau's weblog Life, Internet, Software, Gadgets, Programming and Investments

Snippet IT

This is the place where I want to share anything about information technology.

Search

Recent

  • MD5 and SHA1 Checksum Using Windows
  • MD5 and SHA1 Checksum Using Linux
  • Java: Unlimited Strength Jurisdiction Policy
  • WordPress: How To Change Admin Username
  • Linux: How To Compress And Decompress Folders And Files

Tags

Adsense advertisement advertising apache blog blogging tips C# EGPC error estimation format format Integer Gmail Google Google Adsense Google Chrome Google Search Engine Google search result how to HTTP internet marketing Java JavaScript Linux money password performance PHP programming search engine optimization secure security short URL SQL static constructor String tiny URL Tips and Tricks twitter video Windows Vista Wordpress wordpress plugin wordpress theme Youtube

Copyright © 2025 · Magazine Pro Theme on Genesis Framework · WordPress · Log in