1.HashMap是一個數(shù)組＋鏈表/紅黑樹的結(jié)構(gòu)，數(shù)組的下標(biāo)在HashMap中稱為Bucket值雪猪，每個數(shù)組項對應(yīng)的是一個List
2.每個List中存放的是一個Entry對象诉稍，這個Entry對象是包含鍵和值的
HashMap類實現(xiàn)了諸多接口Map, Cloneable, Serializable
public class HashMap?extends AbstractMap?implements Map, Cloneable, Serializable {
常量
private static final long serialVersionUID =362498820763181265L;
? ? //最小容量
? ? static final int DEFAULT_INITIAL_CAPACITY =1 <<4; // aka 16
????//最大容量
? ? static final int MAXIMUM_CAPACITY =1 <<30;
????//重載因子
? ? static final float DEFAULT_LOAD_FACTOR =0.75f;
? ? //鏈表的最大長度曾雕，超過之后變?yōu)榧t黑樹
? ? static final int TREEIFY_THRESHOLD =8;
? //紅黑樹當(dāng)總的元素量小于6時踏施，變成鏈表
? ? static final int UNTREEIFY_THRESHOLD =6;
? ?//當(dāng)桶中的bin元素被樹化時叮叹，桶的最小容量必須大于4 * TREEIFY_THRESHOLD（樹化的長度）问畅，否則進(jìn)行resize擴(kuò)容娃属，
? ? static final int MIN_TREEIFY_CAPACITY =64;
內(nèi)部靜態(tài)類Node
?Basic hash bin node, used for most entries.
? ? static class Node implements Map.Entry<K,V> {
????????final int hash;
? ? ? ? final K key;
? ? ? ? V value;
? ? ? ? Node<K,V> next;
? ? ? ? Node(int hash, K key, V value, Node<K,V> next) {
? ? ? ? ? ? //哈希值
? ? ? ? ? ? ?this.hash = hash;
? ? ? ? ? ? this.key = key;
? ? ? ? ? ? this.value = value;
? ? ? ? ? ? this.next = next;
? ? ? ? }
????public final K getKey()? ? ? ? {return key; }
????public final V getValue()? ? ? {return value; }
????public final String toString() {return key +"=" +value; }
????public final int hashCode() {
????????return Objects.hashCode(key) ^ Objects.hashCode(value);
? ? ? ? }
????public final V setValue(V newValue) {
????????V oldValue =value;
? ? ? ? ? ? value = newValue;
? ? ? ? ? ? return oldValue;
? ? ? ? }
????public final boolean equals(Object o) {
????????????if (o == this)
????????????????????return true;
? ? ? ? ? ? if (o instanceof Map.Entry) {
????????????????Map.Entry<?,?> e = (Map.Entry<?,?>)o;
? ? ? ? ? ? ? ? if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
????????????????????????return true;
? ? ? ? ? ? }
????????????return false;
? ? ? ? }
}
靜態(tài)工具
/* ---------------- Static utilities -------------- */
? ? //哈希化
? ? static final int hash(Object key) {
????????int h;
? ? //^優(yōu)先級高于三目運算符护姆，>>>無符號右移16位
? ? //如果該類有hashCode的實現(xiàn)會優(yōu)先調(diào)用自身的hashCode方法矾端，沒有的話將調(diào)用Object的hashCode方法；
? ? ? ? return (key ==null) ? 0 : (h = key.hashCode()) ^ (h >>>16);
? ? }
比較方法
? ? static Class<?> comparableClassFor(Object x) {
????????if (x instanceof Comparable) {
????????????Class c; Type[] ts, as; Type t; ParameterizedType p;
? ? ? ? ? ? if ((c = x.getClass()) == String.class) // bypass checks
? ? ? ? ? ? ? ? return c;
? ? ? ? ? ? if ((ts = c.getGenericInterfaces()) !=null) {
????????????????????????for (int i = 0; i < ts.length; ++i) {
????????????????????????????????if (((t = ts[i])instanceof ParameterizedType) &&
????????????????????????????????????((p = (ParameterizedType)t).getRawType() == Comparable.class) ????????????????????????????????&& (as = p.getActualTypeArguments()) !=null
????????????????????????????????&& as.length ==1
????????????????????????????????&& as[0] == c) // type arg is c
? ? ? ? ? ? ? ? ? ? ? ? return c;
? ? ? ? ? ? ? ? }
????????????}
????????}
????????return null;
? ? }
可比較的
? ? @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
????//原文是/rawtypes , unchecked/
? ? static int compareComparables(Class kc, Object k, Object x) {
//邏輯運算符高于三目運算符
????????????return (x ==null || x.getClass() != kc ?0 :
????????????????????((Comparable)k).compareTo(x));
? ? }
為給定目標(biāo)容量卵皂，返回一個容器的尺寸
? ? static final int tableSizeFor(int cap) {
????????int n = cap -1;
? ? ? ? n |= n >>>1;
? ? ? ? n |= n >>>2;
? ? ? ? n |= n >>>4;
? ? ? ? n |= n >>>8;
? ? ? ? n |= n >>>16;
? ? ? ? return (n <0) ?1 : (n >=MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : n +1;
? ? }
/* ---------------- Fields -------------- */
屬性
? ? transient Node[] table; //元素集合
? ? transient Set<Map.Entry<K,V>> entrySet; //緩存的Map.Entry集合
? ? transient int size; //大小
? ? transient int modCount; //?HashMap被改變的次數(shù)?
? ? ?//HashMap的閾值秩铆，用于判斷是否需要調(diào)整HashMap的容量（threshold = 容量*加載因子）?
? ?int threshold;
? ?final float loadFactor; //?加載因子實際大小?
? ? /* ---------------- Public operations -------------- */
構(gòu)造器
????//帶初始化大小和負(fù)載因子的構(gòu)造器
? ? public HashMap(int initialCapacity, float loadFactor) {
????????????if (initialCapacity <0)
????????????????????throw new IllegalArgumentException("Illegal initial capacity: " +
????????????????????????initialCapacity);
? ? ? ? ????if (initialCapacity >MAXIMUM_CAPACITY)
? ? ? ? ? ? ? ? ? ? initialCapacity =MAXIMUM_CAPACITY;
? ? ? ????? if (loadFactor <=0 || Float.isNaN(loadFactor))
????????????????????????throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
? ? ? ? ????this.loadFactor = loadFactor;
? ? ? ? ????this.threshold =tableSizeFor(initialCapacity);//大小為2的次冪
? ? }
? //不帶負(fù)載因子的構(gòu)造器，默認(rèn)為0.75
? ? public HashMap(int initialCapacity) {
????????this(initialCapacity, DEFAULT_LOAD_FACTOR);
? ? }
//構(gòu)造一個空的HashMap對象灯变，默認(rèn)打下為16殴玛，負(fù)載因子0.75
? ? public HashMap() {
????????????this.loadFactor =DEFAULT_LOAD_FACTOR; // all other fields defaulted
? ? }
//通過Map構(gòu)造一個HashMap， 負(fù)載因子默認(rèn)為0.75添祸，通過?putMapEntries方法族阅，將Map中的值放入HashMap當(dāng)中
public HashMap(Map<? extends K, ? extends V>? m) {
????????this.loadFactor =DEFAULT_LOAD_FACTOR;
? ? ? ? putMapEntries(m, false);
? ? }
//Implements Map.putAll and Map constructor
? ? final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
? ? ? ? ?int s = m.size();
? ? ? ? if (s >0) {//判斷map的大小
????????????????if (table ==null) {// pre-size，判斷hashMap的初始大小
? ? ? ? ? ? ? ?????float ft = ((float)s /loadFactor) +1.0F; //判斷這個創(chuàng)建數(shù)組的大小
? ? ? ? ? ? ? ????? int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft? : ????????????????????????????MAXIMUM_CAPACITY);
? ? ? ? ? ? ? ? ????if (t >threshold)//設(shè)置容器大小 膝捞，?threshold初始為0
????????????????????????????threshold = tableSizeFor(t);
? ? ? ? ? ? ????} else if (s? > threshold) //若大于現(xiàn)有長度將擴(kuò)容
? ? ? ? ? ? ? ? ? ?resize();//擴(kuò)容
? ? ? ? ? ? for (Map.Entry e : m.entrySet()) {
????????????????K key = e.getKey();
? ? ? ? ? ? ? ? V value = e.getValue();
? ? ? ? ? ? ? ? putVal(hash(key), key, value, false, evict);
? ? ? ? ? ? }
????}
}
獲取當(dāng)前的存儲key-value的數(shù)量
? ? public int size() {
????????????return size;
? ? }
判斷是否為空
? ? public boolean isEmpty() {
????????????return size ==0;
? ? }
按照key獲取value
? ? public V get(Object key) {
????????Node<K,V> e;
? ? ? ? return (e = getNode(hash(key), key)) ==null ?null : e.value;
? ? }
通過key和hashCode獲取Node
? ? final Node<K,V> getNode(int hash, Object key) {
????????Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
? ? ? ? //hash是key哈咸沟叮化的int值，與數(shù)組的最大下標(biāo)進(jìn)行安位與運算蔬咬，得出實際的位置
? ? ? ? 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;
? ? ? ? ? ? //若第一個并不是所要找的元素鲤遥，則進(jìn)行分類查找（樹/鏈表）
? ? ? ? ? ? if ((e = first.next) !=null) {
? ? ? ? ? ? ? ? //樹（紅黑樹）
????????????????if (first instanceof TreeNode)
????????????????????????????return ((TreeNode<K,V>)first).getTreeNode(hash, key);
? ? ? ? ? ? ????//鏈表
? ? ? ? ? ? ? ?do {
????????????????????????if (e.hash == hash &&
????????????????????????????????????????((k = e.key) == key || (key !=null && key.equals(k))))
????????????????????????????????????return e;
? ? ? ? ? ? ? ? }while ((e = e.next) !=null);
? ? ? ? ? ? }
????????}
????????return null;
? ? }
判斷是否包含某個key
? ? public boolean containsKey(Object key) {
????????return getNode(hash(key), key) !=null;
? ? }
放入Map
? ? public V put(K key, V value) {
? ? ? ? ? ? //參數(shù)：hashCode，key林艘， value盖奈，?onlyIfAbsent（如果原來的key不存在創(chuàng)建，存在則不做任何操作狐援， false默認(rèn)（即替代原有value）钢坦，true）， evict（）
????????????return putVal(hash(key), key, value, false, true);
? ? }
插入HashMap
參數(shù)：hashCode啥酱，key爹凹， value，?onlyIfAbsent（如果原來的key不存在創(chuàng)建镶殷，存在則不做任何操作禾酱， false默認(rèn)（即替代原有value），true）， evict（用于LinkedHashMap中的尾部操作颤陶，這里沒有實際意義颗管。）
? ? final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
????????Node<K,V>[] tab; Node<K,V> p; int n, i;
????????//判斷長度是否為0，若為0滓走，則初始化
? ? ? ? if ((tab =table) ==null || (n = tab.length) ==0)
????????????????????n = (tab = resize()).length;
????????//獲取Node[] 數(shù)組的該位置是否有值垦江，無值直接放入
? ? ? ? if ((p = tab[i = (n -1) & hash]) ==null)
? ? ? ? ? ? ? ? ? ?tab[i] = newNode(hash, key, value, null);
? ? ? ?//有值的話，則添加到鏈表或者樹上
? ? ? ? else {
????????????Node<K,V> e; K k;
????????????//傳入的hashCode和key都與現(xiàn)有的節(jié)點相同
? ? ? ? ? ? if (p.hash == hash &&((k = p.key) == key || (key !=null && key.equals(k))))
????????????????????e = p;
???????????//傳入的hashCode和key都與現(xiàn)有的節(jié)點不相同搅方，則分為兩種情況比吭，樹/鏈表
? ? ? ? ? ?//樹
? ? ? ? ? ? else if (p instanceof TreeNode)
? ? ? ? ? ? ? ? ? ? //插入一個樹節(jié)點
????????????????????e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
? ? ? ? ? ? //鏈表
? ? ? ? ? ? else {
????????????????for (int binCount =0; ; ++binCount) {
? ? ? ? ? ? ? ? ? ? //下一個節(jié)點為空則創(chuàng)建
????????????????????if ((e = p.next) ==null) {
? ? ? ? ? ? ? ? ? ? ? ? //插入一個鏈表節(jié)點
????????????????????????p.next = newNode(hash, key, value, null);
? ? ? ? ? ? ? ? ? ? ? ? //判斷添加后鏈表的長度，超過8則轉(zhuǎn)換為紅黑樹
? ? ? ? ? ? ? ? ? ? ? ? if (binCount >=TREEIFY_THRESHOLD -1)// -1 for 1st
? ? ? ? ? ? ? ? ? ? ? ? ? ? //轉(zhuǎn)換為紅黑樹
? ? ? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash);
? ? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ?//哈涎化找到該節(jié)點梗逮，則返回e
????????????????????if (e.hash == hash &&
????????????????????????????((k = e.key) == key || (key !=null && key.equals(k))))
????????????????????????????break;
? ? ? ? ? ? ? ? //將當(dāng)前節(jié)點在付給p项秉，繼續(xù)循環(huán)
? ? ? ? ? ? ? ? ? ? p = e;
? ? ? ? ? ? ? ? }
????????}
????????if (e !=null) {// existing mapping for key
? ? ? ? ? ? ? ? V oldValue = e.value;
????????????????//判斷onlyIfAbsent绣溜，改寫方式
? ? ? ? ? ? ? ? if (!onlyIfAbsent || oldValue ==null)
????????????????????????e.value = value;
? ? ? ? ? ? ? ? afterNodeAccess(e);//插入節(jié)點后，允許的回調(diào)方法娄蔼，可重寫
? ? ? ? ? ? ? ? return oldValue;
? ? ? ? ? ? }
????????}
????????++modCount;//結(jié)構(gòu)被更改的次數(shù)
? ? ? ? //當(dāng)插入節(jié)點后怖喻，根據(jù)負(fù)載因子判斷是否擴(kuò)容
? ? ? ? if (++size >threshold)
????????????????resize();
? ? ? ? afterNodeInsertion(evict);//結(jié)構(gòu)調(diào)整后，允許的回調(diào)函數(shù)
????????return null;
? ? }
重新定義hashMap的大小岁诉，初始化或者2次冪的方式擴(kuò)容
? ? final Node<K,V>[] resize() {
????????Node<K,V>[] oldTab =table;
? ? ? ? int oldCap = (oldTab ==null) ?0 : oldTab.length;
? ? ? ? int oldThr = threshold;
? ? ? ? int newCap, newThr =0;
????????//原本不為空锚沸，即為擴(kuò)容
? ? ? ? if (oldCap >0) {
? ? ? ? ? ? ? ? //達(dá)到最大值
????????????????if (oldCap >=MAXIMUM_CAPACITY) {
????????????????????????threshold = Integer.MAX_VALUE;
? ? ? ? ? ? ? ? ????????return oldTab;
? ? ? ? ? ? ????}
? ? ? ????????? //按照2次冪方式擴(kuò)容
????????????????else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY
????????????????????????&& oldCap >=DEFAULT_INITIAL_CAPACITY)
????????????????????????newThr = oldThr <<1; // double threshold
? ? ? ? }
? ? ? ? ? ? //如果有容量限制則為原值
????????????else if (oldThr >0)// initial capacity was placed in threshold
? ? ? ? ? ? ????????newCap = oldThr;
????????????//沒有固定參數(shù)，設(shè)置為默認(rèn)值
? ? ? ? ? ? ?else {// zero initial threshold signifies using defaults
? ? ? ? ? ? ????????????newCap =DEFAULT_INITIAL_CAPACITY;//16
? ? ? ? ? ? ????????????newThr = (int)(DEFAULT_LOAD_FACTOR ????????????????????????????????????????????????* DEFAULT_INITIAL_CAPACITY);
? ? ? ? }
????????//確定新的存儲量是多少
????????if (newThr ==0) {
? ? ? ? ? ? ? ? ? float ft = (float)newCap *loadFactor;
? ? ? ? ? ? ? ? ? newThr = (newCap < MAXIMUM_CAPACITY && ft < ????????????????????????????????(float)MAXIMUM_CAPACITY??(int)ft : Integer.MAX_VALUE);
? ? ? ? }
? ? ? ? //新的閥值
????????threshold = newThr;
? ? ? ? @SuppressWarnings({"rawtypes","unchecked"})
????????//創(chuàng)建一個新的數(shù)組
????????Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
? ? ? ? table = newTab;
? ? ? ? if (oldTab !=null) {
????????????for (int j =0; j < oldCap; ++j) {
????????????????Node e;
? ? ? ? ? ? ? ? if ((e = oldTab[j]) !=null) {
????????????????????oldTab[j] =null;
? ? ? ? ? ? ? ? ? ? //如果沒有鏈表和樹直接付值
? ? ? ? ? ? ? ? ? ? if (e.next ==null)
????????????????????????newTab[e.hash & (newCap -1)] = e;
? ? ? ? ? ? ? ? ? ? //如果是紅黑樹
? ? ? ? ? ? ? ? ? ? else if (e instanceof TreeNode)
? ? ? ? ? ? ? ? ? ? ? ? //將樹拆分成高低兩個樹涕癣，重新進(jìn)行哈匣冢化，然后put
????????????????????????((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
????????????????????//如果是鏈表的話
? ? ? ? ? ? ? ? ? ? else {// preserve order
? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> loHead =null, loTail =null;
? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> hiHead =null, hiTail =null;
? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> next;
? ? ? ? ? ? ? ? ? ? ? ? do {
????????????????????????????????next = e.next;
? ? ? ? ? ? ? ? ? ? ? ? ? ? if ((e.hash & oldCap) ==0) {
????????????????????????????????????if (loTail ==null)? loHead = e;
????????????????????????????????????else? loTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if (hiTail ==null)? ?hiHead = e;
????????????????????????????????????else hiTail.next = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hiTail = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????}while ((e = next) !=null);
????????????????//低位的放在原位
? ? ? ? ? ? ? ? ? ?if (loTail !=null) {
? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next =null;
? ? ? ? ? ? ? ? ? ? ? ? ? newTab[j] = loHead;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? //將拆出來的鏈表或者樹的節(jié)點放到新的擴(kuò)容出來的區(qū)域
????????????????????if (hiTail !=null) {
????????????????????????????hiTail.next =null;
? ? ? ? ? ? ? ? ? ? ? ? ? ? newTab[j + oldCap] = hiHead;
? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????}
????????????????}
? ? ? ? ? ? ?}
????????}
????????return newTab;
? ? }
鏈表長度超過8坠韩，將調(diào)整鏈表為樹
? ? final void treeifyBin(Node<K,V>[] tab, int hash) {
????????int n, index; Node e;
? ? ? ? //當(dāng)有樹存在時距潘，最小容量必須大于4*樹化閥值（8）。默認(rèn)64
? ? ? ? if (tab ==null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
? ? ? ? else if ((e = tab[index = (n -1) & hash]) !=null) {
????????????TreeNode<K,V> hd =null, tl =null;
? ? ? ? //循環(huán)替換
? ? ? ? ? ? do {
? ? ? ? ? ? ? ? //將node節(jié)點化成TreeNode節(jié)點
????????????????TreeNode<K,V> p = replacementTreeNode(e, null);
? ? ? ? ? ? ? ? //設(shè)置根節(jié)點
? ? ? ? ? ? ? ? if (tl ==null)
????????????????????hd = p;
? ? ? ? ? ????? //設(shè)置父節(jié)點
? ? ? ? ? ? ? ? else {
????????????????????p.prev = tl;
? ? ? ? ? ? ? ? ? ? tl.next = p;
? ? ? ? ? ? ? ? }
????????????????tl = p;
? ? ? ? ? ? }while ((e = e.next) !=null);
? ? ? ? ????//將頭節(jié)點放到整個數(shù)組當(dāng)中
? ? ? ? ? ? if ((tab[index] = hd) !=null)
????????????????//從頭節(jié)點開始樹化
????????????????hd.treeify(tab);
? ? ? ? }
}
將Map插入全部
? ? public void putAll(Map m) {
????????????putMapEntries(m, true);
? ? }
刪除節(jié)點
? ? public V remove(Object key) {
????????????????Node e;
? ? ? ????????? return (e = removeNode(hash(key), key, null, false, true)) ==null
????????????????????????? null : e.value;
? ? }
刪除節(jié)點
參數(shù)int hash（哈希值）, Object key, Object value（一般為nu l l）,? boolean matchValue（是否value也一致時在刪除只搁，默認(rèn)為false）, boolean movable（是否移動其他節(jié)點音比，在樹的時候， 默認(rèn)為true）
? ? final Node<K,V> removeNode(int hash, Object key, Object value,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? boolean matchValue, boolean movable) {
? ? ? ? ?Node<K,V>[] tab; Node<K,V> p; int n, index;
? ? ? ? //查找到要刪除的桶
? ? ? ? if ((tab =table) !=null && (n = tab.length) >0 &&?
????????????????????????????????????????????(p = tab[index = (n -1) & hash]) !=null) {
????????????????Node<K氢惋，V> node =null, e; K k; V v;
? ? ? ? ? ? ? ? //查找節(jié)點
????????????????//沒有樹或鏈表
? ? ? ? ? ????? if (p.hash == hash &&((k = p.key) == key || (key !=null && key.equals(k))))
???????????????????????node = p;
? ? ? ? ? ? ? ? //有樹或鏈表
? ? ? ? ? ? ????else if ((e = p.next) !=null) {
? ? ? ? ? ? ? ? ? ? //樹
????????????????????if (p instanceof TreeNode)
????????????????????????node = ((TreeNode)p).getTreeNode(hash, key);
? ? ? ? ? ? ? ? ? ? //鏈表
? ? ? ? ? ? ? ? ? ? ?else {
????????????????????????????do {
????????????????????????????????????if (e.hash == hash && ((k = e.key) == key ||
????????????????????????????????????????????????????(key !=null && key.equals(k)))) {
????????????????????????????????????????????????node = e;
????????????????????????????????????????????????break;
? ? ? ? ? ? ? ? ? ? ? ????? ????????}
????????????????????????????????????p = e;
? ? ? ? ? ? ? ? ? ????????? ????}while ((e = e.next) !=null);
? ? ? ? ? ? ? ????? }
????????}
????????//獲取到相應(yīng)的node節(jié)點
????????if (node !=null && (!matchValue || (v = node.value) == value ||
???????????????????????????????????????????????????(value !=null && value.equals(v)))) {
? ? ? ? ? ? ? ? //樹
????????????????if (node instanceof TreeNode)
????????????????????????((TreeNode)node).removeTreeNode(this, tab, movable);
? ? ? ? ? ? //鏈表
????????????//頭節(jié)點
? ? ? ? ? ? ? ? else if (node == p)
????????????????????????tab[index] = node.next;
? ? ? ? ? ? //非頭節(jié)點
????????????????else
? ? ? ? ? ? ? ? ? ? p.next = node.next;
? ? ? ? ? ? ? ? ++modCount;
? ? ? ? ? ? ? ? --size;
? ? ? ? ? ? ? ? afterNodeRemoval(node);
? ? ? ? ? ? ? ? return node;
? ? ? ? ? ? }
????????}
????????return null;
? ? }
清除方法
? ? public void clear() {
? ? ? ? ?Node<K,V>[] tab;
? ? ? ? modCount++;
? ? ? ? if ((tab =table) !=null &&size >0) {
? ? ? ? ? ? ? ? size =0;
? ? ? ? ? ? ????for (int i =0; i < tab.length; ++i)
????????????????????tab[i] =null;
? ? ? ? }
}
是否包含值
? ? public boolean containsValue(Object value) {
????????????Node[] tab; V v;
? ? ? ? ????if ((tab =table) !=null &&size >0) {
????????????????????for (int i =0; i < tab.length; ++i) {
????????????????????????for (Node e = tab[i]; e !=null; e = e.next) {
????????????????????????????if ((v = e.value) == value ||(value !=null && value.equals(v)))
????????????????????????????????return true;
? ? ? ? ? ? ? ????????? ????}
????????????????????}
????????????}
????????return false;
? ? }
key的集合
? ? public SetkeySet() {
????????????Set ks =keySet;
? ? ? ? ? ? if (ks ==null) {
? ? ? ? ? ? ?????ks =new KeySet();
? ? ? ? ? ? ????keySet = ks;
? ? ? ????? }
????????return ks;
? ? }
內(nèi)部類KeySet
final class KeySet extends AbstractSet<K> {
????????public final int size()? ? ? ? ? ? ? ? {return size; }
????????public final void clear()? ? ? ? ? ? ? { HashMap.this.clear(); }
????????public final Iterator<K> iterator()? ? {return new KeyIterator(); }
????????public final boolean contains(Object o) {return containsKey(o); }
????????public final boolean remove(Object key) {
????????????????return removeNode(hash(key), key, null, false, true) !=null;
? ? ? ? }
????????//Spliterator就是為了并行遍歷元素而設(shè)計的一個迭代器洞翩，對于迭代器中數(shù)據(jù)進(jìn)行分割
????????public final Spliterator<K> spliterator() {
????????????????return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
? ? ? ? }
? ? //遍歷
????public final void forEach(Consumer action) {
????????????Node[] tab;
? ? ? ? ? ? if (action ==null)
????????????????throw new NullPointerException();
? ? ? ? ? ? if (size >0 && (tab =table) !=null) {
????????????????int mc =modCount;
? ? ? ? ? ? ? ? for (int i =0; i < tab.length; ++i) {
????????????????????????for (Node e = tab[i]; e !=null; e = e.next)
????????????????????????????????action.accept(e.key);
? ? ? ? ? ? ? ? }
????????????????if (modCount != mc)
????????????????????????throw new ConcurrentModificationException();
? ? ? ? ? ? }
????????}
}
獲取全部的值
? ? public Collection<V> values() {
????????Collection vs =values;
? ? ? ? if (vs ==null) {
????????????vs =new Values();
? ? ? ? ? ? values = vs;
? ? ? ? }
????????return vs;
? ? }
Value的集合類
final class Values extends AbstractCollection<V> {
????public final int size()? ? ? ? ? ? ? ? {return size; }
????public final void clear()? ? ? ? ? ? ? { HashMap.this.clear(); }
????public final Iterator<V> iterator()? ? {return new ValueIterator(); }
????public final boolean contains(Object o) {return containsValue(o); }
????public final Spliterator<V> spliterator() {
????????????return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
? ? ? ? }
????????public final void forEach(Consumer<? super V> action) {
????????????Node<K,V>[] tab;
? ? ? ? ? ? if (action ==null)
????????????????throw new NullPointerException();
? ? ? ? ? ? if (size >0 && (tab =table) !=null) {
????????????????int mc =modCount;
? ? ? ? ? ? ? ? for (int i =0; i < tab.length; ++i) {
????????????????????for (Node e = tab[i]; e !=null; e = e.next)
????????????????????????action.accept(e.value);
? ? ? ? ? ? ? ? }
????????????????if (modCount != mc)
????????????????????throw new ConcurrentModificationException();
? ? ? ? ? ? }
????}
}
set集合
? ? public Set<Map.Entry<K,V>> entrySet() {
????????Set<Map.Entry<K,V>> es;
? ? ? ? return (es =entrySet) ==null ? (entrySet =new EntrySet()) : es;
? ? }
內(nèi)部類EntrySet
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
????public final int size()? ? ? ? ? ? ? ? {return size; }
????public final void clear()? ? ? ? ? ? ? { HashMap.this.clear(); }
????public final Iterator<Map.Entry<K,V>>iterator() {
????????????return new EntryIterator();
? ? }
????public final boolean contains(Object o) {
????????????if (!(oinstanceof Map.Entry))
????????????????????return false;
? ? ? ? ? ? Map.Entry<?,?> e = (Map.Entry<?,?>) o;
? ? ? ? ? ? Object key = e.getKey();
? ? ? ? ? ? Node<K,V> candidate = getNode(hash(key), key);
? ? ? ? ? ? return candidate !=null && candidate.equals(e);
? ? ? ? }
????public final boolean remove(Object o) {
????????if (o instanceof Map.Entry) {
????????????????Map.Entry<?,?> e = (Map.Entry<?,?>) o;
? ? ? ? ? ? ? ? Object key = e.getKey();
? ? ? ? ? ? ? ? Object value = e.getValue();
? ? ? ? ? ? ? ? return removeNode(hash(key), key, value, true, true) !=null;
? ? ? ? ? ? }
????????????return false;
? ? ? ? }
????????public final Spliterator<Map.Entry<K,V>>spliterator() {
????????????return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
? ? ? ? }
public final void forEach(Consumer> action) {
????????????Node<K,V>[] tab;
? ? ? ? ? ? if (action ==null)
????????????????????throw new NullPointerException();
? ? ? ? ? ? if (size >0 && (tab =table) !=null) {
????????????????int mc =modCount;
? ? ? ? ? ? ? ? for (int i =0; i < tab.length; ++i) {
????????????????????for (Node e = tab[i]; e !=null; e = e.next)
????????????????????????action.accept(e);
? ? ? ? ? ? ? ? }
????????????????if (modCount != mc)
????????????????throw new ConcurrentModificationException();
? ? ? ? ? ? }
? ? ? ?}
}
獲取默認(rèn)值
? ? public V getOrDefault(Object key, V defaultValue) {
? ? ? ? ?Node e;
? ? ? ? return (e = getNode(hash(key), key)) ==null ? defaultValue : e.value;
? ? }
key存在則不插入
? ? public V putIfAbsent(K key, V value) {
????????return putVal(hash(key), key, value, true, true);
? ? }
刪除節(jié)點
? ? public boolean remove(Object key, Object value) {
????????????return removeNode(hash(key), key, value, true, true) !=null;
? ? }
替換舊值
? ? public boolean replace(K key, V oldValue, V newValue) {
? ? ? ? ? ?Node<K,V> e; V v;
? ? ? ? if ((e = getNode(hash(key), key)) !=null &&
????????????????????((v = e.value) == oldValue || (v !=null && v.equals(oldValue)))) {
????????????????e.value = newValue;
? ? ? ? ? ? ????fterNodeAccess(e);
????????????????return true;
? ? ? ? }
? ? ? ? ? ?return false;
? ? }
替換舊值
? ? public V replace(K key, V value) {
? ? ? ? ?Node<K,V> e;
? ? ? ? if ((e = getNode(hash(key), key)) !=null) {
????????????V oldValue = e.value;
? ? ? ? ? ? e.value = value;
? ? ? ? ? ? afterNodeAccess(e);
? ? ? ? ? ? return oldValue;
? ? ? ? }
????????return null;
? ? }
compute()是java8在Map中新增的一個方法，其作用是把remappingFunction的計算結(jié)果關(guān)聯(lián)到key上（即remappingFunction返回值作為新value）
?V computeIfAbsent根據(jù)key做匹配Node焰望，（匹配不到則新建然后重排）如果Node有value骚亿，則直接返回oldValue，如果沒有value則根據(jù)Function接口的apply方法獲取value熊赖，返回value循未。Function接口的apply的入?yún)閗ey，調(diào)用computeIfAbsent時重寫Function接口可以根據(jù)key進(jìn)行邏輯處理，apply的返回值即為要存儲的value的妖。
? ? public V computeIfAbsent(K key,
? ? ? ? ? ? ? ? ? ? ? ? ? ?Function mappingFunction<? super K, ? extends V> mappingFunction) {
? ? ? ? ? if (mappingFunction ==null)
????????????????????????????????????throw new NullPointerException();
? ? ? ? ????int hash =hash(key);
? ? ? ? ????Node<K,V>[] tab; Node<K,V> first; int n, i;
? ? ? ????? int binCount =0;
? ? ? ????? TreeNode<K,V> t =null;
? ? ? ????? Node<K,V> old =null;
? ? ? ? ????if (size >threshold || (tab =table) ==null || (n = tab.length) ==0)
????????????????n = (tab = resize()).length;
? ? ? ? ????if ((first = tab[i = (n -1) & hash]) !=null) {
????????????????if (firstinstanceof TreeNode)
????????????????????old = (t = (TreeNode)first).getTreeNode(hash, key);
? ? ? ? ? ? ????else {
????????????????????????Node e = first; K k;
? ? ? ? ? ? ? ? ? ? ? ? do {
????????????????????????????if (e.hash == hash &&((k = e.key) == key || (key !=null && ????????????????????????????????????key.equals(k)))) {
????????????????????????????????????old = e;
????????????????????????????????????break;
? ? ? ? ? ? ? ? ? ? ????????????}
????????????????????????????????++binCount;
? ? ? ? ? ? ? ????????????? }while ((e = e.next) !=null);
? ? ? ? ? ????????? }
????????????????????V oldValue;
? ? ? ? ? ????????? if (old !=null && (oldValue = old.value) !=null) {
????????????????????????afterNodeAccess(old);
? ? ? ? ? ? ? ? ????????return oldValue;
? ? ? ? ? ? ????????}
????????????????}
????????????????V v = mappingFunction.apply(key);
? ? ? ? ????????if (v ==null) {
????????????????????????return null;
? ? ? ????????????? }else if (old !=null) {
????????????????????????old.value = v;
? ? ? ? ? ? ????????????afterNodeAccess(old);
? ? ? ? ? ? ????????????return v;
? ? ? ? ????????????}
????????????????????else if (t !=null)
????????????????????????t.putTreeVal(this, tab, hash, key, v);
? ? ? ????????????? else {
????????????????????????tab[i] = newNode(hash, key, v, first);
? ? ? ? ? ????????????? if (binCount >=TREEIFY_THRESHOLD -1)
????????????????????????????????treeifyBin(tab, hash);
? ? ? ? ? ? ?}
? ? ? ? ? ++modCount;
? ? ? ? ++size;
? ? ? ? afterNodeInsertion(true);
? ? ? ? return v;
? ? }
V computeIfPresent(K key,BiFunction remappingFunction)：根據(jù)key做匹配绣檬，如果匹配不上則返回null,匹配上根據(jù)BiFunction的apply方法獲取value，返回value嫂粟。BiFunction接口的apply的入?yún)閗ey娇未、oldValue，調(diào)用computeIfPresent時重寫Function接口可以根據(jù)key和oldValue進(jìn)行邏輯處理星虹，apply的返回值如果為null則刪除該節(jié)點零抬，否則即為要存儲的value。
public V computeIfPresent(K key,
? ? ? ? ? ? ? ? ? ? BiFunction<? super K, ? super V, ? super V> remappingFunction) {
????????????if (remappingFunction ==null)
????????????????????????throw new NullPointerException();
? ? ? ????? Node<K,V> e; V oldValue;
? ? ? ????? int hash =hash(key);
? ? ? ?????if ((e = getNode(hash, key)) !=null &&(oldValue = e.value) !=null) {
????????????????V v = remappingFunction.apply(key, oldValue);
? ? ? ? ? ? ????if (v !=null) {
????????????????????e.value = v;
? ? ? ? ? ? ? ? ????afterNodeAccess(e);
? ? ? ? ? ? ? ????? return v;
? ? ? ? ? ? }
????????????else
? ? ? ? ? ? ? ? removeNode(hash, key, null, false, true);
? ? ? ????? }
????????return null;
? ? }
V compute(K key,BiFunction remappingFunction)：根據(jù)key做匹配宽涌，根據(jù)BiFunction的apply返回做存儲的value平夜。匹配到Node做value替換，匹配不到新增node卸亮。apply的返回值如果為null則刪除該節(jié)點忽妒，否則即為要存儲的value。
? ? public V compute(K key,
? ? ? ? ? ? ? ? ? ? BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
????????????if (remappingFunction ==null)
????????????????????????throw new NullPointerException();
? ? ? ? ? ? ? int hash =hash(key);
? ? ? ? ? ? ? Node<K,V>[] tab; Node<K,V> first; int n, i;
? ? ? ? ? ? ? ?int binCount =0;
? ? ? ? ????????TreeNode<K,V> t =null;
? ? ? ????????? Node<K,V> old =null;
? ? ? ? ????????if (size >threshold || (tab =table) ==null || (n = tab.length) ==0)
????????????????????????????n = (tab = resize()).length;
? ? ? ?????????if ((first = tab[i = (n -1) & hash]) !=null) {
????????????????????if (first instanceof TreeNode)
????????????????????????old = (t = (TreeNode)first).getTreeNode(hash, key);
? ? ? ? ? ????????? else {
????????????????????????????Node e = first; K k;
? ? ? ? ? ? ? ????????????? do {
????????????????????????????????????if (e.hash == hash &&
????????????????????????????????????????????????((k = e.key) == key || (key !=null && key.equals(k)))) {
????????????????????????????????????????????????old = e;
????????????????????????????????????????????????break;
? ? ? ? ? ? ? ? ? ? ????????????????????????}
????????????????????????????????????????++binCount;
? ? ? ? ? ? ? ????????????????????? }while ((e = e.next) !=null);
? ? ? ? ? ????????????????? }
????????????????????}
? ? ? ? ? V oldValue = (old ==null) ?null : old.value;
? ? ? ? V v = remappingFunction.apply(key, oldValue);
? ? ? ? if (old !=null) {
????????????????if (v !=null) {
????????????????????old.value = v;
? ? ? ? ? ? ? ????? afterNodeAccess(old);
? ? ? ? ? ? ????}
????????????????else? removeNode(hash, key, null, false, true);
? ? ? ? ? ? }
????????????else if (v !=null) {
????????????????if (t !=null)
????????????????????????t.putTreeVal(this, tab, hash, key, v);
? ? ? ? ? ? ????????else {
????????????????????????????tab[i] = newNode(hash, key, v, first);
? ? ? ? ? ? ? ????????????? if (binCount >=TREEIFY_THRESHOLD -1)
????????????????????????????????????treeifyBin(tab, hash);
? ? ? ? ? ?????????}
? ? ? ? ? ? ? ++modCount;
? ? ? ? ? ? ++size;
? ? ? ? ? ? afterNodeInsertion(true);
? ? ? ? }
????????return v;
? ? }
?V merge(K key, V value,BiFunction remappingFunction)：功能大部分與compute相同兼贸，不同之處在于BiFunction中apply的參數(shù)段直，入?yún)閛ldValue、value溶诞，調(diào)用merge時根據(jù)兩個value進(jìn)行邏輯處理并返回value鸯檬。
? ? public V merge(K key, V value,
? ? ? ? ? ? ? ? ? BiFunction remappingFunction) {
????????????if (value ==null)
????????????????????throw new NullPointerException();
? ? ? ????? if (remappingFunction ==null)
????????????????????????throw new NullPointerException();
? ? ? ????? int hash =hash(key);
? ? ? ? ????Node<K,V>[] tab; Node first; int n, i;
? ? ? ? ????int binCount =0;
? ? ? ? ????TreeNode<K,V> t =null;
? ? ? ? ????Node<K,V> old =null;
? ? ? ? ????if (size >threshold || (tab =table) ==null || (n = tab.length) ==0)
????????????????????n = (tab = resize()).length;
? ? ? ????? if ((first = tab[i = (n -1) & hash]) !=null) {
????????????????if (first instanceof TreeNode)
????????????????????????old = (t = (TreeNode)first).getTreeNode(hash, key);
? ? ? ? ? ????? else {
????????????????????????Node<K,V> e = first; K k;
? ? ? ? ? ? ? ? ????????do {
????????????????????????????if (e.hash == hash &&((k = e.key) == key || (key !=null
????????????????????????????????&& key.equals(k)))) {
????????????????????????????????old = e;
????????????????????????????????break;
? ? ? ? ? ? ? ? ? ? ????}
????????????????????????++binCount;
? ? ? ? ? ? ? ????? }while ((e = e.next) !=null);
? ? ? ? ? ????? }
????????}
????????if (old !=null) {
????????????V v;
? ? ? ? ? ? if (old.value !=null)
????????????????????????v = remappingFunction.apply(old.value, value);
????????????else
? ? ? ? ? ? ? ????????? v = value;
? ? ? ? ? ????????????? if (v !=null) {
????????????????????????????old.value = v;
? ? ? ? ? ? ? ? ????????????afterNodeAccess(old);
? ? ? ? ? ????????????? }
????????????????????????else removeNode(hash, key, null, false, true);
? ? ? ? ? ? ????????????return v;
? ? ? ? ????}
????????????if (value !=null) {
????????????????????if (t !=null)
????????????????????????????t.putTreeVal(this, tab, hash, key, value);
? ? ? ? ? ? ????????else {
????????????????????????????tab[i] = newNode(hash, key, value, first);
? ? ? ? ? ? ? ????????????? if (binCount >=TREEIFY_THRESHOLD -1)
????????????????????????????????????treeifyBin(tab, hash);
? ? ? ? ? ? ????????????????}
????????????????????++modCount;
? ? ? ? ? ????????? ++size;
? ? ? ? ? ? ????????afterNodeInsertion(true);
? ? ? ????????? }
????????return value;
? ? }
遍歷
? ? public void forEach(BiConsumer<? super K, ? super V> action) {
????????????Node[] tab;
? ? ? ? ? ? if (action ==null)
????????????????????????throw new NullPointerException();
? ? ? ? ????????if (size >0 && (tab =table) !=null) {
????????????????????????int mc =modCount;
? ? ? ? ? ???????????? for (int i =0; i < tab.length; ++i) {
????????????????????????????????for (Node<K，V> e = tab[i]; e !=null; e = e.next)
????????????????????????????????????????????action.accept(e.key, e.value);
? ? ? ? ? ????????????? }
????????????????????????if (modCount != mc)
????????????????????????????????????throw new ConcurrentModificationException();
? ? ? ????????? }
????????}
替換所有
? ? public void replaceAll(BiFunction<? super K, ? super V> function) {
????????????Node<K,V>[] tab;
? ? ? ? ? ? ?if (function ==null)
????????????????????????throw new NullPointerException();
? ? ? ? ????if (size >0 && (tab =table) !=null) {
????????????????????????int mc =modCount;
? ? ? ? ? ? ????????????for (int i =0; i < tab.length; ++i) {
????????????????????????????for (Node<K,V> e = tab[i]; e !=null; e = e.next) {
????????????????????????????????????????e.value = function.apply(e.key, e.value);
? ? ? ? ? ? ? ? ????????????????}
????????????????????????}
????????????????if (modCount != mc)
????????????????????????????throw new ConcurrentModificationException();
? ? ? ????????? }
}
Returns a shallow copy (淺副本螺垢，key和Value不被克隆)
? ? @SuppressWarnings("unchecked")
? public Object clone() {
????????????HashMap result;
? ? ? ? ?????try {
????????????????????????result = (HashMap)super.clone();
? ? ? ????????? }catch (CloneNotSupportedException e) {
? ? ? ? ? ????????????? throw new InternalError(e);
? ? ? ? ????????}
????????????????result.reinitialize();
? ? ? ????????? result.putMapEntries(this, false);
? ? ? ????????? return result;
? ? }
? ? final float loadFactor() {return loadFactor; }
final int capacity() {
????????????return (table !=null) ?table.length :
????????????????????????(threshold >0) ?threshold : DEFAULT_INITIAL_CAPACITY;
? ? }
Save the state of the HashMap instance to a stream (i.e.,
? ? private void writeObject(java.io.ObjectOutputStream s)throws IOException {
????????int buckets = capacity();
? ? ? ? // Write out the threshold, loadfactor, and any hidden stuff
? ? ? ? s.defaultWriteObject();
? ? ? ? s.writeInt(buckets);//容量
? ? ? ? s.writeInt(size);//長度
? ? ? ? internalWriteEntries(s);
? ? }
? ? private void readObject(java.io.ObjectInputStream s)throws IOException, ????????????????????????????????ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
? ? ? ? s.defaultReadObject();
? ? ? ? reinitialize();
? ? ? ? if (loadFactor <=0 || Float.isNaN(loadFactor))
????????????????????throw new InvalidObjectException("Illegal load factor: " +loadFactor);
? ? ? ? s.readInt();? ? ? ? ? ? ? ? // Read and ignore number of buckets
? ? ? ? int mappings = s.readInt(); // Read number of mappings (size)
? ? ? ? if (mappings <0)
????????????throw new InvalidObjectException("Illegal mappings count: " +mappings);
? ? ? ? else if (mappings >0) {// (if zero, use defaults)
????????????????????// Size the table using given load factor only if within
????????????????????// range of 0.25...4.0
? ? ? ? ? ? float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
? ? ? ? ? ? float fc = (float)mappings / lf +1.0f;
? ? ? ? ? ? int cap = ((fc<DEFAULT_INITIAL_CAPACITY) ?DEFAULT_INITIAL_CAPACITY :
????????????????(fc >=MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY :tableSizeFor((int)fc));
? ? ? ? ? ? float ft = (float)cap * lf;
? ? ? ? ? ? threshold = ((cap< MAXIMUM_CAPACITY && ft<MAXIMUM_CAPACITY) ?
????????????????????????(int)ft : Integer.MAX_VALUE);
? ? ? ? ? ? @SuppressWarnings({"rawtypes","unchecked"})
????????????Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
? ? ? ? ? ? table = tab;
? ? ? ? ? ? // Read the keys and values, and put the mappings in the HashMap
? ? ? ? ? ? for (int i =0; i < mappings; i++) {
????????????????????@SuppressWarnings("unchecked")
????????????????????K key = (K) s.readObject();
? ? ? ? ? ? ? ? ????@SuppressWarnings("unchecked")
????????????????????V value = (V) s.readObject();
? ? ? ? ? ? ? ????? putVal(hash(key), key, value, false, false);
? ? ? ? ? ? }
????????}
}
HashIterator
? ? abstract class HashIterator {
????????Node<K,V> next;? ? ? ? // next entry to return
? ? ? ? Node<K,V> current;? ? // current entry
? ? ? ? int expectedModCount;? // for fast-fail
? ? ? ? int index;? ? ? ? ? ? // current slot
? ? ? ? HashIterator() {
????????????expectedModCount =modCount;
? ? ? ? ? ? Node<k,V>[] t =table;
? ? ? ? ? ? current =next =null;
? ? ? ? ? ? index =0;
? ? ? ? ? ? if (t !=null &&size >0) {// advance to first entry
? ? ? ? ? ? ? ? do {}while (index < t.length && (next = t[index++]) ==null);
? ? ? ? ? ? }
}
public final boolean hasNext() {
????????????????????????return next !=null;
? ? ? ? }
final Node<K,V> nextNode() {
????????????Node<K,V>[] t;
? ? ? ? ? ? Node<K,V> e =next;
? ? ? ? ? ? if (modCount !=expectedModCount)
????????????????????????throw new ConcurrentModificationException();
? ? ? ? ? ? if (e ==null)
????????????????????????throw new NoSuchElementException();
? ? ? ? ? ? if ((next = (current = e).next) ==null && (t =table) !=null) {
????????????????????????do {}while (index < t.length && (next = t[index++]) ==null);
? ? ? ? ? ? }
????????????return e;
? ? ? ? }
public final void remove() {
????????????Node<K,V> p =current;
? ? ? ? ? ? if (p ==null)
????????????????????throw new IllegalStateException();
? ? ? ? ? ? if (modCount !=expectedModCount)
????????????????????throw new ConcurrentModificationException();
? ? ? ? ? ? current =null;
? ? ? ? ? ? K key = p.key;
? ? ? ? ? ? removeNode(hash(key), key, null, false, false);
? ? ? ? ? ? expectedModCount =modCount;
? ? ? ? }
}
final class KeyIterator extends HashIterator
????implements Iterator<K> {
public final K next() {return nextNode().key; }
}
final class ValueIterator extends HashIterator
????implements Iterator<V> {
????public final V next() {return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
????????public final Map.Entry<K,V> next() {return nextNode(); }
}
可并行迭代器
? ? static class HashMapSpliterator {
????????final HashMap<K,V> map;
? ? ? ? Node<K,V> current;? ? ? ? ? // current node
? ? ? ? int index;? ? ? ? ? ? ? ? ? // current index, modified on advance/split
? ? ? ? int fence;? ? ? ? ? ? ? ? ? // one past last index
? ? ? ? int est;? ? ? ? ? ? ? ? ? ? // size estimate
? ? ? ? int expectedModCount;? ? ? // for comodification checks
? ? ? ? HashMapSpliterator(HashMap<K,V> m, int origin,
? ? ? ? ? ? ? ? ? ? ? ? ? int fence, int est,
? ? ? ? ? ? ? ? ? ? ? ? ? int expectedModCount) {
????????????this.map = m;
? ? ? ? ? ? this.index = origin;
? ? ? ? ? ? this.fence = fence;
? ? ? ? ? ? this.est = est;
? ? ? ? ? ? this.expectedModCount = expectedModCount;
? ? ? ? }
????final int getFence() {// initialize fence and size on first use
? ? ? ? ? ? int hi;
? ? ? ? ? ? if ((hi =fence) <0) {
????????????????HashMap<K,V> m =map;
? ? ? ? ? ? ? ? est = m.size;
? ? ? ? ? ? ? ? expectedModCount = m.modCount;
? ? ? ? ? ? ? ? Node<K,V>[] tab = m.table;
? ? ? ? ? ? ? ? hi =fence = (tab ==null) ?0 : tab.length;
? ? ? ? ? ? }
????????return hi;
? ? ? ? }
public final long estimateSize() {
????????????getFence(); // force init
? ? ? ? ? ? return (long)est;
? ? ? ? }
}
static final class KeySpliterator<K,V> extends HashMapSpliterator<K,V> implements Spliterator<K> {
????????KeySpliterator(HashMap<K,V> m, int origin, int fence, int est, int expectedModCount) {
????????????super(m, origin, fence, est, expectedModCount);
? ? ? ? }
public KeySpliterator<K,V> trySplit() {
????????????int hi = getFence(), lo =index, mid = (lo + hi) >>>1;
? ? ? ? ? ? return (lo >= mid ||current !=null) ?null :
????????????????????new KeySpliterator<>(map, lo, index = mid, est >>>=1,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? expectedModCount);
? ? ? ? }
public void forEachRemaining(Consumer<? super K> action) {
????????????int i, hi, mc;
? ? ? ? ? ? if (action ==null)
????????????????throw new NullPointerException();
? ? ? ? ? ? HashMap<K,V> m =map;
? ? ? ? ? ? Node<K,V>[] tab = m.table;
? ? ? ? ? ? if ((hi =fence) <0) {
????????????????mc =expectedModCount = m.modCount;
? ? ? ? ? ? ? ? hi =fence = (tab ==null) ?0 : tab.length;
? ? ? ? ? ? }
????????????else
? ? ? ? ? ? ? ? mc =expectedModCount;
? ? ? ? ? ? if (tab !=null && tab.length >= hi &&
????????????????????(i =index) >=0 && (i < (index = hi) ||current !=null)) {
????????????????Node<K,V> p =current;
? ? ? ? ? ? ? ? current =null;
? ? ? ? ? ? ? ? do {
????????????????????????if (p ==null)
????????????????????????p = tab[i++];
? ? ? ? ? ? ? ? ? ? else {
????????????????????????action.accept(p.key);
? ? ? ? ? ? ? ? ? ? ? ? p = p.next;
? ? ? ? ? ? ? ? ? ? }
????????????????}while (p !=null || i < hi);
? ? ? ? ? ? ? ? if (m.modCount != mc)
????????????????????????throw new ConcurrentModificationException();
? ? ? ? ? ? ????}
????}
public boolean tryAdvance(Consumer<? super K> action) {
????????????????int hi;
? ? ? ? ? ? ????if (action ==null)
????????????????????????throw new NullPointerException();
? ? ? ? ? ? ????Node<K,V>[] tab =map.table;
? ? ? ? ? ????? if (tab !=null && tab.length >= (hi = getFence()) &&index >=0) {
????????????????????while (current !=null ||index < hi) {
????????????????????????????if (current ==null)
????????????????????????????????????current = tab[index++];
? ? ? ? ? ? ? ? ? ? ????????else {
????????????????????????????????K k =current.key;
? ? ? ? ? ? ? ? ? ? ? ????????? current =current.next;
? ? ? ? ? ? ? ? ? ? ? ????????? action.accept(k);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (map.modCount !=expectedModCount)
????????????????????????????????????throw new ConcurrentModificationException();
????????????????????????????????return true;
? ? ? ? ? ? ? ? ? ? }
????????????}
????????}
????????return false;
? ? }
????public int characteristics() {
????????return (fence <0 ||est ==map.size ? Spliterator.SIZED :0) | Spliterator.DISTINCT;
? ? ? ? }
}
static final class ValueSpliterator<K,V> extends HashMapSpliterator<K,V>
implements Spliterator<V> {
ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
? ? ? ? ? ? ? ? ? ? ? ? int expectedModCount) {
????????????????super(m, origin, fence, est, expectedModCount);
? ? ? ? }
public ValueSpliterator<K,V> trySplit() {
????????????int hi = getFence(), lo =index, mid = (lo + hi) >>>1;
? ? ? ? ? ? return (lo >= mid ||current !=null) ?null :
????????????????????????new ValueSpliterator<>(map, lo, index = mid, est >>>=1,
????????????????????????????????expectedModCount);
? ? ? ? }
public void forEachRemaining(Consumer<? super V> action) {
????????????????int i, hi, mc;
? ? ? ? ? ? if (action ==null)
????????????????????throw new NullPointerException();
? ? ? ? ? ? HashMap<K,V> m =map;
? ? ? ? ? ? Node<K,V>[] tab = m.table;
? ? ? ? ? ? if ((hi =fence) <0) {
????????????????mc =expectedModCount = m.modCount;
? ? ? ? ? ? ? ? hi =fence = (tab ==null) ?0 : tab.length;
? ? ? ? ? ? }
????????????else
? ? ? ? ? ? ? ? mc =expectedModCount;
? ? ? ? ? ? if (tab !=null && tab.length >= hi &&
????????????????????????(i =index) >=0 && (i < (index = hi) ||current !=null)) {
? ? ? ? ? ? ? ? ?Node<K,V> p =current;
? ? ? ? ? ? ? ? current =null;
? ? ? ? ? ? ? ? do {
????????????????????if (p ==null)
????????????????????????????p = tab[i++];
? ? ? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? ? ? action.accept(p.value);
? ? ? ? ? ? ? ? ? ? ? ? p = p.next;
? ? ? ? ? ? ? ? ? ? }
????????????????}while (p !=null || i < hi);
? ? ? ? ? ? ? ? if (m.modCount != mc)
????????????????????????throw new ConcurrentModificationException();
? ? ? ? ? ????? }
????}
public boolean tryAdvance(Consumer<? super V> action) {
????????????int hi;
? ? ? ? ? ? if (action ==null)
????????????????????????throw new NullPointerException();
? ? ? ? ? ? Node[] tab =map.table;
? ? ? ? ? ? if (tab !=null && tab.length >= (hi = getFence()) &&index >=0) {
????????????????????while (current !=null ||index < hi) {
????????????????????????????if (current ==null)
????????????????????????????????current = tab[index++];
? ? ? ? ? ? ? ? ? ????????? else {
????????????????????????????????V v =current.value;
? ? ? ? ? ? ? ? ? ? ? ????????? current =current.next;
? ? ? ? ? ? ? ? ? ? ? ????????? action.accept(v);
? ? ? ? ? ? ? ? ? ? ? ????????? if (map.modCount !=expectedModCount)
????????????????????????????????????????throw new ConcurrentModificationException();
????????????????????????????????return true;
? ? ? ? ? ? ? ? ? ? ????????}
????????????????????}
????????????}
????????????return false;
? ? ? ? }
public int characteristics() {
????????????????return (fence <0 ||est ==map.size ? Spliterator.SIZED :0);
? ? ? ? }
}
static final class EntrySpliterator<K,V>extends HashMapSpliterator<K,V>
implements Spliterator<K,V> {
EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
? ? ? ? ? ? ? ? ? ? ? ? int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
? ? ? ? }
public EntrySpliterator<K,V> trySplit() {
? ? ? ? ? ? ? int hi = getFence(), lo =index, mid = (lo + hi) >>>1;
? ? ? ? ? ? return (lo >= mid ||current !=null) ?null :
????????????new EntrySpliterator<>(map, lo, index = mid, est >>>=1, expectedModCount);
? ? ? ? }
public void forEachRemaining(Consumer<? super Map.Entry<K,V> action) {
????????????int i, hi, mc;
? ? ? ? ? ? if (action ==null)
????????????????????throw new NullPointerException();
? ? ? ? ? ? HashMap<K,V> m =map;
? ? ? ? ? ? Node<K,V>[] tab = m.table;
? ? ? ? ? ? if ((hi =fence) <0) {
????????????????mc =expectedModCount = m.modCount;
? ? ? ? ? ? ? ? hi =fence = (tab ==null) ?0 : tab.length;
? ? ? ? ? ? }
????????????else
? ? ? ? ? ? ? ? mc =expectedModCount;
? ? ? ? ? ? ? ? ?if (tab !=null && tab.length >= hi &&(i =index) >=0
????????????????????????&& (i < (index = hi) ||current !=null)) {
????????????????????????Node<K,V> p =current;
? ? ? ? ? ? ? ? ????????current =null;
? ? ? ? ? ? ? ????????? do {
????????????????????????????if (p ==null)
????????????????????????????????p = tab[i++];
? ? ? ? ? ? ? ? ? ? ????????else {
????????????????????????????????????action.accept(p);
? ? ? ? ? ? ? ? ? ? ? ????????????? p = p.next;
? ? ? ? ? ? ? ? ? ? ????????????}
????????????????????????????}while (p !=null || i < hi);
? ? ? ? ? ? ? ????????????????? if (m.modCount != mc)
????????????????????????????????????????throw new ConcurrentModificationException();
? ? ? ? ? ? ????????????}
????????}
public boolean tryAdvance(Consumer<? super Map<K,V>> action) {
int hi;
? ? ? ? ? ? if (action ==null)
????????????????????throw new NullPointerException();
? ? ? ? ? ? Node<K,V>[] tab =map.table;
? ? ? ? ? ? if (tab !=null && tab.length >= (hi = getFence()) &&index >=0) {
????????????????while (current !=null ||index < hi) {
????????????????????????????if (current ==null)
????????????????????????????????current = tab[index++];
? ? ? ? ? ? ? ? ? ????????? else {
????????????????????????????????Node<K,V> e =current;
? ? ? ? ? ? ? ? ? ? ? ? ????????current =current.next;
? ? ? ? ? ? ? ? ? ? ? ????????? action.accept(e);
? ? ? ? ? ? ? ? ? ? ? ????????? if (map.modCount !=expectedModCount)
????????????????????????????????????????throw new ConcurrentModificationException();
????????????????????????????????return true;
? ? ? ? ? ? ? ? ? ? ????}
????????????????}
????????}
????????return false;
? ? ? ? }
public int characteristics() {
????????????return (fence <0 ||est ==map.size ? Spliterator.SIZED :0) | Spliterator.DISTINCT;
? ? ? ? }
}
? ? Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
????????????return new Node<>(hash, key, value, next);
? ? }
? ? Node<K,V> replacementNode(Node<K,V> p, Node next) {
????????????????return new Node<>(p.hash, p.key, p.value, next);
? ? }
? ? TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
????????????return new TreeNode<>(hash, key, value, next);
? ? }
? ? TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
????????????return new TreeNode<>(p.hash, p.key, p.value, next);
? ? }
? ? void reinitialize() {
????????table =null;
? ? ? ? entrySet =null;
? ? ? ? keySet =null;
? ? ? ? values =null;
? ? ? ? modCount =0;
? ? ? ? threshold =0;
? ? ? ? size =0;
? ? }
回調(diào)函數(shù)
? ? void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
// Called only from writeObject, to ensure compatible ordering.
? ? void internalWriteEntries(java.io.ObjectOutputStream s)throws IOException {
????????Node<K,V>[] tab;
? ? ? ? if (size >0 && (tab =table) !=null) {
????????????????for (int i =0; i < tab.length; ++i) {
????????????????????????for (Node e = tab[i]; e !=null; e = e.next) {
????????????????????????????s.writeObject(e.key);
? ? ? ? ? ? ? ? ? ????????? s.writeObject(e.value);
? ? ? ? ? ? ? ? ????????}
????????????????}
????????}
}
紅黑樹
? ? static final class TreeNodeextends LinkedHashMap.Entry {
? ? ? ? TreeNode<K,V> parent;? // red-black tree links
? ? ? ? TreeNode<K,V> left;
? ? ? ? TreeNode<K,V> right;
? ? ? ? TreeNode<K,V> prev;? ? // needed to unlink next upon deletion
? ? ? ? boolean red;
? ? ? ? TreeNode(int hash, K key, V val, Node<K,V> next) {
????????????????super(hash, key, val, next);
? ? ? ? }
//返回跟節(jié)點
? ? ? ? final TreeNoderoot() {
????????????????????for (TreeNode r =this, p;;) {
????????????????????????????if ((p = r.parent) ==null)? return r;
? ? ? ? ? ? ? ????????? r = p;
? ? ? ? ? ????????? }
????????????}
//確保給定的根是它的bin的第一個節(jié)點喧务。
? ? ? ? static void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
? ? ? ? ? ? ?int n;
? ? ? ? ? ? if (root !=null && tab !=null && (n = tab.length) >0) {
? ? ? ? ? ? ? ? ?int index = (n -1) & root.hash;
? ? ? ? ? ? ? ? TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
? ? ? ? ? ? ? ? if (root != first) {
????????????????????Node<K,V> rn;
? ? ? ? ? ? ? ? ? ? tab[index] = root;
? ? ? ? ? ? ? ? ? ? TreeNode<K,V> rp = root.prev;
? ? ? ? ? ? ? ? ? ? if ((rn = root.next) !=null)
????????????????????????((TreeNode<K,V>)rn).prev = rp;
? ? ? ? ? ? ? ? ? ? if (rp !=null)
? ? ? ? ? ? ? ? ? ? ? ? ?rp.next = rn;
? ? ? ? ? ? ? ? ? ? if (first !=null)
????????????????????????first.prev = root;
? ? ? ? ? ? ? ? ? ? root.next = first;
? ? ? ? ? ? ? ? ? ? root.prev =null;
? ? ? ? ? ? ? ? }
????????????????assert checkInvariants(root);
? ? ? ? ? ? }
}
//在樹中查找某個節(jié)點
? ? ? ? final TreeNode<K,V > find(int h, Object k, Class kc) {
????????????TreeNode<K,V> p =this;
? ? ? ? ? ? do {
????????????????int ph, dir; K pk;
? ? ? ? ? ? ? ? TreeNode<K,V> pl = p.left, pr = p.right, q;
? ? ? ? ? ? ? ? if ((ph = p.hash) > h)
????????????????????????p = pl;
? ? ? ? ? ? ? ? else if (ph < h)
????????????????????????p = pr;
? ? ? ? ? ? ? ? else if ((pk = p.key) == k || (k !=null && k.equals(pk)))
????????????????????????????????????return p;
? ? ? ? ? ? ? ? else if (pl ==null)
????????????????????????????????p = pr;
? ? ? ? ? ? ? ? else if (pr ==null)
????????????????????????p = pl;
? ? ? ? ? ? ? ? else if ((kc !=null || (kc =comparableClassFor(k)) !=null) &&
????????????????????????(dir =compareComparables(kc, k, pk)) !=0)
????????????????????????p = (dir <0) ? pl : pr;
? ? ? ? ? ? ? ? else if ((q = pr.find(h, k, kc)) !=null)
????????????????????????return q;
????????????????else
? ? ? ? ? ? ? ? ? ? ????p = pl;
? ? ? ? ? ????? }while (p !=null);
? ? ? ? ? ? ? ?return null;
? ? ? ? }
//按照hashCode和Key查找
? ? ? ? final TreeNodegetTreeNode(int h, Object k) {
????????????????????????return ((parent !=null) ? root() :this).find(h, k, null);
? ? ? ? }
//tieBreakOrder()方法最終還是通過調(diào)用System.identityHashCode()方法來比較。
? ? ? ? static int tieBreakOrder(Object a, Object b) {
????????????int d;
? ? ? ? ? ? if (a ==null || b ==null ||
????????????????????????(d = a.getClass().getName().compareTo(b.getClass().getName())) ==0)
????????????????d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 :1);
? ? ? ? ? ? return d;
? ? ? ? }
//將鏈表轉(zhuǎn)化為樹
? ? ? ?final void treeify(Node<K,V>[] tab) {
????????????TreeNode<K,V> root =null;
? ? ? ? ? ? for (TreeNode<K,V> x =this, next; x !=null; x = next) {
????????????????next = (TreeNode<K,V>)x.next;
? ? ? ? ? ? ? ? x.left = x.right =null;
? ? ? ? ? ? ? ? if (root ==null) {
????????????????????x.parent =null;
? ? ? ? ? ? ? ? ? ? x.red =false;
? ? ? ? ? ? ? ? ? ? root = x;
? ? ? ? ? ? ? ? }
????????????????else {
????????????????????K k = x.key;
? ? ? ? ? ? ? ? ? ? int h = x.hash;
? ? ? ? ? ? ? ? ? ? Class kc =null;
? ? ? ? ? ? ? ? ? ? for (TreeNode<K,V> p = root;;) {
? ? ? ? ? ? ? ? ? ? ? ? ?int dir, ph;
? ? ? ? ? ? ? ? ? ? ? ? K pk = p.key;
? ? ? ? ? ? ? ? ? ? ? ? if ((ph = p.hash) > h)
????????????????????????????dir = -1;
? ? ? ? ? ? ? ? ? ? ? ? else if (ph < h)
????????????????????????????dir =1;
? ? ? ? ? ? ? ? ? ? ? ? else if ((kc ==null &&(kc =comparableClassFor(k)) ==null) ||
????????????????????????????????(dir =compareComparables(kc, k, pk)) ==0)
????????????????????????????dir =tieBreakOrder(k, pk);
? ? ? ? ? ? ? ? ? ? ? ? TreeNode<K,V> xp = p;
? ? ? ? ? ? ? ? ? ? ? ? if ((p = (dir <=0) ? p.left : p.right) ==null) {
????????????????????????????????x.parent = xp;
? ? ? ? ? ? ? ? ? ? ? ? ? ????? if (dir <=0) xp.left = x;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?else xp.right = x;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?root =balanceInsertion(root, x);
????????????????????????????????break;
? ? ? ? ? ? ? ? ? ? ? ? }
????????????????}
????????????????}
????????????}
????????????moveRootToFront(tab, root);
? ? ? ? }
//將樹轉(zhuǎn)化為鏈表,返回頭節(jié)點
? ? ? ? final Node<K,V> untreeify(HashMap<K,V> map) {
????????????Node<K,V> hd =null, tl =null;
? ? ? ? ? ? for (Node<K,V> q =this; q !=null; q = q.next) {
????????????????????Node<K,V> p = map.replacementNode(q, null);
? ? ? ? ? ? ? ? if (tl ==null)? ? hd = p;
? ? ? ? ? ? ? ? ?else? tl.next = p;
? ? ? ? ? ? ? ? tl = p;
? ? ? ? ? ? }
????????return hd;
? ? ? ? }
//樹版的插入操作
? ? ? ? final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? int h, K k, V v) {
????????????Class kc =null;
? ? ? ? ? ? boolean searched =false;
? ? ? ? ? ? TreeNode<K,V> root = (parent !=null) ? root() :this;
? ? ? ? ? ? for (TreeNode<K,V> p = root;;) {
????????????????int dir, ph; K pk;
? ? ? ? ? ? ? ? if ((ph = p.hash) > h)
? ? ? ? ? ? ? ? ? ? ? dir = -1;
? ? ? ? ? ? ? ? else if (ph < h)
????????????????????????dir =1;
? ? ? ? ? ? ? ? else if ((pk = p.key) == k || (k !=null && k.equals(pk)))
????????????????????????????return p;
? ? ? ? ? ? ? ? else if ((kc ==null &&(kc =comparableClassFor(k)) ==null) ||
????????????????????????????(dir =compareComparables(kc, k, pk)) ==0) {
????????????????????????if (!searched) {
????????????????????????????TreeNode<K,V> q, ch;
? ? ? ? ? ? ? ? ? ? ? ????? searched =true;
? ? ? ? ? ? ? ? ? ? ? ????????? if (((ch = p.left) !=null &&(q = ch.find(h, k, kc)) !=null) ||
????????????????????????????????????((ch = p.right) !=null &&(q = ch.find(h, k, kc)) !=null))
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return q;
? ? ? ? ? ? ? ? ? ? }
????????????????dir =tieBreakOrder(k, pk);
? ? ? ? ? ? ? ? }
????????????????TreeNode<K,V> xp = p;
? ? ? ? ? ? ? ? if ((p = (dir <=0) ? p.left : p.right) ==null) {
????????????????????Node<K,V> xpn = xp.next;
? ? ? ? ? ? ? ? ? ? TreeNode x = map.newTreeNode(h, k, v, xpn);
? ? ? ? ? ? ? ? ? ? if (dir <=0)? xp.left = x;
? ? ? ? ? ? ? ? ? ? ? else? ?xp.right = x;
? ? ? ? ? ? ? ? ? ? xp.next = x;
? ? ? ? ? ? ? ? ? ? x.parent = x.prev = xp;
? ? ? ? ? ? ? ? ? ? if (xpn !=null)((TreeNode<K,V>)xpn).prev = x;
? ? ? ? ? ? ? ? ? ? moveRootToFront(tab, balanceInsertion(root, x));
????????????????????return null;
? ? ? ? ? ? ? ? }
????????}
}
//刪除樹的節(jié)點
? ? ? ? final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? boolean movable) {
? ? ? ? ? ? ? ?int n;
? ? ? ? ? ? if (tab ==null || (n = tab.length) ==0) return;
? ? ? ? ? ? int index = (n -1) & hash;
? ? ? ? ? ? TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
? ? ? ? ? ? TreeNode<K,V> succ = (TreeNode<K,V>)next, pred =prev;
? ? ? ? ? ? if (pred ==null)
????????????????tab[index] = first = succ;
????????????else
? ? ? ? ? ? ? ? pred.next = succ;
? ? ? ? ? ? if (succ !=null)
????????????????????succ.prev = pred;
? ? ? ? ? ? if (first ==null)
????????????????return;
? ? ? ? ? ? if (root.parent !=null)
????????????????????root = root.root();
? ? ? ? ? ? if (root ==null || root.right ==null ||(rl = root.left) ==null || rl.left ==null) {
????????????????????tab[index] = first.untreeify(map);? // too small
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
????????????TreeNode<K,V> p =this, pl =left, pr =right, replacement;
? ? ? ? ? ? if (pl !=null && pr !=null) {
????????????????TreeNode<K,V> s = pr, sl;
? ? ? ? ? ? ? ? while ((sl = s.left) !=null)// find successor
? ? ? ? ? ? ? ? ? ? s = sl;
? ? ? ? ? ? ? ? boolean c = s.red; s.red = p.red; p.red = c; // swap colors
? ? ? ? ? ? ? ? TreeNode<K,V> sr = s.right;
? ? ? ? ? ? ? ? TreeNode<K,V> pp = p.parent;
? ? ? ? ? ? ? ? if (s == pr) {// p was s's direct parent
? ? ? ? ? ? ? ? ? ? p.parent = s;
? ? ? ? ? ? ? ? ? ? s.right = p;
? ? ? ? ? ? ? ? }
????????????????else {
????????????????????TreeNode<K,V> sp = s.parent;
? ? ? ? ? ? ? ? ? ? if ((p.parent = sp) !=null) {
????????????????????????if (s == sp.left)? sp.left = p;
????????????????????????else? sp.right = p;
? ? ? ? ? ? ? ? ? ? }
????????????????????if ((s.right = pr) !=null)? ?pr.parent = s;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? p.left =null;
? ? ? ? ? ? ? ? if ((p.right = sr) !=null)
????????????????????????sr.parent = p;
? ? ? ? ? ? ? ? if ((s.left = pl) !=null)
????????????????????????pl.parent = s;
? ? ? ? ? ? ? ? if ((s.parent = pp) ==null)
? ? ? ? ? ? ? ? ? ? ? ? root = s;
? ? ? ? ? ? ? ? else if (p == pp.left)
????????????????????????pp.left = s;
????????????????else
? ? ? ? ? ? ? ? ? ? pp.right = s;
? ? ? ? ? ? ? ? if (sr !=null)
????????????????????????replacement = sr;
????????????????else
? ? ? ? ? ? ? ? ? ? replacement = p;
? ? ? ? ? ? }
????????????else if (pl !=null) replacement = pl;
? ? ? ? ? ? else if (pr !=null) replacement = pr;
????????????else replacement = p;
? ? ? ? ? ? if (replacement != p) {
? ? ? ? ? ? ? ? ?TreeNode<K,V> pp = replacement.parent = p.parent;
? ? ? ? ? ? ? ? if (pp ==null)? root = replacement;
? ? ? ? ? ? ? ? else if (p == pp.left)? ?pp.left = replacement;
? ? ? ? ? ? ? ?????else pp.right = replacement;
? ? ? ? ? ? ? ? p.left = p.right = p.parent =null;
? ? ? ? ? ? }
????????????TreeNode<K,V> r = p.red ? root :balanceDeletion(root, replacement);
? ? ? ? ? ? if (replacement == p) {// detach
? ? ? ? ? ? ? ? TreeNode<K,V> pp = p.parent;
? ? ? ? ? ? ? ? p.parent =null;
? ? ? ? ? ? ? ? if (pp !=null) {
????????????????????if (p == pp.left)? pp.left =null;
? ? ? ? ? ? ? ? ? ? else if (p == pp.right) pp.right =null;
? ? ? ? ? ? ? ? }
????????}
????????????if (movable) moveRootToFront(tab, r);
? ? ? ? }
//拆分樹
? ? ? ? final void split(HashMap map, Node[] tab, int index, int bit) {
????????????TreeNode b =this;
? ? ? ? ? ? // Relink into lo and hi lists, preserving order
? ? ? ? ? ? TreeNode loHead =null, loTail =null;
? ? ? ? ? ? TreeNode hiHead =null, hiTail =null;
? ? ? ? ? ? int lc =0, hc =0;
? ? ? ? ? ? for (TreeNode e = b, next; e !=null; e = next) {
? ? ? ? ? ? ? ? ?next = (TreeNode)e.next;
? ? ? ? ? ? ? ? e.next =null;
? ? ? ? ? ? ? ? if ((e.hash & bit) ==0) {
????????????????????if ((e.prev = loTail) ==null) loHead = e;
????????????????????else loTail.next = e;
? ? ? ? ? ? ? ? ? ? loTail = e;
? ? ? ? ? ? ? ? ? ? ++lc;
? ? ? ? ? ? ? ? }
????????????else {
????????????????????if ((e.prev = hiTail) ==null) hiHead = e;
? ? ? ? ? ? ? ? ? ? else hiTail.next = e;
? ? ? ? ? ? ? ? ? ? hiTail = e;
? ? ? ? ? ? ? ? ? ? ++hc;
? ? ? ? ? ? ? ? }
????????????}
????????if (loHead !=null) {
????????????????????if (lc <=UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map);
? ? ? ? ? ? ? ? ????else {
? ? ? ? ? ? ? ? ? ? ? ?tab[index] = loHead;
? ? ? ? ? ? ? ? ? ? if (hiHead !=null)// (else is already treeified)
? ? ? ? ? ? ? ? ? ? ? ? loHead.treeify(tab);
? ? ? ? ? ? ? ? }
????????????}
????????????if (hiHead !=null) {
????????????????if (hc <=UNTREEIFY_THRESHOLD)
????????????????????????tab[index + bit] = hiHead.untreeify(map);
? ? ? ? ? ? ? ? else {
????????????????????tab[index + bit] = hiHead;
? ? ? ? ? ? ? ? ? ? if (loHead !=null) hiHead.treeify(tab);
? ? ? ? ? ? ? ? }
????????}
????}
//紅黑樹平衡方法
//左旋
? ? ? ? static<K,V>? TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
????????????TreeNode r, pp, rl;
? ? ? ? ? ? if (p !=null && (r = p.right) !=null) {
????????????????????if ((rl = p.right = r.left) !=null)? rl.parent = p;
? ? ? ? ? ? ? ????? if ((pp = r.parent = p.parent) ==null) (root = r).red =false;
? ? ? ? ? ? ? ? ????else if (pp.left == p) pp.left = r;
????????????????????else pp.right = r;
? ? ? ? ? ? ? ????? r.left = p;
? ? ? ? ? ? ? ????? p.parent = r;
? ? ? ? ? ????? }
????????????return root;
? ? ? ? }
//右旋
static TreeNode rotateRight(TreeNode root,TreeNode p) {
????????????TreeNode l, pp, lr;
? ? ? ? ? ? if (p !=null && (l = p.left) !=null) {
????????????????????????if ((lr = p.left = l.right) !=null) lr.parent = p;
? ? ? ? ? ? ? ????????? if ((pp = l.parent = p.parent) ==null) (root = l).red =false;
? ? ? ? ? ? ? ? ????????else if (pp.right == p) pp.right = l;
????????????????????????else pp.left = l;
? ? ? ? ? ? ? ????????? l.right = p;
? ? ? ? ? ? ? ????? p.parent = l;
? ? ? ? ? ? ????}
? ? ? ? ? ? return root;
? ? ? ? }
//平衡
static TreeNode balanceInsertion(TreeNode root, TreeNode x) {
????????????????x.red =true;
? ? ? ? ? ? for (TreeNode xp, xpp, xppl, xppr;;) {
????????????????????if ((xp = x.parent) ==null) {
????????????????????????????????x.red =false;
? ? ? ? ? ? ? ? ? ? ????????????return x;
? ? ? ? ? ? ? ? }
????????????????else if (!xp.red || (xpp = xp.parent) ==null) return root;
? ? ? ? ? ? ? ????? if (xp == (xppl = xpp.left)) {
????????????????????????if ((xppr = xpp.right) !=null && xppr.red) {
????????????????????????????xppr.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ????xp.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ????xpp.red =true;
? ? ? ? ? ? ? ? ? ? ? ????? x = xpp;
? ? ? ? ? ? ? ? ? ? }else {
????????????????????????if (x == xp.right) {
????????????????????????????root =rotateLeft(root, x = xp);
? ? ? ? ? ? ? ? ? ? ? ? ? ? xpp = (xp = x.parent) ==null ?null : xp.parent;
? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????if (xp !=null) {
????????????????????????????xp.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ? if (xpp !=null) {
????????????????????????????????xpp.red =true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? root =rotateRight(root, xpp);
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????????}
????????????????????}
????????????????}else {
????????????????????????if (xppl !=null && xppl.red) {
????????????????????????????xppl.red =false;
? ? ? ? ? ? ? ? ? ? ? ????? xp.red =false;
? ? ? ? ? ? ? ? ? ? ? ????? xpp.red =true;
? ? ? ? ? ? ? ? ? ? ? ????? x = xpp;
? ? ? ? ? ? ? ? ? ????? }else {
????????????????????????????if (x == xp.left) {
????????????????????????????????root =rotateRight(root, x = xp);
? ? ? ? ? ? ? ? ? ? ? ? ? ????? xpp = (xp = x.parent) ==null ?null : xp.parent;
? ? ? ? ? ? ? ? ? ? ? ? ????}
????????????????????????????if (xp !=null) {
????????????????????????????????????xp.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ????????? if (xpp !=null) {
????????????????????????????????????????xpp.red =true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????root =rotateLeft(root, xpp);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????}
????????????????????????????????}
????????????????????????????}
????????????????????????}
????????????????????}
????????}
static TreeNode balanceDeletion(TreeNode root, TreeNode x) {
for (TreeNode xp, xpl, xpr;;)? {
????????????if (x ==null || x == root) return root;
? ? ? ? ? ? ?else if ((xp = x.parent) ==null) {
????????????????????x.red =false;
? ? ? ? ? ? ? ? ? ? return x;
? ? ? ? ? ? ? ? }else if (x.red) {
????????????????????x.red =false;
? ? ? ? ? ? ? ? ? ? return root;
? ? ? ? ? ? ? ? }else if ((xpl = xp.left) == x) {
????????????????????????if ((xpr = xp.right) !=null && xpr.red) {
????????????????????????????xpr.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ????xp.red =true;
? ? ? ? ? ? ? ? ? ? ? ????? root =rotateLeft(root, xp);
? ? ? ? ? ? ? ? ? ? ? ????? xpr = (xp = x.parent) ==null ?null : xp.right;
? ? ? ? ? ? ? ? ? ? }
????????????????????if (xpr ==null)? x = xp;
? ? ? ? ? ? ? ? ? ? else {
????????????????????????TreeNode sl = xpr.left, sr = xpr.right;
? ? ? ? ? ? ? ? ? ? ? ? if ((sr ==null || !sr.red) &&(sl ==null || !sl.red)) {
????????????????????????????xpr.red =true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? x = xp;
? ? ? ? ? ? ? ? ? ? ? ? }else {
????????????????????????????????if (sr ==null || !sr.red) {
????????????????????????????????????????if (sl !=null)sl.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? xpr.red =true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? root =rotateRight(root, xpr);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? xpr = (xp = x.parent) ==null ?null : xp.right;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????????????if (xpr !=null) {
????????????????????????????????xpr.red = (xp ==null) ?false : xp.red;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if ((sr = xpr.right) !=null) sr.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????????????if (xp !=null) {
????????????????????????????????xp.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? root =rotateLeft(root, xp);
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????????????x = root;
? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????}
????????????????}else {// symmetric
? ? ? ? ? ? ? ? ? ? if (xpl !=null && xpl.red) {
????????????????????????xpl.red =false;
? ? ? ? ? ? ? ? ? ? ? ? xp.red =true;
? ? ? ? ? ? ? ? ? ? ? ? root =rotateRight(root, xp);
? ? ? ? ? ? ? ? ? ? ? ? xpl = (xp = x.parent) ==null ?null : xp.left;
? ? ? ? ? ? ? ? ? ? }
????????????????????if (xpl ==null) x = xp;
? ? ? ? ? ? ? ? ? ? else {
????????????????????????TreeNode sl = xpl.left, sr = xpl.right;
? ? ? ? ? ? ? ? ? ? ? ? if ((sl ==null || !sl.red) &&(sr ==null || !sr.red)) {
????????????????????????????xpl.red =true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? x = xp;
? ? ? ? ? ? ? ? ? ? ? ? }else {
????????????????????????????????if (sl ==null || !sl.red) {
????????????????????????????????????????if (sr !=null) sr.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? xpl.red =true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? root =rotateLeft(root, xpl);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? xpl = (xp = x.parent) ==null ?null : xp.left;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????????????if (xpl !=null) {
????????????????????????????????xpl.red = (xp ==null) ?false : xp.red;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if ((sl = xpl.left) !=null) sl.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????????????if (xp !=null) {
????????????????????????????????xp.red =false;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? root =rotateRight(root, xp);
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
????????????????????????????x = root;
? ? ? ? ? ? ? ? ? ? ? ? }
????????????????}
????????????}
????????}
}
//遞歸不變檢查枉圃，檢測穩(wěn)定性
? ? ? ? static boolean checkInvariants(TreeNode t) {
? ? ? ? ? ? TreeNode tp = t.parent, tl = t.left, tr = t.right,
? ? ? ? ? ? ? ? tb = t.prev, tn = (TreeNode)t.next;
? ? ? ? ? ? if (tb !=null && tb.next != t) return false;
? ? ? ? ? ? if (tn !=null && tn.prev != t) return false;
? ? ? ? ? ? if (tp !=null && t != tp.left && t != tp.right) return false;
? ? ? ? ? ? if (tl !=null && (tl.parent != t || tl.hash > t.hash)) return false;
? ? ? ? ? ? if (tr !=null && (tr.parent != t || tr.hash < t.hash)) return false;
? ? ? ? ? ? if (t.red && tl !=null && tl.red && tr !=null && tr.red) return false;
? ? ? ? ? ? if (tl !=null && !checkInvariants(tl)) return false;
? ? ? ? ? ? if (tr !=null && !checkInvariants(tr)) return false;
????????????return true;
? ? ? ? }
????}
}
