jdk1.8源码解析：HashMap底层数据结构之链表转红黑树的具体时机
- 2019 年 10 月 3 日
- 筆記
??
????????????HashMap?????????????
???????HashMap???“??????”??????
????????????HashMap.put(K key, V value)????
?????????
???HashMap???“??????”??????????HashMap??????????
??? jdk1.8 HashMap??????????+??+??????+???? “??????”????????????????????????????
??HashMap???“??????”??????
/** * ?????(?????)?????????????????????????????????????? * ??????2????????8??????????????? */ static final int TREEIFY_THRESHOLD = 8; /** * ????????????????????????? */ static final int MIN_TREEIFY_CAPACITY = 64;
????????HashMap.put(K key, V value)???????????????????
??????HashMap??????????put(K key, V value)?????putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)???????????????????putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)????
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K, V>[] tab; Node<K, V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //??????????????????????????????"??/???.index(0)" 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???????????????? p.next = newNode(hash, key, value, null); //????????????????????
//“binCount >= 7”?p???.index(0)????binCount == 7??p.index == 7,newNode.index == 8? //???????????8????????????9???????????????????????????? if (binCount >= TREEIFY_THRESHOLD - 1)
????????????????treeifyBin(tab, hash); //?????? break;
????????????}
????????????……
????????????p = e;
??????????}
?????? }
???????……
????}
????……
}
????????????????HashMap??“??????8????????????9???????????????????????????”?
????debug?????????????????
??1. ?????????????hashCode()??????????????????????????????equals()???
public class A03Bean { protected int number; public A03Bean(int number) { this.number = number; } /** * ??hashCode()??????4???????????????0. */ @Override public int hashCode() { return number % 4; } /** * ?????equals()??????????????????equals()?????????????????? */ @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; A03Bean other = (A03Bean) obj; if (number != other.number) return false; return true; } }
??2. ?????A03Bean?????HashMap??
public class A03Method_TreeifyBin2 { public static void main(String[] args) { HashMap<A03Bean, Integer> hashMap = new HashMap<>(); hashMap.put(new A03Bean(4), 0); hashMap.put(new A03Bean(8), 1); hashMap.put(new A03Bean(12), 2); hashMap.put(new A03Bean(16), 3); hashMap.put(new A03Bean(20), 4); hashMap.put(new A03Bean(24), 5); hashMap.put(new A03Bean(28), 6); hashMap.put(new A03Bean(32), 7); hashMap.put(new A03Bean(36), 8); hashMap.put(new A03Bean(40), 9); hashMap.put(new A03Bean(44), 10); System.out.println("hashMap.size = " + hashMap.size()); //???????????HashMap??? for(A03Bean key : hashMap.keySet()) { System.out.println(key.number); } } }
??3.debug????????????????????????“??????”????
????????HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)???“treeifyBin(tab, hash);”???
??4.?????
?????put??9????hashMap.put(new A03Bean(36), 8);???HashMap????????????
???????????????8???????put??9????????9????put???????????????????2??????????
???????????????????????put??????hashMap.size??11?
????????“HashMap????????????”??????????????“HashMap?????????????”?
