HashMap&LinkedHashMap&Lr
1、HashMap
hashmap
1.1、 put函数的实现
public V put(K key, V value) {
// 对key的hashCode()做hash
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;
// tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 节点存在
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) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 写入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put函数大致的思路为：
1、对key的hashCode()做hash，然后再计算它在数组中的index;
2、如果没碰撞直接放到bucket里；
3、如果碰撞了，以链表的形式存在buckets后；
4、如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
5、如果节点已经存在就替换old value(保证key的唯一性)；
6、如果bucket满了(超过load factor*current capacity)，就要resize。
1.2、get函数的实现
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get大致思路如下：
0、对key的hashCode()做hash，然后再计算它在数组中的index;
1、如果hash相等并且key相等，直接命中；
2、如果有冲突，就去树中或者链表中寻找；
3、若为树；O(logn)；
4、若为链表，O(n)。
1.3、hash实现
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash实现
高16bit不变，低16bit和高16bit做了一个异或，计算下标的方式是(n - 1) & hash，异或一下，在bucket的n比较小的时，也可以让高16位和低16位都参数下标计算，有效缓解碰撞。
1.4、hashmap原理速记
hashmap是采用数组+链表的形式去存储键值对的，在java1.8中为了更快的查询，它会在链表超过一定长度时将链表转换成红黑树；它的put过程大概是这样的,,,；它的get过程大概是这样的,,,。
2、LinkedHashMap
linkedhashmap
LinkedHashMap是Hashmap+双向链表，并且依靠双向链表保持顺序。
2.1、三个重点实现的函数
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap继承于HashMap，因此也重新实现了这3个函数，顾名思义这三个函数的作用分别是：节点访问后、节点插入后、节点移除后做一些事情。
2.1.1、afterNodeAccess函数
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果定义了accessOrder，那么就保证最近访问节点放到最后
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
意思是如果定义了accessOrder，就把这个节点从双向链表原位置删除然后放到最后。（注意此时节点的next地址是不变的，改变的只是它的before和after地址）看似代码很乱，画图很容易理解。
2.1.2、afterNodeInsertion函数
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 如果定义了移除规则，则执行相应的移除
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
意思是 ，如果定义了移除规则removeEldestEntry，则执行相应的移除。（移除的是双向链表头结点，最近最少使用的节点）。
2.1.3、afterNodeRemoval函数
void afterNodeRemoval(Node<K,V> e) { // unlink
// 从链表中移除节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
意思是节点从hash表中删除后也要从双向链表中删除。
2.2、put和get函数
put函数在LinkedHashMap中未重新实现，只是实现了afterNodeAccess和afterNodeInsertion两个回调函数，在hashmap中的put方法中有对应调用。
get函数则重新实现并加入了afterNodeAccess来保证访问顺序，下面是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;
}
2.3、LinkedHashMap原理速记
LinkedHashMap是Hashmap+双向链表构成的，并且依靠双向链表保持顺序。
accessorder模式下，一个节点被访问之后就会将它从双向链表的原位置删除并放到最后，当一个节点插入后，如果重写了移除规则removeEldestEntry方法，则移除双向链表的首节点，即最近最少使用的节点，以此来实现LRU。
3、LruCache
3.1、LruCache构造
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
LruCache使用accessorder模式的LinkedHashMap构造。
3.2、put方法
public final V put(K key, V value) {
//不可为空，否则抛出异常
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
//插入的缓存对象值加1
putCount++;
//增加已有缓存的大小
size += safeSizeOf(key, value);
//向map中加入缓存对象
previous = map.put(key, value);
//如果已有缓存对象，则缓存大小恢复到之前
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//entryRemoved()是个空方法，可以自行实现
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//调整缓存大小(关键方法)
trimToSize(maxSize);
return previous;
}
put()方法将键值对插入存储到LinkedHashMap中，然后调用 trimToSize()方法，来判断缓存是否已满，如果满了就是使用Lru算法进行删除。
trimToSize方法
public void trimToSize(int maxSize) {
//死循环
while (true) {
K key;
V value;
synchronized (this) {
//如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
//如果缓存大小size小于最大缓存，或者map为空，不需要再删除缓存对象，跳出循环
if (size <= maxSize || map.isEmpty()) {
break;
}
//迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
//删除该对象，并更新缓存大小
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
trimToSize()方法不断地删除LinkedHashMap中队头的节点，即最近最少访问的节点，直到缓存大小小于最大值。
3.2、get方法
public final V get(K key) {
//key为空抛出异常
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//获取对应的缓存对象
//get()方法会实现将访问的元素更新到队列头部的功能
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
调用LinkedHashMap的get方法去获取数据，并维持访问顺序。
3.2、LruCache原理速记
LruCache内部维护了一个LinkedHashMap，并使用LinkedHashMap的accessorder模式去实现Lru算法，LinkedHashMap是Hashmap+双向链表构成的，并且依靠双向链表保持顺序。accessorder模式下，一个节点被访问之后就会将它从双向链表的原位置删除并放到最后，当一个节点插入后，如果大于了LruCache的最大容量，就会移除双向链表的首节点，即最近最少使用的节点，以此来实现LRU。
4、LinkedHashMap实现LruCache
public class LRUCache <K, V>{
private int capacity;
private Map<K, V> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new java.util.LinkedHashMap<K, V> (capacity, 0.75f, true) {
// 定义put后的移除规则，大于容量就删除eldest
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
};
}
public V get(K key) {
return cache.get(key);
}
public V put(K key, V value) {
return cache.put(key, value);
}
}
