LinkedHashMap源码解读与实现LRU缓存
2017-11-28 本文已影响39人
icecrea
LinkedHashMap继承HashMap
自定义全局变量header表示头节点
private transient Entry<K,V> header;
private final boolean accessOrder;
同时LinkedHashMap的自定义内部类Entry也继承了HashMap的Entry，但是新增了两个指针before和after。在哈希表的基础上又构成了双向链接列表。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
private void remove() {
before.after = after;
after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
构造方法：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
可以看到，默认调用了父类HashMap的构造方法，传入loadFactor，默认为 false，代表按照插入顺序进行迭代。可以显式设置为 true，代表以访问顺序进行迭代。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
可以看到最后一步构造调用了init()方法，在HashMap中方法为空。而在LinkedHashMap中重写了这个方法，进一步实现了对其元素Entry的初始化。
@Override
void init() {
header = new Entry<>(-1, null, null, );
header.before = header.after = header;
}
在HashMap中，其Put方法如下。它的Entry.recordAccess是空方法。
过程如下：先哈希定位到数组中哈希桶位置，然后遍历entry链表，如果hash相同并且key相同，覆盖原value，更新成新value。如果对应哈希桶中没有元素，调用addEntry()方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
而LinkedHashMap没有重写Put方法，而是重写了父Entry.recordAccess()方法。还有addEntry(),createEntry()方法
如果accessOrder为真，表示按照访问顺序迭代时，调用addBefore(lm.header)方法，表示将元素放到最后。（双向链表，头结点的before代表最后元素）
注意：这里调用情况是，同一个哈希桶对应的entry链表的调整。
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
重写Entry.addBefore方法，实现链表的链接
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
重写的addEnty,createEntry方法。主要是重写createEntry方法，通过调用 e.addBefore(header)完成链表的链接。
/**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
/**
* This override differs from addEntry in that it doesn't resize the
* table or remove the eldest entry.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
LinkedHashMap 重写了父类 HashMap 的 get 方法，在每一次get后调用了我们前面分析过的recordAccess方法，将元素放置到最后一个，这样就形成了一个按访问顺序迭代的哈希链表。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
如何通过这种数据结构实现lru缓存？
该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建 LRU 缓存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回 false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
LinkedHashMap在添加元素的时候会对此进行判断
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
通过重写removeEldestEntry可以实现自定义容量的linkedlist
LRU具体实现代码如下：
public class LRUCache<K, V> {
private static final float hashTableLoadFactor = 0.75f;
private LinkedHashMap<K, V> map;
private int cacheSize;
static Logger logger = LoggerFactory.getLogger(LRUCache.class);
public LRUCache(int cacheSize) {
this.cacheSize = cacheSize;
int hashTableCapacity = (int) Math
.ceil(cacheSize / hashTableLoadFactor) + 1;
map = new LinkedHashMap<K, V>(hashTableCapacity, hashTableLoadFactor, true) {
private static final long serialVersionUID = 1;
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > LRUCache.this.cacheSize;
}
};
}
public synchronized V get(K key) {
return map.get(key);
}
public synchronized void put(K key, V value) {
map.put(key, value);
}
public synchronized Collection<Map.Entry<K, V>> getAll() {
return Lists.newArrayList(map.entrySet());
}
public static void main(String[] args) {
LRUCache<String, String> c = new LRUCache<String, String>(3);
c.put("1", "one");
c.put("2", "two");
c.put("3", "three");
c.put("4", "four");
if (c.get("2") == null) {
throw new Error();
}
c.put("5", "five");
c.put("4", "second four");
c.get("5");
for (Map.Entry<String, String> e : c.getAll()) {
logger.info(e.getKey() + " : " + e.getValue());
}
}
