day24--Java集合07

Java集合07

14.HashMap底层机制

• （k,v）是一个Node，实现了Map.Entry，查看HashMap的源码可以看到
  
• jdk7.0 的HashMap底层实现[数组+链表]，jdk8.0底层[数组+链表+红黑树]
  

14.1HashMap扩容机制（和HashSet完全相同）

详见10.2HashSet的底层扩容机制

• HashMap底层维护了Node类型的数组table，默认为null
  
• 当创建对象时，将加载因子（loadfactor）初始化为0.75
  
• 当添加key-value时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素则直接添加；如果该索引处有元素，继续判断该元素的key是否和准备加入的key相等。若相等，则直接替换value；若不相等，需要判断是树结构还是链表结构，作出相应处理。如果添加是发现容量还不够，则需要扩容。
  
• 第一次添加，则需要扩容table容量为16，临界值（threshold）为（0.75*16=）12
  
• 以后再扩容，则需要扩容为table的容量为之前的两倍，临界值也为原来的两倍，即24.以此类推
  
• 在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认为8），并且table的大小>=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）。
  

例子：

1. package li.map.hashmap;
3. import java.util.HashMap;
5. @SuppressWarnings("all")
6. public class HashMapSource {
7.     public static void main(String[] args) {
8.         HashMap map = new HashMap();
9.         map.put("java",10);//ok
10.         map.put("php",10);//ok
11.         map.put("java",20);//替换value
13.         System.out.println(map);//{java=20, php=10}
14.     }
15. }

复制代码

执行过程如下：

• 执行构造器 newHashMap();
  初始化加载因子 loadfactor = 0.75
  HashMap$Node[ ] = null
  
• 执行put（），调用hash（）方法计算key的值
  可以看到，如果传入的参数key为空的话，就返回0；如果不为空，则求出 key 的 hashCode 值，然后将hashCode 值右移16位并且与原来的 hashCode 值进行 ^(按位异或) 操作，并返回这个哈希值
  

1. public V put(K key, V value) {//K="java" value= 10
2.     return putVal(hash(key), key, value, false, true);
3. }

复制代码

1. static final int hash(Object key) {
2.     int h;
3.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4. }

复制代码

3.调用putVal方法：

1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2.                boolean evict) {//
3.     Node<K,V>[] tab; Node<K,V> p; int n, i;//定义了辅助变量
4.     //这里定义的tablejiushi HashMap的一个数组，类型是Node[]数组
5.     if ((tab = table) == null || (n = tab.length) == 0)//if 语句表示，如果当前table是null，或者大小=0，则进行第一次扩容，扩容到16个空间
6.         n = (tab = resize()).length;//如果为第一次扩容，此时初始的table已经变成容量为16的数组
7.    
8.     /*
9.     1.根据key，得到hash 去计算key应该放到table表的哪个索引位置，并且把这个未知的对象赋给赋值变量p               2.再判断p是否为空
10.             2.1如果p为空，表示该位置还没存放元素，就创建一个Node (key="java", value=PRESENT)并把数         据放在该位置--table[i]=newNode(hash, key, value, null);
11.     */
12.     if ((p = tab[i = (n - 1) & hash]) == null)
13.         tab[i] = newNode(hash, key, value, null);
14.    
15.    
16.     else {
17.       //2.2如果不为空，就会进入else语句
18.         Node<K,V> e; K k;//定义辅助变量
19.        /*这里的p指向当前索引所在的对象（由上面的p = tab[i = (n - 1) & hash])计算出索引位置），如          果当前索引位置对应链表的第一个元素的哈希值 和 准备添加的key的哈希值 一样，
20.        并且 满足下面两个条件之一：
21.         1.准备加入的key 和 p指向的Node节点 的key 是同一个对象：(k = p.key) == key
22.         2.p指向的Node节点的key 的equals()和准备加入的key比较后相同 并且key不等于null：(key !=               null && key.equals(k))
23.        就不加入  只是换原来的元素（不插入新结点只是替换值）
24.         */
25.         if (p.hash == hash &&
26.             ((k = p.key) == key || (key != null && key.equals(k))))
27.             e = p;
28.         
29.         //再判断p是否是一颗红黑树
30.         //如果是红黑树，就调用putTreeVal（）方法来进行添加
31.         else if (p instanceof TreeNode)
32.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
33.         
34.         else { //如果table对应索引位置已经是一个链表了，就使用for循环依次比较
35.                //（1）依次和该链表的每个元素都比较后 都不相同，就则将数据加入到该链表的最后
36.             for (int binCount = 0; ; ++binCount) {
37.                 if ((e = p.next) == null) {//先赋值再判断
38.                     p.next = newNode(hash, key, value, null);
39.                     //注意：把元素添加到链表之后立即 判断该链表是否已经达到8个节点，如果已经达到则                         //调用 treeifyBin()对当前链表进行树化（转成红黑树）
40.                     //在转成红黑树时 还要进行一个判断：
41.                     //如果该table数组的为空或者大小小于64，则对table数组进行扩容
42.                     //如果上面条件不成立，即数组大小大于等于64且链表数量达到8个，就转成红黑树
43.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
44.                         treeifyBin(tab, hash);
45.                     break;
46.                 }
47.                
48.                  //（2）如果在依次和该链表的每个元素比较的过程中发现如果有相同情况，就直接break
49.                 if (e.hash == hash &&
50.                     ((k = e.key) == key || (key != null && key.equals(k))))
51.                     break;
52.                 p = e;//在上面for循环条件已经把p.next赋值给e了，这里e又赋值给p 其实就是将p指针指                         //向p.next，然后再进行新一轮的判断，如此循环，直到有满足上面if语句的条件为止
53.             }
54.      }
55.         
56.         if (e != null) { // existing mapping for key
57.             V oldValue = e.value;
58.             if (!onlyIfAbsent || oldValue == null)
59.                 e.value = value;//替换，key对应value
60.             afterNodeAccess(e);
61.             return oldValue;
62.         }
63.     }
64.    
65.    
66.     ++modCount;//每增加一个Node，就size++
67.     if (++size > threshold)//当使用的容量 > 临界值时，就扩容
68.         resize();
69.     afterNodeInsertion(evict);
70.     return null;
71. }

复制代码

PS:关于树化

1.         for (int binCount = 0; ; ++binCount) {
2.             //（1）依次和该链表的每个元素都比较后 都不相同，就则将数据加入到该链表的最后
3.                 if ((e = p.next) == null) {//先赋值再判断
4.                     p.next = newNode(hash, key, value, null);
5.                     
6.                     //注意：把元素添加到链表之后立即 判断该链表是否已经达到8个节点，如果已经达到则                         //调用 treeifyBin()对当前链表进行树化（转成红黑树）
7.                     //在转成红黑树时 还要进行一个判断：
8.                     //如果该table数组的为空或者大小小于64，则对table数组进行扩容
9.                     //如果上面条件不成立，即数组大小大于等于64且链表数量达到8个，就转成红黑树
10.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
11.                         treeifyBin(tab, hash);
12.                     break;
13.                 }
14.                
15.                  //（2）如果在依次和该链表的每个元素比较的过程中发现如果有相同情况，就直接break
16.                 if (e.hash == hash &&
17.                     ((k = e.key) == key || (key != null && key.equals(k))))
18.                     break;
19.                 p = e;//在上面for循环条件已经把p.next赋值给e了，这里e又赋值给p 其实就是将p指针指                         //向p.next，然后再进行新一轮的判断，如此循环，直到有满足上面if语句的条件为止
20.             }

复制代码

遍历过程中p从第一个节点遍历到最后一个节点，但由于binCount是从0开始计数，所以在做树化判断时binCount
的值等于 链表长度 - 1（注意此时的链表长度没有算新插入的节点）
判断条件为 binCount >= TREEIFY_THRESHOLD - 1 ==> binCount+1(链表长度) >= TREEIFY_THRESHOLD
但此时链表新插入了一个节点

1. p.next = newNode(hash, key, value, null);

复制代码

所以链表树化的那一刻，它的真实长度应该时binCount+1+1 => 链表长度>TREEIFY_THRESHOLD(8)
即：
链表长度大于8时，treeifyBin()方法被调用
（在做树化判断时，链表长度 = binCount+1（从零计数）+1（新插入节点） = bincount +2）
（判断条件： (bincount >= 8-1) => (bincount>=7) => (bincount+2>=9) => (链表长度>=9) 长度是整数 大于等于9也就是大于8）
ps:剪枝--->如果有链表树化之后，树中的节点经过删除之后越来越少，当元素个数减少到一定程度，树会转变为了链表

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！