HashMap实现原理及源码分析

我会带着你远行 2022-03-07 05:18 344阅读 0赞

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而HashMap的实现原理也常常出现在各类的面试题中，重要性可见一斑。本文会对java集合框架中的对应实现HashMap的实现原理进行讲解，然后会对JDK7的HashMap源码进行分析。

### 一、什么是哈希表 ###

**       数组**：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)。

**线性链表**：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。

**       二叉树**：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

**哈希表**：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道，数据结构的物理存储结构只有两种：**顺序存储结构**和**链式存储结构**（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，**哈希表的主干就是数组**。

比如我们要新增或查找某个元素，我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。

**存储位置 = f(关键字)**

**　**　其中，这个函数f一般称为**哈希函数**，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70][]

查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

**       哈希冲突**

然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的**哈希冲突**，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 **计算简单**和**散列地址分布均匀,**但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是**数组+链表**的方式。

### 二、HashMap实现原理 ###

HashMap的主干是一个Node数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。

//HashMap的主干数组，可以看到就是一个Node数组，初始值为空数组{}，
    //主干数组的长度一定是2的次幂，至于为什么这么做，后面会有详细分析。
        transient Node<K,V>[] table;

Node是HashMap中的一个静态内部类,实现了Map.Entry。代码如下

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }

所以，HashMap的整体结构如下，下方的Entry就是Node。1.8后的修改

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1][]

**简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。**

### 三、重写equals方法需同时重写hashCode方法 ###

关于HashMap的源码分析就介绍到这儿了，最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题

public class MyTest {
        private static class Person{
            int idCard;
            String name;
    
            public Person(int idCard, String name) {
                this.idCard = idCard;
                this.name = name;
            }
            @Override
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (o == null || getClass() != o.getClass()){
                    return false;
                }
                Person person = (Person) o;
                //两个对象是否等值，通过idCard来确定
                return this.idCard == person.idCard;
            }
    
        }
        public static void main(String []args){
            HashMap<Person,String> map = new HashMap<Person, String>();
            Person person = new Person(1234,"乔峰");
            //put到hashmap中去
            map.put(person,"天龙八部");
            //get取出，从逻辑上讲应该能输出“天龙八部”
            System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
        }
    }
    结果：null

如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时， key(hashcode1)--> hash-->indexFor--> 最终索引位置 ，而通过key取出value的时候 key(hashcode1)-->hash-->indexFor-->最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）

所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

### 四、为什么HashMap中的&位必须为奇数（Length - 1） ###

**HashMap里的哈希算法：**

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

如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。如何进行位运算呢？有如下的公式（Length是HashMap的长度）：

> index = HashCode（Key） & （Length - 1）

下面我们以“book”的Key来演示整个过程：

*  1.计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。
 *  2.假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
 *  3.把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。

假设HashMap的长度是10，重复刚才的运算步骤：

![20190703104352908.png][]

单独看这个结果，表面上并没有问题。我们再来尝试一个新的HashCode 101110001110101110 1011 ：

![20190703104412363.png][]

让我们再换一个HashCode 101110001110101110 1111 试试 ：

![20190703104426345.png][]

是的，虽然HashCode的倒数第二第三位从0变成了1，但是运算的结果都是1001。也就是说，当HashMap长度为10的时候，有些index结果的出现几率会更大，而有些index结果永远不会出现（比如0111）！

这样，显然不符合Hash算法均匀分布的原则。

**反观长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。**

## 五、HashMap的扩容机制 ##

**何时进行扩容？**

HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put 方法插入元素之前，HashMap并不会去初始化或者扩容table。当首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化，当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容。

**扩容机制**

JDK8以后，resize过程中对Hash表数组大小的修改使用的是2次幂的扩展（指长度扩为原来2倍），这样有2个好处。

**1、**在hashmap的源码中。put方法会调用indexFor(int h, int length)方法，这个方法主要是根据key的hash值找到这个entry在Hash表数组中的位置，源码如下：

/**
    * Returns index for hash code h.
    */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

上述代码也相当于对length求模。 注意最后return的是**h&(length-1)**。如果length不为2的幂，比如15。那么length-1的2进制就会变成1110。在h为随机数的情况下，和1110做&操作。尾数永远为0。那么0001、1001、1101等尾数为1的位置就永远不可能被entry占用。这样会造成浪费，不随机等问题。 length-1 二进制中为1的位数越多，那么分布就平均。

**2、**以下图为例，其中图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，n代表length。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2][]

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 3][]

resize过程中不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图（一方面位运算更快，另一方面**抗碰撞**的Hash函数其实挺耗时的）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 4][]

源码如下：

1 final Node<K,V>[] resize() {
     2     Node<K,V>[] oldTab = table;
     3     int oldCap = (oldTab == null) ? 0 : oldTab.length;
     4     int oldThr = threshold;
     5     int newCap, newThr = 0;
     6     if (oldCap > 0) {
     7         // 超过最大值就不再扩充了，就只好随你碰撞去吧
     8         if (oldCap >= MAXIMUM_CAPACITY) {
     9             threshold = Integer.MAX_VALUE;
    10             return oldTab;
    11         }
    12         // 没超过最大值，就扩充为原来的2倍
    13         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    14                  oldCap >= DEFAULT_INITIAL_CAPACITY)
    15             newThr = oldThr << 1; // double threshold
    16     }
    17     else if (oldThr > 0) // initial capacity was placed in threshold
    18         newCap = oldThr;
    19     else {               // zero initial threshold signifies using defaults
    20         newCap = DEFAULT_INITIAL_CAPACITY;
    21         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    22     }
    23     // 计算新的resize上限
    24     if (newThr == 0) {
    25 
    26         float ft = (float)newCap * loadFactor;
    27         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    28                   (int)ft : Integer.MAX_VALUE);
    29     }
    30     threshold = newThr;
    31     @SuppressWarnings({"rawtypes"，"unchecked"})
    32         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    33     table = newTab;
    34     if (oldTab != null) {
    35         // 把每个bucket都移动到新的buckets中
    36         for (int j = 0; j < oldCap; ++j) {
    37             Node<K,V> e;
    38             if ((e = oldTab[j]) != null) {
    39                 oldTab[j] = null;
    40                 if (e.next == null)
    41                     newTab[e.hash & (newCap - 1)] = e;
    42                 else if (e instanceof TreeNode)
    43                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    44                 else { // 链表优化重hash的代码块
    45                     Node<K,V> loHead = null, loTail = null;
    46                     Node<K,V> hiHead = null, hiTail = null;
    47                     Node<K,V> next;
    48                     do {
    49                         next = e.next;
    50                         // 原索引
    51                         if ((e.hash & oldCap) == 0) {
    52                             if (loTail == null)
    53                                 loHead = e;
    54                             else
    55                                 loTail.next = e;
    56                             loTail = e;
    57                         }
    58                         // 原索引+oldCap
    59                         else {
    60                             if (hiTail == null)
    61                                 hiHead = e;
    62                             else
    63                                 hiTail.next = e;
    64                             hiTail = e;
    65                         }
    66                     } while ((e = next) != null);
    67                     // 原索引放到bucket里
    68                     if (loTail != null) {
    69                         loTail.next = null;
    70                         newTab[j] = loHead;
    71                     }
    72                     // 原索引+oldCap放到bucket里
    73                     if (hiTail != null) {
    74                         hiTail.next = null;
    75                         newTab[j + oldCap] = hiHead;
    76                     }
    77                 }
    78             }
    79         }
    80     }
    81     return newTab;
    82 }

## [六、java中Map遍历的四种方式][java_Map] ##

在java中所有的map都实现了Map接口，因此所有的Map（如HashMap, TreeMap, LinkedHashMap, Hashtable等）都可以用以下的方式去遍历。

方法一：在for循环中使用entries实现Map的遍历：

/**
    * 最常见也是大多数情况下用的最多的，一般在键值对都需要使用
     */
    Map <String,String>map = new HashMap<String,String>();
    map.put("熊大", "棕色");
    map.put("熊二", "黄色");
    for(Map.Entry<String, String> entry : map.entrySet()){
        String mapKey = entry.getKey();
        String mapValue = entry.getValue();
        System.out.println(mapKey+":"+mapValue);
    }

方法二：在for循环中遍历key或者values，一般适用于只需要map中的key或者value时使用，在性能上比使用entrySet较好；

Map <String,String>map = new HashMap<String,String>();
    map.put("熊大", "棕色");
    map.put("熊二", "黄色");
    //key
    for(String key : map.keySet()){
        System.out.println(key);
    }
    //value
    for(String value : map.values()){
        System.out.println(value);
    }

方法三：通过Iterator遍历；

Iterator<Entry<String, String>> entries = map.entrySet().iterator();
    while(entries.hasNext()){
        Entry<String, String> entry = entries.next();
        String key = entry.getKey();
        String value = entry.getValue();
        System.out.println(key+":"+value);
    }

方法四：通过键找值遍历，这种方式的效率比较低，因为本身从键取值是耗时的操作；

for(String key : map.keySet()){
        String value = map.get(key);
        System.out.println(key+":"+value);
    }

**在1.8之前，新插入的元素都是放在了链表的头部位置。1.8之后，新插入的元素都放在了链表的尾部。**

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            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;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    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;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

参考文章：[<http://www.cnblogs.com/chengxiao/>][http_www.cnblogs.com_chengxiao]

[https://www.liangzl.com/get-article-detail-7251.html][https_www.liangzl.com_get-article-detail-7251.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70]: /images/20220307/d9b54e210f0b47849c29ff61b81f3bd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1]: /images/20220307/0772dbe7f3ed416cb9323ed9193ba968.png
[20190703104352908.png]: /images/20220307/8175ffe619f94a4b8ee08c25c0b7c020.png
[20190703104412363.png]: /images/20220307/8a3d516946f84626b2639a48ae472497.png
[20190703104426345.png]: /images/20220307/ec4d37d8637040039e863b1a415fec15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2]: /images/20220307/58b4fec315034ce3a9eb49398ef9415e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 3]: /images/20220307/3e0cc8cd6b2647af9789d4d95a62dde5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 4]: /images/20220307/7cd11b010bd4401097e68107fa5a8bb6.png
[java_Map]: https://www.cnblogs.com/damoblog/p/9124937.html
[http_www.cnblogs.com_chengxiao]: http://www.cnblogs.com/chengxiao/
[https_www.liangzl.com_get-article-detail-7251.html]: https://www.liangzl.com/get-article-detail-7251.html