Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

题述如上。

第一次编写的代码，思路是通过引用计数器来实现，功能通过，但又因为要不断地维护这个计数器而效率低下导致未accepted。

public class LRUCache {
	class Cache {
		int key;
		int value;
		int count;
	}

	Cache[] Cc;

	public LRUCache(int capacity) {
		Cc = new Cache[capacity];
		for (int i = 0; i < Cc.length; i++) {
			Cc[i] = new Cache();
			Cc[i].value = http://www.mamicode.com/-1;>
然后我又默默的优化了一下。思路还是一样的。但是少了很多多余的变量
class Map {
		int key;
		int value;
	}

	Map[] map;
	int capacity;

	public LRUCache(int capacity) {
		map = new Map[capacity];
		for (int i = 0; i < capacity; i++) {
			map[i] = new Map();
		}
		this.capacity = capacity;
	}

	public int get(int key) {
		int i = capacity - 1;
		int result = -1;
		Map temp = new Map();
		while (i > 0) {
			if (map[i].key == key) {
				result = map[i].value;
				temp = map[i];
				while (i < capacity - 1) {
					map[i] = map[i + 1];
					i++;
				}
				map[capacity - 1] = temp;
				break;
			}
			i--;
		}

		return result;
	}

	public void set(int key, int value) {
		int i = 0;
		while (i < capacity - 1) {
			map[i].key = map[i + 1].key;
			map[i].value = http://www.mamicode.com/map[i + 1].value;>
但是还是没有通过：
Time Limit Exceeded
然后就不淡然了。。主要的问题是如何维护一个管道 。而且还是可调配顺序的。免不了要去用循环向后压数据，那么问题就在于如何去‘压’这个数。

然后。。想到了。。指针。。然后是自然的链表，有key和value其实可以用hashmap.但是不太想用已经现有的东西。所以我决定写一个由简到繁的代码。

第一个：用java里边自带的linkedhashmap。简直就是完全为了本题而出的。
简直像cheating.
public class LRUCache {
    private int capacity;
    private Map<Integer, Integer> map;

    public LRUCache(int c) {
      this.capacity = c;
      this.map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
      };
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        return map.get(key);
    }

    public void set(int key, int value) {
        map.put(key, value);
    }
}


第二个就是自己写个链表。然后用hashmap的
class Node {
		int key;
		int value;
		Node next;
		Node pre;

		Node(int key, int value) {
			this.key = key;
			this.value = http://www.mamicode.com/value;>



可以看到自己写链表的话效率上会快那么 一点。主要是因为自己的功能单一。所以相当于精简了不必要的代码而提高了效率。

第三个比较有挑战性啦。那就是连hashmap都自己来实现一下
hashmap的结构特别像一个珠帘。同样下标的数据将会放在一串珠子上。


public class LRUCache {
	class Node {
		int key;
		int value;
		Node next;
		Node pre;

		Node(int key, int value) {
			this.key = key;
			this.value = http://www.mamicode.com/value;>
高度参考 Hashmap的源代码，然后进行部分重现，对于Java 8的hashmap有时间将继续实现，Java 8在进行hashmap的实现时，如果 hash碰撞非常多将自动转换成treemap

主要实现难点及技巧：
int capacity = 0;
	Node head = new Node(-1, -1);
	Node tail;
	int size = 0;
	int Mapsize = 1;

	public LRUCache(int capacity) {
		this.capacity = capacity;

		while (Mapsize < capacity) {
			Mapsize = Mapsize << 1;
		}
		mymap = new Map[Mapsize];
	}
在初始化的时候找到大于设置容量的最小的2的n次方。
用途：用于之后各种的计算下标，如想找到第5个数时，5&Mapsize-1。比如说Mapsize此时是16，那么就是5&15=5，101&1111=101=5.很神奇的地方是当下标大于size时，比如说16&15将等于0，也就是达到了循环赋值的目的。



public void set(int key, int value) {
		Node temp = new Node(key, value);
		int index = key & Mapsize - 1;
		Map e = mymap[index];
		for (; e != null; e = e.next) {
			if (e.key == key) {
				removeNode(e.value);
				e.value = http://www.mamicode.com/temp;>set方法也是调试了许久，苦于java不支持指针所以要在map里加一个构造函数，    Map(int key, Node value, Map next),将新加入的结点到在链表头。

private void removeHead() {
		// TODO Auto-generated method stub

		int index = head.key & Mapsize - 1;
		Map prev = mymap[index];
		Map e = prev;
		while (e != null) {
			Map next = e.next;
			if (e.value.key == head.key) {
				if (prev == e)
					mymap[index] = next;
				else
					prev.next = next;
			}
			prev = e;
			e = next;
		}
		if (size > 1) {
			head = head.next;
			head.pre = null;
		} else {
			head = null;
		}
		size--;
	}
删除头指针，关键代码在于
                Map prev = mymap[index];
		Map e = prev;
		while (e != null) {
			Map next = e.next;
			if (e.value.key == head.key) {
				if (prev == e)
					mymap[index] = next;
				else
					prev.next = next;
			}
			prev = e;
			e = next;
		}

两个变量prev 和next 分别用于存储要删除结点的前一个和后一个结点，当找到要删除的结点e时，只需要将prev=next即可。
if (prev == e)是用来判断第一次循环时也就是mymap[index]的本身是不是要删除的那个结点，是的话直接等于下一个就好。

这次的运行效率自然应比上一个高了。





为了再次优化将构造函数变为
while (Mapsize < capacity*2) {
			Mapsize = Mapsize << 1;
		}

以减少hash碰撞。




























Leetcode之LRU Cache