Java 集合系列4、家喻户晓之HashMap（上）

在前面的文章中，我们以及介绍了 List 大家族的相关知识：

• Java 集合系列1、细思极恐之ArrayList
• Java 集合系列2、百密一疏之Vector
• Java 集合系列3、骨骼惊奇之LinkedList

在接下来的文章，则主要为大家介绍一下 Java 集合家庭中另一小分队 Map ，我们先来看看 Map 家庭的整体架构：

在这篇文章中，我们主要介绍一下HashMap：

HashMap 的依赖关系：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

• 1、AbstractMap：表明它是一个散列表，基于Key-Value 的存储方式
• 2、Cloneable：支持拷贝功能
• 3、Seriablizable：重写了write/readObject，支持序列化

从依赖关系上面来看， HashMap 并没有 List 集合 那么的复杂，主要是因为在迭代上面，HashMap 区别 key-value 进行迭代，而他们的迭代又依赖与keySet-valueSet 进行，因此，虽然依赖关系上面HashMap 看似简单，但是内部的依赖关系更为复杂。

2、HashMap 成员变量

默认 桶（数组） 容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表转树 大小
static final int TREEIFY_THRESHOLD = 8;

树转链表 大小
static final int UNTREEIFY_THRESHOLD = 6;

最小转红黑树容量
static final int MIN_TREEIFY_CAPACITY = 64;

存储数据节点
static class Node<K,V> implements Map.Entry<K,V> 

节点数组
transient Node<K,V>[] table;

数据容量
transient int size;

操作次数
transient int modCount;

扩容大小
int threshold;

对比于JDK8之前的HashMap ，成员变量主要的区别在于多了红黑树的相关变量，用于标示我们在什么时候进行 list -> Tree 的转换。

附上Jdk8 中HashMap 的数据结构展示图：

3、HashMap 构造函数

HashMap 提供了四种构造函数：

m

4、HashMap Put 过程

接下来我们主要讲解一下，HashMap 在JDK8中的添加数据过程（引用）：

4.1、put(K key, V value)

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

上述方法是我们在开发过程中最常使用到的方法，但是却很少人知道，其实内部真正调用的方法是这个 putVal(hash(key), key, value, false, true) 方法。这里稍微介绍一下这几个参数：

• hash 值，用于确定存储位置
• key：存入键值
• value：存入数据
• onlyIfAbsent：是否覆盖原本数据，如果为true 则不覆盖
• onlyIfAbsent：table 是否处于创建模式

4.1.1 hash(Object key)

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

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。 这里引用一张图，易于大家了解相关机制

这里可能会比较疑惑，为什么需要对自身的hashCode 进行运算，这么做可以在数组table 比较小的时候，让高位bit 也能参与到hash 运算中，同时不会又太大的开销。

4.2、putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

由于源码篇幅过长，这里我进行分开讲解，同学们可以对照源码进行阅读

4.2.1 声明成员变量（第一步）

Node<K,V>[] tab; Node<K,V> p; int n, i;

第一部分主要县声明几个需要使用到的成员变量：

• tab：对应table 用于存储数据
• p：我们需要存储的数据，将转化为该对象
• n：数组（table） 长度
• i：数组下标

4.2.2 Table 为 null，初始化Table（第二步）

table 为空说明当前操作为第一次操作，通过上面构造函数的阅读，我们可以了解到，我们并没有对table 进行初始化，因此在第一次put 操作的时候，我们需要先将table 进行初始化。

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

从上述代码可以看到，table 的初始化和扩容，都依赖于 resize（） 方法，在后面我们会对该方法进行详细分析。

4.2.3 Hash碰撞确认下标（True）

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

在上一步我们以及确认当前table不为空，然后我们需要计算我们对象需要存储的下标了。

如果该下标中并没有数据，我们只需创建一个新的节点，然后将其存入 tab[] 即可。

4.2.4 Hash碰撞确认下标（False）

与上述过程相反，Hash碰撞结果后，发现该下标有保存元素，将其保存到变量 p = tab[i = (n - 1) & hash] ，现在 p 保存的是目标数组下标中的元素。如上图所示(引用)：

4.2.4.1 key 值相同覆盖

在获取到 p 后，我们首先判断它的 key 是否与我们这次插入的key 相同，如果相同，我们将其引用传递给 e

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

4.2.4.2 红黑树节点处理

else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

由于在JDK 8后，会对过长的链表进行处理，即 链表 -> 红黑树，因此对应的节点也会进行相关的处理。红黑树的节点则为TreeNode，因此在获取到 p 后，如果他跟首位元素不匹配，那么他就有可能为红黑树的内容。所以进行 putTreeVal(this, tab, hash, key, value) 操作。该操作的源码，将会在后续进行细述。

4.2.4.3 链表节点处理

else {
            //for 循环遍历链表，binCount 用于记录长度，如果过长则进行树的转化
                for (int binCount = 0; ; ++binCount) {
                // 如果发现p.next 为空，说明下一个节点为插入节点
                    if ((e = p.next) == null) {
                        //创建一个新的节点
                        p.next = newNode(hash, key, value, null);
                        //判断是否需要转树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        //结束遍历
                        break;
                    }
                    //如果插入的key 相同，退出遍历
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //替换 p
                    p = e;
                }
            }

链表遍历处理，整个过程就是，遍历所有节点，当发现如果存在key 与插入的key 相同，那么退出遍历，否则在最后插入新的节点。判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

4.2.4.3 判断是否覆盖

if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

如果 e 不为空，说明在校验 key 的hash 值，发现存在相同的 key，那么将会在这里进行判断是否对其进行覆盖。

4.2.5 容量判断

if (++size > threshold)
            resize();

如果 size 大于 threshold 则进行扩容处理。

5、Resize（）扩容

在上面的构造函数，和 put 过程都有调用过 resize（） 方法，那么，我们接下来将会分析一下 resize（） 过程。由于 JDK 8 引入了红黑树，我们先从 JDK 7 开始阅读 resize（） 过程。下面部分内容参考：传送门

5.1 JDK 7 resize()

在 JDK 7 中，扩容主要分为了两个步骤：

• 容器扩展
• 内容拷贝

5.1.1 容器扩展

1 void resize(int newCapacity) {   //传入新的容量
 2     Entry[] oldTable = table;    //引用扩容前的Entry数组
 3     int oldCapacity = oldTable.length;         
 4     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
 5         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
 6         return;
 7     }
 8  
 9     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
10     transfer(newTable);                         //！！将数据转移到新的Entry数组里
11     table = newTable;                           //HashMap的table属性引用新的Entry数组
12     threshold = (int)(newCapacity * loadFactor);//修改阈值
13 }

5.1.2 内容拷贝

1 void transfer(Entry[] newTable) {
 2     Entry[] src = table;                   //src引用了旧的Entry数组
 3     int newCapacity = newTable.length;
 4     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
 5         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
 6         if (e != null) {
 7             src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
 8             do {
 9                 Entry<K,V> next = e.next;
10                 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
11                 e.next = newTable[i]; //标记[1]
12                 newTable[i] = e;      //将元素放在数组上
13                 e = next;             //访问下一个Entry链上的元素
14             } while (e != null);
15         }
16     }
17 }

5.1.3 扩容过程展示（引用）

下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。

5.2 JDK 8 resize()

由于扩容部分代码篇幅比较长，童鞋们可以对比着博客与源码进行阅读。 与上述流程相似， JDK 8 中扩容过程主要分成两个部分：

• 容器扩展
• 内容拷贝

5.2.1 容器扩展

Node<K,V>[] oldTab = table;         //创建一个对象指向当前数组
        int oldCap = (oldTab == null) ? 0 : oldTab.length;      // 获取旧数组的长度
        int oldThr = threshold;                             //获取旧的阀值
        int newCap, newThr = 0;   
        // 第一步，确认数组长度
        if (oldCap > 0) {                           //如果数组不为空
            if (oldCap >= MAXIMUM_CAPACITY) {           //当容器大小以及是最大值时
                threshold = Integer.MAX_VALUE;          //设置阀值为最大值，并且不再做扩容处理
                return oldTab;
            }
            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;
        else {               // zero initial threshold signifies using defaults
            //如果数组长度与阀值为空，创建一个默认长度的数组长度
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        // 第二步，创建新数组
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;

从上面的流程分析，我们可以看到在 JDK 8 HashMap 中，开始使用位运算进行扩容计算，主要优点将会在后续数据拷贝中具体表现。

5.2.2 内容拷贝

在上述容器扩容结束后，如果发现 oldTab 不为空，那么接下来将会进行内容拷贝：

if (oldTab != null) {
            //对旧数组进行遍历
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //
                if ((e = oldTab[j]) != null) {
                    //将旧数组中的内容清空
                    oldTab[j] = null;
                    //如果 e 没有后续内容，只处理当前值即可
                    if (e.next == null)
                        通过位运算确定下标
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果 当前节点为红黑树节点，进行红黑树相关处理    
                    else if (e instanceof TreeNode)
                        ((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;
                            }
                            //高位与运算，确认索引为 愿索引+ oldCap
                            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;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }

内容拷贝，在 JDK 8 中优化，主要是：

• 通过高位与运算确认存储地址
• 链表不会出现导致，JDK 8 通过创建新链表方式进行转移

我们来看一下 JDK 8 是如何通过高位与运算确认存储位置的：

6、小结

HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。

(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。

(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。

(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

(4) JDK1.8引入红黑树大程度优化了HashMap的性能。

(5) 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。