大綱
- linkedhashmap數(shù)據(jù)結(jié)構(gòu)原理
- linkedhashmap源碼分析
1.linkedhashmap數(shù)據(jù)結(jié)構(gòu)原理
- linkedhashmap繼承了hashmap的所有方法和屬性，在hashmap數(shù)據(jù)結(jié)構(gòu)，數(shù)組+單項(xiàng)鏈表+紅黑樹(shù)的原理上加上了雙向鏈表，通過(guò)雙向鏈表保證輸出的時(shí)候按照插入順序或者自己指定的順序進(jìn)行輸出。
2. linkedhashmap源碼分析
2.1 linkedhashmap成員變量參數(shù)
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
// 序列化唯一表示 UID
private static final long serialVersionUID = 3801124242820219131L;
// 雙向鏈表的頭節(jié)點(diǎn)
transient LinkedHashMapEntry<K,V> head;
// 雙向鏈表的尾節(jié)點(diǎn)
transient LinkedHashMapEntry<K,V> tail;
// 默認(rèn)是 false次兆，則迭代時(shí)輸出的順序是插入節(jié)點(diǎn)的順序栓辜。
// 若為 true颅悉，則輸出的順序是按照訪問(wèn)節(jié)點(diǎn)的順序（最近最少使用原則）嘀粱。
// accessOrder 為 true 時(shí)，可以在這基礎(chǔ)之上構(gòu)建一個(gè) LruCache爬迟。
final boolean accessOrder;
}
2.2 linkedhashmap構(gòu)建方法
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
...
/**
* 無(wú)參構(gòu)造函數(shù)
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 有參構(gòu)造函數(shù)
*
* @param initialCapacity 初始化時(shí)的容量
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 有參構(gòu)造函數(shù)
*
* @param initialCapacity 初始化時(shí)的容量
* @param loadFactor 擴(kuò)容的加載因子
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 有參構(gòu)造函數(shù)
*
* @param initialCapacity 初始化時(shí)的容量
* @param loadFactor 擴(kuò)容的加載因子
* @param accessOrder 迭代輸出節(jié)點(diǎn)的順序
*/
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
/**
* 有參構(gòu)造函數(shù)
*
* @param m 利用另一個(gè)Map 來(lái)構(gòu)建
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
// 批量插入一個(gè) map 中的所有數(shù)據(jù)到本集合中橘蜜。
putMapEntries(m, false);
}
...
}
2.3 .linkedhashmap的put()方法。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
當(dāng)前方法重寫了hashmap中的Node方法付呕，當(dāng)創(chuàng)建的時(shí)候會(huì)調(diào)用當(dāng)前方法中的類進(jìn)行創(chuàng)建计福，根據(jù)添加順序?yàn)殡p向鏈表添加位置。在hashmap的put()調(diào)用中會(huì)生成前后項(xiàng)指針徽职。當(dāng)前情況都是
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //???????
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
linkedhashmap直接使用了hashmap的put()方法象颖，因?yàn)槔^承了hashmap并且重寫了afterNodeInsertion()方法,在accessOrder為true的時(shí)候調(diào)用，會(huì)破壞原先的順序存儲(chǔ)姆钉，會(huì)把最近訪問(wèn)的放到鏈表的最后
/**
* 此方法的作用是將剛剛訪問(wèn)的節(jié)點(diǎn)e放到鏈表的尾端
*/
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
// accessOrder = true 時(shí) 訪問(wèn)節(jié)點(diǎn)后才需要置于尾端
// 如果e本身就在尾端说订，那就不需要操作
if (accessOrder && (last = tail) != e) {
// 記錄節(jié)點(diǎn)e、e的前驅(qū)潮瓶、e的后繼
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// b<->p <--> a
// 第一步：現(xiàn)將p.after置空
//斷開(kāi)p的后節(jié)點(diǎn)
p.after = null;
// 第二步：將e的前驅(qū).after 連接上e的后繼
if (b == null)
//如果沒(méi)有頭節(jié)點(diǎn) b<---> p
直接把head指向a
head = a;
else
//如果有前驅(qū)的話陶冷，把b< ---> a
b.after = a;
if (a != null)
// 如果a不等于空的話，把a(bǔ)指向b
a.before = b;
else
//如果a等于空的話毯辅，把last指向b.
last = b;
if (last == null)
//如果last 空把p插入到head節(jié)點(diǎn)埂伦。
head = p;
else {
//把p插入到最后節(jié)點(diǎn)。
p.before = last;
last.after = p;
}
//更新節(jié)點(diǎn)為尾節(jié)點(diǎn)悉罕。
tail = p;
// 鏈表結(jié)構(gòu)性調(diào)整赤屋，修改次數(shù)自增
++modCount;
}
}
2.4.linkedhashmap的remove方法
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // b是當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，a是后一個(gè)節(jié)點(diǎn)
p.before = p.after = null; //先斷開(kāi)當(dāng)前節(jié)點(diǎn)壁袄，把當(dāng)前節(jié)點(diǎn)對(duì)上一個(gè)和下一個(gè)節(jié)點(diǎn)的引用置為空
if (b == null) //當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)是null，說(shuō)明當(dāng)前節(jié)點(diǎn)是頭節(jié)點(diǎn)媚媒，那去掉當(dāng)前節(jié)點(diǎn)之后嗜逻，當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)成為了鏈第一個(gè)，
// 也就是頭節(jié)點(diǎn)缭召，當(dāng)然有可能a也是null栈顷，那整個(gè)鏈就是空鏈，這種寫法兼容了a也是null的情況
head = a;
else
b.after = a; //如果當(dāng)前節(jié)點(diǎn)不是頭節(jié)點(diǎn)嵌巷，直接去掉當(dāng)前節(jié)點(diǎn)萄凤，當(dāng)前節(jié)點(diǎn)的前一個(gè)和后一個(gè)連起來(lái)
if (a == null) //如果當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)是null，說(shuō)明當(dāng)前節(jié)點(diǎn)是尾節(jié)點(diǎn)搪哪，那把當(dāng)前節(jié)點(diǎn)去掉后靡努，當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)成為了鏈的最后一個(gè)節(jié)點(diǎn)尾節(jié)點(diǎn)。
tail = b;
else
a.before = b;//如果當(dāng)前節(jié)點(diǎn)不是尾節(jié)點(diǎn)，直接去掉當(dāng)前節(jié)點(diǎn)惑朦，當(dāng)前節(jié)點(diǎn)的前一個(gè)和后一個(gè)連起來(lái)
}
當(dāng)前方法總結(jié):當(dāng)前方法為刪除雙向鏈表的節(jié)點(diǎn)：有一下幾種情況: a 前一個(gè)節(jié)點(diǎn); b后一個(gè)節(jié)點(diǎn);p當(dāng)前節(jié)點(diǎn);
1.a<-->p --> a ;
- a<--> p <-->b --> a<-->b;
- p <--> b --> b;
2.5. linkedhashmap的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的區(qū)別在于，當(dāng)accessOrder為true的話漾月，會(huì)把當(dāng)前訪問(wèn)的節(jié)點(diǎn)插入到雙向鏈表的最后病梢。
喜歡的話點(diǎn)歌贊個(gè)??
