LinkedHashMap中有一个重要的数据:
// LinkedEntry就是一个双向链表。除了保存当前对象的引用外,还保存了其上一个元素 before 和下一个元素 after 的引用
static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
LinkedEntry<K, V> nxt;
LinkedEntry<K, V> prv;
/** Create the header entry */
LinkedEntry() {
super(null, null, 0, null);
nxt = prv = this;
}
/** Create a normal entry */
LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
super(key, value, hash, next);
this.nxt = nxt;
this.prv = prv;
}
}
接下来看源代码:
public class LinkedHashMap<K, V> extends HashMap<K, V> {
// 如果用transient声明一个实例变量,当对象存储时,它的值不需要维持。换句话来说就是,用transient关键字标记的成员变量不参与序列化过程。
transient LinkedEntry<K, V> header;
/**
* True if access ordered, false if insertion ordered.
*/
private final boolean accessOrder;
//添加到header的prv位置,作为新的tail
@Override
void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
table[index] = oldTail.nxt = header.prv = newTail;
}
//这个方法和HashMap很类似,唯一需要注意的就是accessOrder那一句
@Override
public V get(Object key) {
/*
* This method is overridden to eliminate the need for a polymorphic
* invocation in superclass at the expense of code duplication.
*/
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
// Replace with Collections.secondaryHash when the VM is fast enough (http://b/8290590).
int hash = secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
//如果按照读取顺序,那么要调整e节点的位置
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
//取出e节点插入到header前面一个节点
private void makeTail(LinkedEntry<K, V> e) {
// 把e节点取出来
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// 把e节点插入到header前面一个节点中
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
}
LinkedHashMap没有实现put方法,而是复写了HashMap中的put方法里面的addNewEntry
由此我们可以总结 1.添加一个数据。先找到数组中对应的index,然后把数据放到链表的最后位置。由于是双向链表,那么就等于放在header.prv 2.获取一个数据。先找到数组中对应的index,然后找到数据所在的位置。如果是按照读取顺序来排序的,那么还要将这个节点放到双向链表的最后一位(这个特性,可以实现LRU算法)
参考: http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html http://blog.csdn.net/ns_code/article/details/37867985