Least Recently Used or LRU Cache : a simple implementation in Java

A friend of mine asked me about LRU cache and while explaining the same I could not locate a simple implementation one by just googling it.

The Java util provides a beautiful implementation through LinkedHashMap. Which is a Hash table and linked list implementation of the Map interface, with predictable iteration order. In order to use it as an LRU cache, do the following,

• use constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) and set the accessOrder to true. and,
• override the implementation for removeEldestEntry(Map.Entry eldest)
• please keep in mind that this is NOT an thread safe implementation and to have thread safety for this LinkedHashMap, you can do something like Map m = Collections.synchronizedMap(new LinkedHashMap(…)), if multiple threads may use the map.

You can of-course look at the implementation of LinkedHashMap for reference and it is really awesome how implemented but I thought to write up my own implementation for LRU cache using a HashMap and a linked list with minimal functionality. So this implementation provides a LRU cache implementation in Java using Hashmap and a doubly linked list.

package com.das.yadab.java;

import java.util.HashMap;
import java.util.Map;

public class LRUCache<K, V> {
    public static final int MAX_SIZE = 100; // Default max size for the cache to grow.
    private Entry<K, V> head;
    private HashMap<K, Entry> internalCache;
    private int maxSize;

    public LRUCache() {
        this.head = new Entry(null, null);
        head.before = head.after = head;
        internalCache = new HashMap<K, Entry>();
        maxSize = MAX_SIZE;
    }

    public LRUCache(int maxSize) {
        this.head = new Entry(null, null);
        head.before = head.after = head;
        internalCache = new HashMap<K, Entry>();
        this.maxSize = maxSize;
    }

    /**
     * Gets value associated with the specified key from cache.
     *
     * @param key
     * @return value or null if not found
     */
    public V get(Object key) {
        Entry<K, V> e = internalCache.get(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

    /**
     * Associates key and value in the cache, null value is not allowed.
     * If cache size has grown more than the allowed capacity the eldest member will be evicted.
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        if (value == null) {
            throw (new IllegalArgumentException("Null Value association is not helpful in caching"));
        }
        if(internalCache.containsKey(key)){
            internalCache.get(key).setValue(value);
            internalCache.get(key).recordAccess(this);
           return;
        } 
        if (shouldRemoveEldestEntry()) {
          Entry eldest = head.after;
          removeEntry(eldest);
        }
        Entry entry = new Entry(key, value);
        entry.addBefore(head);
        internalCache.put(key, entry);
        return value;
    }

    private void removeEntry(Entry eldest) {
        // since we do not allow null value association so this is safe.
        if (internalCache.remove(eldest.key) != null) {
            eldest.recordRemoval(this);
        }
    }

    /*
    Returns true if this map should remove its eldest entry.
    if maxSize is not set during initialization the method will always return false.
     */
    public boolean shouldRemoveEldestEntry() {
        if (internalCache.size() > maxSize) {
            return true;
        }
        return false;
    }

    static class Entry<K, V> implements Map.Entry<K, V> {
        private Entry<K, V> before, after;
        private K key;
        private V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        private void addBefore(Entry<K, V> existingEntry) {
            after = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(LRUCache<K, V> cache) {
            remove();
            addBefore(cache.head);
        }

        final void recordRemoval(LRUCache<K, V> m) {
            remove();
        }

        private void remove() {
            before.after = after;
            after.before = before;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry) o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return (key == null ? 0 : key.hashCode()) ^
                    (value == null ? 0 : value.hashCode());
        }

        @Override
        public String toString() {
            return "Entry key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "internalCache=" + internalCache +
                ", head=" + head +
                ", maxSize=" + maxSize +
                '}';
    }
}

An example usage, since it only accesses the key “0”, it should retain the key “0” though it is added at the beginning.
LRUCache cache = new LRUCache(5);
for (int i = 0; i < 10; i++) {
    cache.put(Integer.toString(i), i);
    cache.get(Integer.toString(0));
}

			

			
			


				

Java : difference between Polymorphism and Inheritance

Since the definition for both them have some common ground so it may confuse some times with the differences between this two paradigm. Definitions from wiki, you might have already read it.

• Polymorphism : polymorphism is the provision of a single interface to entities of different types. Java supports basically subtype(using inheritance in Java) and parametric polymorphism (using generics in Java).
• Inheritance (OOP) is when an object or class is based on another object (prototypal inheritance) or class (class-based inheritance), using the same implementation (inheriting from an object or class) specifying implementation to maintain the same behavior (realizing an interface; inheriting behavior).

So from the above definition,

1. Inheritance or subclassing in Java is one of the technique used to achieve polymorphism.
2. Inheritance refers to using the structure and behavior of a superclass in a subclass.
3. Inheritance helps code reuse at the same time while achieving polymorphism.

Java : Asynchronous Task sequencing using Observer pattern

The other day I was answering a question on stackoverflow on what could be a simple implementation of sequencing or ordering asynchronous tasks in Java. More detail about the question. Basically task sequencing problem is, you have a list of tasks say : {A, B, C, D} and you want execute them in some order, say {A} -> {B, C} ->{D} ->{X} -> {A}.

I preferred the Observer pattern because it is more of a reactive pattern so that design is reactive in nature rather than controlling and more loosely coupled.

public abstract class Task extends Observable implements Runnable, Observer {
    private final Mutex lock = new Mutex();
    private final String taskId;
    private final Set<String> completedTasks;
    private final Set<String> shouldCompletedTasksBeforeStart;

    public Task(final String taskId) {
        this.taskId = taskId;
        this.completedTasks = new HashSet<>();
        this.shouldCompletedTasksBeforeStart = new HashSet<>();
    }

    public String getTaskId() {
        return this.taskId;
    }

    @Override
    public void run() {
        while (true) {
            this.lock.getLock();
            if (this.completedTasks.equals(this.shouldCompletedTasksBeforeStart)) {
                doWork();
                setChanged();
                notifyObservers(this.taskId);
                // reset
                this.completedTasks.clear();
            }
            this.lock.freeLock();
            try {
                // just some sleep, you change to how it fits you
                Thread.sleep(1000);
            } catch (final InterruptedException e) {
                // TODO Auto-generated catch block
            }
        }
    }

    @Override
    public void update(final Observable observable, final Object arg) {
        this.lock.getLock();
        this.completedTasks.add((String) arg);
        this.lock.freeLock();
    }

    public void addPredecessorTask(final Task task) {
        if (this.taskId.equals(task.taskId)) {
            return;
        }
        this.lock.getLock();
        // Notice here, it is a little logic make your predecessor/successor work
        task.addObserver(this);
        this.shouldCompletedTasksBeforeStart.add(task.taskId);
        this.lock.freeLock();
    }
    protected abstract void doWork();
}

//HelloTask.java
public static class HelloTask extends Task {
    public HelloTask(final String taskId) {
        super(taskId);
    }

    @Override
    protected void doWork() {
        System.out.println("Hello from " + getTaskId() + "!");
    }
}

//Main.java
public class Main {
    public static void main(final String[] args) {
        final HelloTask helloTaskA = new HelloTask("A");
        final HelloTask helloTaskB = new HelloTask("B");
        final HelloTask helloTaskC = new HelloTask("C");

        helloTaskA.addPredecessorTask(helloTaskB);
        helloTaskC.addPredecessorTask(helloTaskB);

        final ExecutorService pool = Executors.newFixedThreadPool(10);
        pool.execute(helloTaskC);
        pool.execute(helloTaskA);
        pool.execute(helloTaskB);

    }
}

Artificial Brain and cryptanalysis

Was reading about different Blue brain or Artificial brain projects and thought of writing a simple network myself. So all I could afford myself is one compute machine from amazon which allows to run 3000 threads only if I am not doing much in each neuron. Each thread is a neuron and after adding little logic of filtering I came down to much lower number. I felt like, what am I doing, so to simulate this in cloud framework, I need the following,

• A good messaging platform
• A very lightweight service framework to make it work as neuron

And to able to use this network for doing a cryptanalysis is not far but the brain I produced is a size of an ant or less. I need bigger brain means a lot of machines => a lot of money ??

GIDS.WEB 2011; Software Development == Mobile Software Development ?

Today, I have attended the GIDS.WEB 2011 (great indial developer summit) and it came back with mixed feeling about how it went! I have registered myself for the WEB sessions only as I am very interested to see how the new trends and technologies merging? I am not surprised to see that all the presenter are fucusing on mobile / tablet devices in their speech but I am surprised that some are stretching it bit more…In example they just point out mobile devices / tablets for all the topics.

simple C/C++ Serialization or deflating or Marshalling user defined data types or objects

But is it to use boost or not it is your decision 🙂  It is a good lib. But I find it very handy for small in another way as below;-

// Just a simple serialization in C++
#ifndef CVARIABLELENDATA_HPP
#define CVARIABLELENDATA_HPP

#include <string>

typedef char*	BuffPtr;
typedef size_t	BuffLen;

class CVariableLenData
{
public:
	//Serilizes data members to a char buffer
	void Serialize(BuffPtr &ptr, BuffLen len, BuffLen &writelen) const;

	//DeSerilizes from a char buffer & constructs an object
	static CVariableLenData* DeSerialize(const BuffPtr ptr, BuffLen len);

	void SetData(std::string& str);
	void SetData(int& val);

	CVariableLenData();
private:
	int m_some_int;			// fixed length
	std::string m_some_str; // variable length
	CVariableLenData(const CVariableLenData&);
};

#endif //CVARIABLELENDATA_HPP

// Source file
#include <cstdio>
#include "CVariableLenData.h"

using namespace std;

CVariableLenData::CVariableLenData():m_some_int(0),m_some_str(){}

void CVariableLenData::Serialize(BuffPtr &ptr, BuffLen bufflen, BuffLen& writelen) const
{
	if(!ptr)
		return;
	writelen = _snprintf (ptr, bufflen,"%d", m_some_int);
	*(ptr+writelen) = ' ';		// after each numeric value add an space
	size_t len = writelen + 1;
	// now write the string
	// copy length
	writelen = _snprintf ( (ptr+len), bufflen,"%u", m_some_str.length());
	*(ptr + len ) = ' ';
	len = len + writelen + 1;
	// Copy the data
	memcpy( (ptr+len), m_some_str.c_str(), m_some_str.length());
	writelen = len;
	return;
}

Some links.

• http://www.parashift.com/c++-faq-lite/serialization.html
• http://functionx.com/cpp/articles/serialization.htm
• http://en.wikipedia.org/wiki/Serialization
• http://stackoverflow.com/questions/234724/how-to-serialize-in-c
• http://www.boost.org/doc/libs/1_44_0/libs/serialization/doc/index.html