1溃蔫、HashMap
1.1皆疹、 put函數(shù)的實現(xiàn)
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為空則創(chuàng)建
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;
// 節(jié)點存在
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函數(shù)大致的思路為：
1、對key的hashCode()做hash兄墅，然后再計算它在數(shù)組中的index;
2踢星、如果沒碰撞直接放到bucket里；
3隙咸、如果碰撞了沐悦，以鏈表的形式存在buckets后；
4五督、如果碰撞導(dǎo)致鏈表過長(大于等于TREEIFY_THRESHOLD)藏否，就把鏈表轉(zhuǎn)換成紅黑樹；
5充包、如果節(jié)點已經(jīng)存在就替換old value(保證key的唯一性)副签；
6、如果bucket滿了(超過load factor*current capacity)，就要resize淆储。
1.2冠场、get函數(shù)的實現(xiàn)
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) {
// 在樹中g(shù)et
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中g(shù)et
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本砰，然后再計算它在數(shù)組中的index;
1慈鸠、如果hash相等并且key相等，直接命中灌具；
2青团、如果有沖突，就去樹中或者鏈表中尋找咖楣；
3督笆、若為樹；O(logn)诱贿；
4娃肿、若為鏈表，O(n)珠十。
1.3料扰、hash實現(xiàn)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
高16bit不變，低16bit和高16bit做了一個異或焙蹭，計算下標的方式是(n - 1) & hash晒杈，異或一下，在bucket的n比較小的時孔厉，也可以讓高16位和低16位都參數(shù)下標計算拯钻，有效緩解碰撞。
1.4撰豺、hashmap原理速記
hashmap是采用數(shù)組+鏈表的形式去存儲鍵值對的粪般，在java1.8中為了更快的查詢，它會在鏈表超過一定長度時將鏈表轉(zhuǎn)換成紅黑樹污桦；它的put過程大概是這樣的,,,亩歹；它的get過程大概是這樣的,,,。
2凡橱、LinkedHashMap
LinkedHashMap是Hashmap+雙向鏈表小作，并且依靠雙向鏈表保持順序。
2.1梭纹、三個重點實現(xiàn)的函數(shù)
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap繼承于HashMap躲惰，因此也重新實現(xiàn)了這3個函數(shù)，顧名思義這三個函數(shù)的作用分別是：節(jié)點訪問后变抽、節(jié)點插入后础拨、節(jié)點移除后做一些事情氮块。
2.1.1、afterNodeAccess函數(shù)
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果定義了accessOrder诡宗，那么就保證最近訪問節(jié)點放到最后
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滔蝉，就把這個節(jié)點從雙向鏈表原位置刪除然后放到最后。（注意此時節(jié)點的next地址是不變的塔沃，改變的只是它的before和after地址）看似代碼很亂蝠引，畫圖很容易理解。
2.1.2蛀柴、afterNodeInsertion函數(shù)
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 如果定義了移除規(guī)則螃概，則執(zhí)行相應(yīng)的移除
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
意思是 ，如果定義了移除規(guī)則removeEldestEntry鸽疾，則執(zhí)行相應(yīng)的移除吊洼。（移除的是雙向鏈表頭結(jié)點，最近最少使用的節(jié)點）制肮。
2.1.3冒窍、afterNodeRemoval函數(shù)
void afterNodeRemoval(Node<K,V> e) { // unlink
// 從鏈表中移除節(jié)點
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;
}
意思是節(jié)點從hash表中刪除后也要從雙向鏈表中刪除。
2.2豺鼻、put和get函數(shù)
put函數(shù)在LinkedHashMap中未重新實現(xiàn)综液，只是實現(xiàn)了afterNodeAccess和afterNodeInsertion兩個回調(diào)函數(shù)，在hashmap中的put方法中有對應(yīng)調(diào)用儒飒。
get函數(shù)則重新實現(xiàn)并加入了afterNodeAccess來保證訪問順序谬莹，下面是get函數(shù)的具體實現(xiàn)：
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+雙向鏈表構(gòu)成的约素，并且依靠雙向鏈表保持順序届良。
accessorder模式下，一個節(jié)點被訪問之后就會將它從雙向鏈表的原位置刪除并放到最后圣猎，當(dāng)一個節(jié)點插入后，如果重寫了移除規(guī)則removeEldestEntry方法乞而，則移除雙向鏈表的首節(jié)點送悔，即最近最少使用的節(jié)點，以此來實現(xiàn)LRU爪模。
3欠啤、LruCache
3.1、LruCache構(gòu)造
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構(gòu)造屋灌。
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);
//如果已有緩存對象绑嘹，則緩存大小恢復(fù)到之前
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//entryRemoved()是個空方法，可以自行實現(xiàn)
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//調(diào)整緩存大小(關(guān)鍵方法)
trimToSize(maxSize);
return previous;
}
put()方法將鍵值對插入存儲到LinkedHashMap中疾呻，然后調(diào)用 trimToSize()方法，來判斷緩存是否已滿写半，如果滿了就是使用Lru算法進行刪除岸蜗。
trimToSize方法
public void trimToSize(int maxSize) {
//死循環(huán)
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為空璃岳，不需要再刪除緩存對象，跳出循環(huán)
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中隊頭的節(jié)點蜕该，即最近最少訪問的節(jié)點犁柜，直到緩存大小小于最大值。
3.2蛇损、get方法
public final V get(K key) {
//key為空拋出異常
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//獲取對應(yīng)的緩存對象
//get()方法會實現(xiàn)將訪問的元素更新到隊列頭部的功能
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
調(diào)用LinkedHashMap的get方法去獲取數(shù)據(jù)赁温，并維持訪問順序。
3.2淤齐、LruCache原理速記
LruCache內(nèi)部維護了一個LinkedHashMap股囊，并使用LinkedHashMap的accessorder模式去實現(xiàn)Lru算法，LinkedHashMap是Hashmap+雙向鏈表構(gòu)成的更啄，并且依靠雙向鏈表保持順序稚疹。accessorder模式下，一個節(jié)點被訪問之后就會將它從雙向鏈表的原位置刪除并放到最后祭务，當(dāng)一個節(jié)點插入后内狗，如果大于了LruCache的最大容量，就會移除雙向鏈表的首節(jié)點义锥，即最近最少使用的節(jié)點柳沙，以此來實現(xiàn)LRU。
4拌倍、LinkedHashMap實現(xiàn)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后的移除規(guī)則赂鲤，大于容量就刪除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);
}
}
