HashMap源码分析 IT

　　首先，HashMap 是 Map 的一个实现类，它代表的是一种键值对的数据存储形式。key和value允许为null,key不允许重复，可以接受null键和值。

　　jdk1.7中使用一个Entry数组来存储数据，jdk1.8中使用一个Node数组来存储数据，但这个Node可能是链表结构，也可能是红黑树结构。
　　jdk 8 之前，其内部是由数组+链表来实现的，继承了数组的线性查找和链表的寻址修改，而 jdk 8 对于链表长度超过（底层代码>=）8 的链表将调用treeifyBin函数转储为红黑树。因为，如果按照链表的方式存储，随着节点的增加数据会越来越多，这会导致查询节点的时间复杂度会逐渐增加，平均时间复杂度Ｏ(n)。为了提高查询效率，故在JDK１.8中引入了改进方法红黑树，以加快检索速度。此数据结构的平均查询效率为Ｏ(log n) 。

　　要了解红黑树，先要知道avl树，要知道avl树，首先要知道二叉树。

二叉树

　　二叉查找树，也称二叉搜索树，或二叉排序树。其定义也比较简单，要么是一颗空树，要么就是具有如下性质的二叉树：

　　（1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

　　（2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

　　（3）任意节点的左、右子树也分别为二叉查找树；

　　（4）没有键值相等的节点。

　　二叉树就是每个父节点下面有零个一个或两个子节点。我们在向二叉树中存放数据的时候将比父节点大的数放在右节点，将比父节点小的数放在左节点，这样之后我们在查找某个数的时候只需要将其与父节点比较，大则进入右边并递归调用，小则进入左边递归。但其存在不足，如果运气很不好我的数据本身就是有序的，比如【1，2，3，4，5，6，7】，这样就会导致树的不平衡，二叉树就会退化成为链表。所以我们推出了avl树。

avl树

　　平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度不能超过1　　

　　avl树即平衡树，他对二叉树做了改进，在我们每插入一个节点的时候，必须保证每个节点对应的左子树和右子树的树高度差不超过1。如果超过了就对其进行调平衡，具体的调平衡操作就不在这里讲了，无非就是四个操作——左旋，左旋再右旋，右旋再左旋。最终可以是二叉树左右两边的树高相近，这样我们在查找的时候就可以按照二分查找来检索，也不会出现退化成链表的情况。

　　那么平衡二叉树如何保持”平衡“呢？根据定义，有两个重点，一是左右两子树的高度差的绝对值不能超过1，二是左右两子树也是一颗平衡二叉树

　　二叉树和avl树详细讲解查看文章：二叉查找树和平衡二叉树

　　红黑树详细讲解查看文章：最容易懂得红黑树

　　平衡二叉树是一棵高度平衡的二叉树，所以查询的时间复杂度是 O(logN) 。插入的话，失衡的情况有4种，左左，左右，右左，右右，即一旦插入新节点导致失衡需要调整，最多也只要旋转2次，所以，插入复杂度是 O(1) ，但是平衡二叉树也不是完美的，也有缺点，从上面删除处理思路中也可以看到，就是删除节点时有可能因为失衡，导致需要从删除节点的父节点开始，不断的回溯到根节点，如果这棵平衡二叉树很高的话，那中间就要判断很多个节点。所以后来也出现了综合性能比其更好的树—-红黑树，后面再讲。

红黑树

　　红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

　　红黑树的特点：

　　　　1.节点是红色或黑色。
　　　　2.根节点是黑色。
　　　　3 每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
　　　　4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
　　　　5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

　　之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。
而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

HashMap的 get(Object key)方法分析(以下源码版本为jdk1.8版本)：

1 public V get(Object key) {
2         Node<K,V> e;
3         return (e = getNode(hash(key), key)) == null ? null : e.value;
4     }

　　看下hash(key)算法：

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

　　hash方法计算的值为key的hashCode值与其右移16位后的异或的结果。

　　getNode源码：

 1 final Node<K,V> getNode(int hash, Object key) {
 2         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 3         if ((tab = table) != null && (n = tab.length) > 0 &&
 4             (first = tab[(n - 1) & hash]) != null) {
 5             if (first.hash == hash && // always check first node
 6                 ((k = first.key) == key || (key != null && key.equals(k))))
 7                 return first;
 8             if ((e = first.next) != null) {
 9                 if (first instanceof TreeNode)
10                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
11                 do {
12                     if (e.hash == hash &&
13                         ((k = e.key) == key || (key != null && key.equals(k))))
14                         return e;
15                 } while ((e = e.next) != null);
16             }
17         }
18         return null;
19     }

View Code

　　Node<K,V>就是数组中存储的元素，其源码：

 1 static class Node<K,V> implements Map.Entry<K,V> {
 2         final int hash;
 3         final K key;
 4         V value;
 5         Node<K,V> next;
 6 
 7         Node(int hash, K key, V value, Node<K,V> next) {
 8             this.hash = hash;
 9             this.key = key;
10             this.value = value;
11             this.next = next;
12         }
13 
14         public final K getKey()        { return key; }
15         public final V getValue()      { return value; }
16         public final String toString() { return key + "=" + value; }
17 
18         public final int hashCode() {
19             return Objects.hashCode(key) ^ Objects.hashCode(value);
20         }
21 
22         public final V setValue(V newValue) {
23             V oldValue = value;
24             value = newValue;
25             return oldValue;
26         }
27 
28         public final boolean equals(Object o) {
29             if (o == this)
30                 return true;
31             if (o instanceof Map.Entry) {
32                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
33                 if (Objects.equals(key, e.getKey()) &&
34                     Objects.equals(value, e.getValue()))
35                     return true;
36             }
37             return false;
38         }
39     }

View Code

　　由以上代码我们可以看到，在HashMap中要找到某个元素，先根据hash(key)值来找到key对应的Node元素在数组中的位置，返回唯一的node.value。查找方式：

　　1.根据key的hash算法找到该key对应的Node在数组中的元素位置，找不到直接返回null;
　　2.可以找到元素位置，则根据key的equals方法匹配元素位置的key:
　　　　a.若相等则直接返回数组中的该元素的value值;
　　　　b.不相等则判断：该节点若属于红黑树则调用红黑树的方法查找并返回结果，否则用do{}while方式遍历链表查找；

HashMap的put(K key, V value)方法分析：　　

 1 public V put(K key, V value) {
 2         return putVal(hash(key), key, value, false, true);
 3     }
 4 
 5 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
 6     Node<K,V>[] tab; Node<K,V> p; int n, i;
 7     //如果 table 还未被初始化，那么初始化它
 8     if ((tab = table) == null || (n = tab.length) == 0)
 9         n = (tab = resize()).length;
10     //根据键的 hash 值找到该键对应到数组中存储的索引
11     //如果为 null，那么说明此索引位置并没有被占用
12     if ((p = tab[i = (n - 1) & hash]) == null)
13         tab[i] = newNode(hash, key, value, null);
14     //不为 null，说明此处已经被占用，只需要将构建一个节点插入到这个链表的尾部即可
15     else {
16         Node<K,V> e; K k;
17         //当前结点和将要插入的结点的 hash 和 key 相同，说明这是一次修改操作
18         if (p.hash == hash &&
19             ((k = p.key) == key || (key != null && key.equals(k))))
20             e = p;
21         //如果 p 这个头结点是红黑树结点的话，以红黑树的插入形式进行插入
22         else if (p instanceof TreeNode)
23             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
24         //遍历此条链表，将构建一个节点插入到该链表的尾部
25         else {
26             for (int binCount = 0; ; ++binCount) {
27                 if ((e = p.next) == null) {
28                     p.next = newNode(hash, key, value, null);
29                     //当binCount为7的时候，循环了8次，满足此条件，此时链表长度为P头结点+7=8，也就是说当链表长度>8的时候 ，将链表裂变成红黑树
30                     if (binCount >= TREEIFY_THRESHOLD - 1)
31                         treeifyBin(tab, hash);
32                     break;
33                 }
34                 //遍历的过程中，如果发现与某个结点的 hash和key，这依然是一次修改操作
35                 if (e.hash == hash &&
36                     ((k = e.key) == key || (key != null && key.equals(k))))
37                     break;
38                 p = e;
39             }
40         }
41         //e 不是 null，说明当前的 put 操作是一次修改操作并且e指向的就是需要被修改的结点
42         if (e != null) {
43             V oldValue = e.value;
44             if (!onlyIfAbsent || oldValue == null)
45                 e.value = value;
46             afterNodeAccess(e);
47             return oldValue;
48         }
49     }
50     ++modCount;
51     //如果添加后，数组容量达到阈值，进行扩容
52     if (++size > threshold)
53         resize();
54     afterNodeInsertion(evict);
55     return null;
56 }

HashMap 碰撞问题处理：

　　碰撞：所谓“碰撞”就上面所述是多个元素计算得出相同的hashCode，在put时出现冲突。HashMap解决碰撞如下：

　　当程序试图将一个key-value对放入HashMap中时，程序首先根据hash(key)返回值决定该 Node(HashMap内部类Node实现了Entry) 的存储位置：

　　　　1.如果两个 Node的 key 的 hashCode() 返回值相同，那它们的存储位置相同。
　　　　2.如果这两个 Node的 key 通过 equals 比较返回 true，则新添加 Node的 value 将覆盖集合中原有 Node的 value，但key不会覆盖。
　　　　3.如果这两个 Node的 key 通过 equals 比较返回 false，则新添加的 Node将与集合中原有 Node形成链表，而且新添加的 Node位于 Entry 链的尾部，当链表长度大于等于8，则将链表裂变成红黑树。

　　当HashMap中的数据越来越多时，发生碰撞的概率也越来越高，这个时候会对数据进行扩容，默认长度为16，负载因子为0.75，也就是数据数目达到两者乘积也就是16*0.75=12时，数组会扩容为原来的两倍，2*16=32。这个扩容操作叫做rehash，因为要对原先所有数据重新计算位置，再放入扩容后的数组中，所以如果可以确定数组长度的话，提前设置好长度，可以减少性能消耗。