HashMap都在用，原理你真的了解吗？

喜欢ヅ旅行 2022-03-28 10:18 280阅读 0赞

### 1、HashMap基本源码实现 ###

以jdk1.8为例，hashMap是继承了AbstractMap抽象类，而AbstractMap抽象类是实现了Map接口的。Map是jdk中util工具集合系列包中基本的数据结构，如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70][] HashMap继承AbstractMap，AbstractMap实现Map接口

HashMap继承AbstractMap抽象类：

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {
    
        private static final long serialVersionUID = 362498820763181265L;
        ....    
    }

AbstractMap实现Map接口：

public abstract class AbstractMap<K,V> implements Map<K,V> {
        /**
         * Sole constructor.  (For invocation by subclass constructors, typically
         * implicit.)
         */
        protected AbstractMap() {
        }
    
        // Query Operations
        ....
    }

### 2、HashMap的基本数据结构 ###

很多人都知道，HashMap是由“数组+链表”的结构组成，但这是jdk1.8以前的说法。jdk1.8以后，HashMap有了很大改善；数据结构也改变成了：“数组+链表+红黑树”；当链表节点较多时（大于8），会转换为红黑树；否则仍是以链表结构。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 1][] 链表转换为红黑树结构存储

*  头节点指的是table表上索引位置的节点，也就是链表的头节点。
 *  根结点（root节点）指的是红黑树最上面的那个节点，也就是没有父节点的节点。
 *  红黑树的根结点不一定是索引位置的头结点。
 *  转为红黑树节点后，链表的结构还存在，通过next属性维持，红黑树节点在进行操作时都会维护链表的结构，并不是转为红黑树节点，链表结构就不存在了。
 *  在红黑树上，叶子节点也可能有next节点，因为红黑树的结构跟链表的结构是互不影响的，不会因为是叶子节点就说该节点已经没有next节点。
 *  源码中一些变量定义：如果定义了一个节点p，则pl为p的左节点，pr为p的右节点，pp为p的父节点，ph为p的hash值，pk为p的key值，kc为key的类等等。源码中很喜欢在if/for等语句中进行赋值并判断，请注意。
 *  链表中移除一个节点只需如下图操作，其他操作同理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 2][] 链表移除操作

*  红黑树在维护链表结构时，移除一个节点只需如下图操作（红黑树中增加了一个prev属性），其他操作同理。注：此处只是红黑树维护链表结构的操作，红黑树还需要单独进行红黑树的移除或者其他操作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 3][] 红黑树移除操作

*  源码中进行红黑树的查找时，会反复用到以下两条规则：1）如果目标节点的hash值小于p节点的hash值，则向p节点的左边遍历；否则向p节点的右边遍历。2）如果目标节点的key值小于p节点的key值，则向p节点的左边遍历；否则向p节点的右边遍历。这两条规则是利用了红黑树的特性（左节点<根结点<右节点）。
 *  源码中进行红黑树的查找时，会用dir（direction）来表示向左还是向右查找，dir存储的值是目标节点的hash/key与p节点的hash/key的比较结果。

### 3、HashMap的工作原理 ###

*  定位哈希桶数组索引位置

不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是“数组+链表+红黑树”的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表/红黑树，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。下面是定位哈希桶数组的源码：

// 代码1
    static final int hash(Object key) { // 计算key的hash值
        int h;
        // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    // 代码2
    int n = tab.length;
    // 将(tab.length - 1) 与 hash值进行&运算
    int index = (n - 1) & hash;

整个过程本质上就是三步：

1.  拿到key的hashCode值
2.  将hashCode的高位参与运算，重新计算hash值
3.  将计算出来的hash值与(table.length - 1)进行&运算

方法解读：

对于任意给定的对象，只要它的hashCode()返回值相同，那么计算得到的hash值总是相同的。我们首先想到的就是把hash值对table长度取模运算，这样一来，元素的分布相对来说是比较均匀的。

但是模运算消耗还是比较大的，我们知道计算机比较快的运算为位运算，因此JDK团队对取模运算进行了优化，使用上面代码2的位与运算来代替模运算。这个方法非常巧妙，它通过 “(table.length -1) & h” 来得到该对象的索引位置，这个优化是基于以下公式：x mod 2^n = x & (2^n - 1)。我们知道HashMap底层数组的长度总是2的n次方，并且取模运算为“h mod table.length”，对应上面的公式，可以得到该运算等同于“h & (table.length - 1)”。这是HashMap在速度上的优化，因为&比%具有更高的效率。

在JDK1.8的实现中，还优化了高位运算的算法，将hashCode的高16位与hashCode进行异或运算，主要是为了在table的length较小的时候，让高位也参与运算，并且不会有太大的开销。

下图是一个简单的例子，table长度为16：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 4][] 通过hash值计算索引位置

*  HashMap的put方法实现

思路如下：

1.table\[\]是否为空

2.判断table\[i\]处是否插入过值

3.判断链表长度是否大于8，如果大于就转换为红黑二叉树，并插入树中

4.判断key是否和原有key相同，如果相同就覆盖原有key的value，并返回原有value

5.如果key不相同，就插入一个key，记录结构变化一次

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
    //判断table是否为空，如果是空的就创建一个table，并获取他的长度
            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);
            else {
    //进入这里说明索引位置已经放入过数据了
                Node<K,V> e; K k;
    //判断put的数据和之前的数据是否重复
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))   //key的地址或key的equals()只要有一个相等就认为key重复了，就直接覆盖原来key的value
                    e = p;
    //判断是否是红黑树，如果是红黑树就直接插入树中
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
    //如果不是红黑树，就遍历每个节点，判断链表长度是否大于8，如果大于就转换为红黑树
                    for (int binCount = 0; ; ++binCount) {
                        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是否可要插入的key相同，如果相同就直接覆盖
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
    //如果e不是null，说明没有迭代到最后就跳出了循环，说明链表中有相同的key，因此只需要将value覆盖，并将oldValue返回即可
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
    //说明没有key相同，因此要插入一个key-value，并记录内部结构变化次数
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

*  HashMap的get方法实现

实现思路：

1.判断表或key是否是null，如果是直接返回null

2.判断索引处第一个key与传入key是否相等，如果相等直接返回

3.如果不相等，判断链表是否是红黑二叉树，如果是，直接从树中取值

4.如果不是树，就遍历链表查找

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果表不是空的，并且要查找索引处有值，就判断位于第一个的key是否是要查找的key
            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;
    //如果不是就判断链表是否是红黑二叉树，如果是，就从树中取值
                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;
        }

*  扩容机制

HashMap扩容可以分为三种情况：

第一种：使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为0。因此第一次扩容的容量为默认值DEFAULT\_INITIAL\_CAPACITY也就是16。同时threshold = DEFAULT\_INITIAL\_CAPACITY \* DEFAULT\_LOAD\_FACTOR = 12。

第二种：指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold，接着threshold = 当前的容量（threshold） \* DEFAULT\_LOAD\_FACTOR。

第三种：HashMap不是第一次扩容。如果HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍。

这边也可以引申到一个问题就是HashMap是先插入数据再进行扩容的，但是如果是刚刚初始化容器的时候是先扩容再插入数据。

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;//首次初始化后table为Null
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;//默认构造器的情况下为0
            int newCap, newThr = 0;
            if (oldCap > 0) {//table扩容过
                 //当前table容量大于最大值得时候返回当前table
                 if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                //table的容量乘以2，threshold的值也乘以2           
                newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
            //使用带有初始容量的构造器时，table容量为初始化得到的threshold
            newCap = oldThr;
            else {  //默认构造器下进行扩容  
                 // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                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"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
          if (oldTab != null) {
            //对新扩容后的table进行赋值，条件中的代码删减
            }
            return newTab;
        }

## ##

总结，HashMap虽然日常大家都在用。网上对hashMap原理讲解的博客文章也是数不胜数，想要彻底掌握其底层原理和实现流程；还是得结合jdk源码一步一步跟踪。

最后，HashMap<Key, value>中的Key在日常工作中建议尽量能用String、Integer就用这2个，会大大加快HashMap的工作效率。关于其原因，这里就不再赘述了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 5][] 同名原创公众号： **程序大视界**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70]: /images/20220328/c25efaa74b634951bf94e746ceacccf1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 1]: /images/20220328/1db272da2e304122bf373f6493db0812.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 2]: /images/20220328/b54fb22267064e86b21b2533cd4f6884.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 3]: /images/20220328/19a0685affa04685aa349d9ac2d1aa63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 4]: /images/20220328/1869ec170fa5473784a2437c3f2e511e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70 5]: /images/20220328/98e764a561d347d5b297607edba61a4e.png