get操作
如果value存在于缓存中，或者可以由create创建，则返回key的对应的value。如果返回了value，它就会被移动到队列的头部。如果value没有被缓存并且不能被创建，则返回null。
public final V get(K key) {
//key不能为null
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
//命中次数
hitCount++;
return mapValue;
}
//未命中次数
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
//可以自己实现create方法，在miss的时候提供一个value
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
//create次数
createCount++;
mapValue = map.put(key, createdValue);
//如果保存value的时候，发现了一个新值，说明是在create的时候put进来的，那么就把最新的value保存进去。
if (mapValue != null) {
// There was a conflict so undo that last put
map.put(key, mapValue);
} else {
size += safeSizeOf(key, createdValue);
}
}
if (mapValue != null) {
//createdValue被覆盖了，回调一次以示来过
entryRemoved(false, key, createdValue, mapValue);
//返回最新的值
return mapValue;
} else {
trimToSize(maxSize);
//返回create的value
return createdValue;
}
}
HashMap的put操作
表在第一次使用时初始化，并在必要时进行调整。当分配时，长度总是2的幂。（我们还可以容忍某些操作的长度为0，以允许目前不需要的引导机制。）
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果链表为null或者为空，就进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//key的hash值与数组的长度相与，计算出键值的分布索引，如果此索引处没有数据，新建//一个节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果此索引处有数据
Node<K,V> e; K k;
//如果该索引处的首结点的key与put的key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//树结构在这里不讨论
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//遍历该链表
for (int binCount = 0; ; ++binCount) {
//如果链表遍历完都没有相同的key，就新建一个Node，并添加到链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果该索引下的链表存在相同的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//e是等于p.next,将e赋值给p，也就是将p.next赋值给p,是为了遍历链表需要
p = e;
}
}
//如果存在相同的key的node
if (e != null) { // existing mapping for key
V oldValue = e.value;
//如果设置可以覆盖相同key的value，或者原来的value为null，那么就覆盖
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
此方法在HashMap中为空实现，具体实现在LinkedHashMap中，此处设计到的设计模式为模板方法模式
LinkedHashMap的newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
链接到列表尾部
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
注意：新put的节点，第一次加入HashMap，根本不会走这个方法，因为e = null
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMapEntry<K,V> last;
//如果访问顺序accessOrder 为true，并且e不在链表尾部
if (accessOrder && (last = tail) != e) {
//put的节点p
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
//因为要移动到链表的尾部，所以after=null
p.after = null;
//如果put的e节点的上一个节点为null，那么说明在访问p之前，p为head，此时需要将//p之后的元素设置为head
if (b == null)
head = a;
Else
//如果p上一个节点不为null，那么将p从中断开
b.after = a;
//如果a不为null，将a指向b，也就是p的上一个节点，将p断开
if (a != null)
a.before = b;
else
//如果a为null，那么设置b为last
last = b;
//如果last为null，说明p现在为head
if (last == null)
head = p;
else {
//如果last不为null，将p链接到last之后
p.before = last;
last.after = p;
}
//设置p为尾部节点
tail = p;
//修改次数++
++modCount;
}
}
LinkedHashMap在访问一个元素之后，会将这个元素移动到双向链表的尾部(设置accessOrder 为true时)，LruCache的核心思想
LinkedHashMapEntry继承自HashMap.Node
HashMap.Node是一个单链表，LinkedHashMapEntry是一个双向链表，LinkedHashMap就是一个继承自HashMap的双向链表
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
put元素之后
注意：removeEldestEntry方法修饰符为protected，可以被子类重写
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
//如果evict为true，并且有最老的节点head，并且removeEldestEntry返回值为true，就会remove掉最老的节点。
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
get操作
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
//如果设置了访问指令，那么就把该节点移动到双向链表的尾部
afterNodeAccess(e);
return e.value;
}
//调用的是HashMap的getNode方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果散列链表不为null，也不为空，那么获取hash对应的索引处的第一个节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果查找的key与第一个节点相同，那么就直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果不等于第一个节点，那么就遍历这个节点所在的单链表
if ((e = first.next) != null) {
//数结构，暂不讨论
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//查找到就返回，找不到就返回null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
