Map底层之HashMap原理浅析

Myth丶恋晨 2022-05-18 10:13 260阅读 0赞

## 1.概述 ##

Map<k,v="">是常见的键值对存储接口，Java中存储键值对的数据类型都实现了这个接口，表示映射表。其中有两个核心操作get(Object key)和put(K key, V value)，分别用来获取键对应的值以及向映射表中插入键值对。

public interface Map<K,V> {
        ···
        V get(Object key);
        V put(K key, V value);
        ···
    }

HashMap是Map的常见实现类，也是Java中使用最频繁的储存键值对的结构，这篇文章我们就来看一下它的基本原理。

## ##

### 2.HashMap的工作原理 ###

*Java中的数组在添加或者删除的时候，都会复制一个新数组，比较耗内存，但是数组遍历比较高效（**寻址容易，插入和删除困难**）；然而，链表则是遍历比较慢，而添加和删除元素代价低（**寻址困难，插入和删除容易**）。HashMap则是巧妙的结合这两点——哈希表。*

HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些键值对（Entry）分散存储在一个数组中，这个数组就是HashMap的主干。

![70][]

从这张图可以看出来，HashMap是**数组+链表**实现的。在它的主干数组上，每一个元素存储的不仅是一个Entry对象，也是一个**链表的头节点**。每一个Entry通过Next指针指向它所在链表的下一个Entry节点。

**2.1-put**

一个HashMap默认的长度为16（数组长度）。当我们调用HashMap的put方法，向其中放入一个Entry（键值对）时，有这样一个问题要解决：**这个Entry对象存储在HashMap中哪个位置**？通过下面的算法来决定：

int hash = hash(key);
    int i = indexFor(hash,table.length);

假如我们向HashMap中put(100,haozz)这个元素，那么首先需要计算100这个key的hash值，然后indexFor方法对该哈希值和HashMap数组的长度进行运算（实际上是**与运算**）。得到的值即是该元素存储在该HashMap中的下标值。

这样，我们就明确了新来的Entry对象存储在HashMap中的位置。那么新的问题又来了：**如果我有两个Entry，他们通过上面的运算之后得到的下标相同，那该怎么办呢**？这个时候就该链表登场了。我们之前说过，每一个Entry有一个Next属性指向下一个Entry。当新来的Entry对象（Entry-A）映射到的下标值为2，而且2位置上已经有对象（Entry-B）的时候，它只需要插入到对应的链表即可。并且使用的是“头插法”，即后来的放在前面（因为HashMap的设计者认为后插入的元素被使用到的概率更大，遍历查找时会更快的找到）。然后记录下来：Entry-A.next=Entry-B，并且这时候，HashMap的主干数组上存储的是Entry-A（后插入的元素），Entry-A所在的链表上还有Entry-B。可以用下图表示：

![70 1][]

此时，若再进来Entry-C，则原理相同，变成用Entry-C.next=Entry-A（Entry-C ——>Entry-A ——>Entry-B）。也就是说，**数组主干上的元素都是链表中的第一个元素，也都是下标值相同的最新添加进来的元素，之前进来的则被next变量引用着**。至此，HashMap的put方法的原理就基本清楚了。附上源码：

public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value); //null总是放在数组的第一个链表中
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            //遍历链表
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                //如果key在链表中已存在，则替换为新value
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(hash, key, value, i);
            return null;
    } 
    
    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next
        //如果size超过threshold，则扩充table大小。再散列
        if (size++ >= threshold)
                resize(2 * table.length);
    }

**2.2-get**

清楚了put方法的原理之后，get方法的操作原理就比较简单了。同样根据上面的算法，算出key在HashMap中所对应的下标值，找到Entry存储的位置，如果同一个位置可能有多个Entry对象，就会得到一个由Entry对象组成的链表，然后就要顺着对应链表的头节点，一一遍历查找。下面附上源码：

public V get(Object key) {
            if (key == null)//HashMap允许key为null
                return getForNullKey();
            int hash = hash(key.hashCode());//计算该key的hash码
            //先定位到数组元素，再遍历该元素处的链表
            for (Entry<K,V> e = table[indexFor(hash, table.length)];//取出HashMap主干数组中指定索引出的值
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))//如果遍历到的元素的key和hash与被搜索的key相同
                    return e.value;
            }
            return null;
    }

**2.3-HashMap默认长度**

上面说过，**HashMap默认的长度为16**。并且当HashMap里面的数据越来越多的时候。同一个位置上的链表的就会越来越长，影响性能。所以在一定情况下，HashMap会进行扩容，即对主干数组增加长度，而且**每次扩容时（或手动初始化时）长度必须是2的幂**。这又是为什么呢？我们要从上面讲到的算法说起。

int hash = hash(key);
    int i = indexFor(hash,table.length);

每次将元素映射到HashMap主干数组的位置上时，会进行上面的算法，用key的hash值和主干数组的长度进行indexFor方法，来看一下这个方法：

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

可以看到，这里是用h（key的hash值）和length-1（主干数组的长度-1）进行了**按位取并**运算。为什么要这样做呢？我们知道，当多个元素放入HashMap的时候，有可能会映射到同样的数组位置，那么如何保证HashMap中的元素尽量均匀分布呢，举一个小例子来看一下：

1.  将("book",100)放入HashMap中；
2.  计算“book”的hashCode(3029737)，二进制为1011100011101011101001；
3.  HashMap的长度为16，Length-1结果为15，二进制为1111；
4.  **与运算**：1011100011101011101001 & 1111 = 1001，十进制为9，所以index = 9；

可以说，该算法最终得到的index结果，完全取决于key的hashcode值的最后几位（因为主干数组的长度-1的hashCode全是1）。这样做不但效果等同于取模，而且大大提高了性能。那么为什么默认长度是16呢，如果是10 会怎么样？重复刚才的运算步骤：

![70 2][]

这个结果单独看没什么问题，但是如果有一个新的hashcode为101110001110101110 1011：

![70 3][]

再换一个hashcode为101110001110101110 1111：

![70 4][]

这样一来，当我们输入的hashcode后几位不同（1001、1011、1111）的时候，运算的结果都是1001（9），也就是说当HashMap的长度为10的时候，index = 9的概率会更大，而其余的index结果永远不会出现（比如0111）。这样显然HashMap的分布是不均匀的。

反之，**当HashMap的长度为16或其他2的幂，length-1的值所有二进制位全为1，这时index的结果等同于hashcode后几位的值。只要输入的hashcode本身分布均匀，该算法的结果就是均匀的。**

**2.4-HashMap的rehash**

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，越来越多的元素会被放到HashMap中同一个index的链表上，效率低下。所以为了提高查询的效率，就要对HashMap进行扩容。

当HashMap中的元素个数超过**length（数组大小）\*loadFactor（负载因子）**时，就会进行扩容，loadFactor的默认值为0.75。默认情况下，数组大小为16，当HashMap中的元素格式超过16\*0.75=12时，就会把HashMap数组的大小扩大为16\*2=32。但这是个非常耗性能的过程，因为length改变了，需要重新计算每个元素的位置。所以如果我们可以提前预知HashMap的个数，最好还是提前预设HashMap的长度（这一点和ArrayList的初始化有相似之处）。HashMap包含如下几个构造器：

*  HashMap()：构建一个初始长度为16，负载因子为0.75的HashMap；
 *  HashMap(int initialCapacity)：构建一个初始长度为大于initialCapacity的最小的2的n次幂，负载因子为0.75的HashMap（HashMap的容量永远是2的n次幂）；
 *  HashMap(int initialCapacity, float loadFactor)：构建一个初始长度为大于initialCapacity的最小的2的n次幂，负载因子为loadFactor的HashMap

# #

## 3.HashMap与HashTable的比较 ##

Map接口常用的引申类有HashMap和HashTable。二者的区别如下：

*  HashTable继承自Dictionary，而Dictionary实现了Map接口。HashMap继承自AbstractMap，并且自身实现了Map接口；
 *  HashTable的方法是同步的（线程安全）。HashMap不是（HashMap可以使用Collections.synchronized(map)方法进行同步化，或者直接使用ConcurrentHashMap）；
 *  HashTable不允许null（key和value都不允许为null。在编译器不会报错，但在运行时会报空指针异常）。HashMap允许null值（key和value都可以），并且允许多个键所对应的value值为null，当HashMap的get方法返回null值时，既可以表示HashMap中没有该key，也可以表示该key所对应的value值为null，因此在HashMap中不能有get方法来判断是否存在某个键，应该使用containsKey()方法；
 *  HashTable中hash数组默认大小是11，增加方式是old\*2+1,。HashMap中hash数组的默认大小是16，而且扩容的话长度一定是2的幂（后面解释）;
 *  哈希值使用不同：HashTable直接使用对象的hashCode值（int hash = key.hashCode();）。HashMap重新计算hash值，并且涉及位运算

# #

## 4.HashMap引申 ##

本篇文章我们只对HashMap的基本原理做初步分析，HashMap的设计还存在许多玄妙之处。还有许多问题我们将在以后的文章的分析：

*  HashMap的存储依赖hash值的计算，因此选用String、Integer这些不会变化的类作为键会提高HashMap的效率，因为他们的hash值不会发生变化，获取对象速度将会提高；
 *  JDK1.8为HashMap增加了红黑树

参考文章：

[https://mp.weixin.qq.com/s?\_\_biz=MzIxMjE5MTE1Nw==&mid=2653191907&idx=1&sn=876860c5a9a6710ead5dd8de37403ffc&chksm=8c990c39bbee852f71c9dfc587fd70d10b0eab1cca17123c0a68bf1e16d46d71717712b91509&scene=21\#wechat\_redirect][https_mp.weixin.qq.com_s_biz_MzIxMjE5MTE1Nw_mid_2653191907_idx_1_sn_876860c5a9a6710ead5dd8de37403ffc_chksm_8c990c39bbee852f71c9dfc587fd70d10b0eab1cca17123c0a68bf1e16d46d71717712b91509_scene_21_wechat_redirect]

[70]: /images/20220518/03f4131aa6ff4c0aa2102133c01f6c3f.png
[70 1]: /images/20220518/a7b85a357729417bbb225984476e6d49.png
[70 2]: /images/20220518/581fbe70cf4d4c9ebe756953de6feea0.png
[70 3]: /images/20220518/496181d799964c428a65fdd9407e364b.png
[70 4]: /images/20220518/da81735e1ed94f7e928ed00217e5ec0e.png
[https_mp.weixin.qq.com_s_biz_MzIxMjE5MTE1Nw_mid_2653191907_idx_1_sn_876860c5a9a6710ead5dd8de37403ffc_chksm_8c990c39bbee852f71c9dfc587fd70d10b0eab1cca17123c0a68bf1e16d46d71717712b91509_scene_21_wechat_redirect]: https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653191907&idx=1&sn=876860c5a9a6710ead5dd8de37403ffc&chksm=8c990c39bbee852f71c9dfc587fd70d10b0eab1cca17123c0a68bf1e16d46d71717712b91509&scene=21#wechat_redirect