Java HashMap原理解析

HashMap是Java中常用的一种数据结构，主要用于存储键值对。它基于哈希表实现，其中键和值都可以为null。HashMap有着优秀的插入和查找效率，因此得到了广泛的应用。本文将对Java HashMap的具体实现进行详细阐述，包括哈希表的结构、扩容机制、实现原理以及在Java8中的优化。

一、哈希表的结构

HashMap底层是一个“链表散列”的结构，即数组和链表的结合体。具体而言，HashMap底层是一个数组(table数组)，数组中的每个元素称为桶(bucket)，每个桶中又存放着链表。当键值对被put进Hashmap中时，通过hash函数计算出对应的hash值（即桶的index），然后将键值对加入到对应桶的链表中。

下面是一个简单的HashMap示意图：

             +----+    +----+
    table[0] |    | -> |    |
             +----+    +----+
    table[1] |    | -> |    |
             +----+    +----+
          ... 
             +----+    +----+             +----+
    table[n] |    | -> |    | -> ... -> |    |
             +----+    +----+             +----+

上图中table数组长度为n，每个元素是一个链表的头结点。每个链表头节点代表桶，对应的链表中存储了hash值相同的键值对。

二、扩容机制

当HashMap中存储的键值对数量达到一定程度时（即超过了容量*负载因子），HashMap就需要对table数组进行扩容，以保证存储空间的充足。

Java8之前的默认负载因子为0.75，意味着table数组的容量为n时，最多可存放n*0.75个键值对。当所存储的键值对数量即将超过容量时，HashMap会将table数组的长度扩大为原来的两倍，即将容量翻倍，然后将原来的键值对重新哈希到新数组中。

下图是HashMap扩容前后的对比示意图：

    // table长度为4，负载因子为0.75，最多存储3个键值对
                    +--------------+
                    |              |
                    v              |
    +------+------+------+------+
    | node | node | null | null |
    +------+------+------+------+

    // 添加第4个键值对时，HashMap扩容，将table长度扩大为8
                           +------------------------+
                           |                        |
                           v                        |
    +------+------+------+------+------+------+------+------+ 
    | node | node | null | null | null | null | null | null | 
    +------+------+------+------+------+------+------+------+

扩容时，原来的键值对仍然存储在原有的桶对应的链表中，而新添加的键值对则可能会散落到新的桶链表中。

三、实现原理

HashMap是一个典型的哈希表，它本质上是通过哈希函数将键映射到桶的位置，然后将键值对存储在对应桶的链表中。HashMap中使用的哈希表具有以下特点：

哈希表桶数量不固定，动态扩容；
哈希函数计算尽可能地减少哈希冲突发生的概率；
键值对存储方式为链表；
链表长度较长时，自动转化为红黑树，以提高查找效率；
键和值均可为null。

根据Java8的源码，HashMap的哈希函数实现如下：

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

可以看出，哈希函数主要由两个步骤组成：获取键的hashCode，然后通过位运算（异或运算和无符号右移操作）将高位的影响降低，使得得到的hash值更加乱序。

对于哈希冲突的处理方式，HashMap采用的是拉链法。即当出现哈希冲突时，将键值对添加至对应桶的链表中，之后根据键的equals方法找到对应的节点，即可获取或修改对应的值。

在Java8中，为了提高HashMap的查找效率，引入了红黑树的优化。当桶的长度大于等于8时，将链表转化为平衡树。通过红黑树的查找方式，可以将查找效率提高至O(log n)。

四、在Java8中的优化

在Java8中，HashMap进行了大量的优化，主要有以下几点：

哈希表的长度不再以2的整数次幂为基础，而是使用保持2的整数次幂的最小值的方法来分配桶的数量。
桶的数量很少，因为HashMap使用了红黑树，这样链表很长的目标性从O(n)变成了O(log n)。
引入了TreeNode，当桶中链表的长度超过8时，链表会转化为红黑树，以提高查找效率。
当链表的长度小于等于6时，会转为链表，避免了因为节点太少转换为树而带来的额外开销。
在遍历HashMap时，使用了迭代器，使得在遍历时可以通过指向后一个元素的指针，快速进行下一轮迭代。

下面是Java8中红黑树的示意图：

    +-------------+
    |             |
    v             |
  +------+     +------+
  | node |---->| node |--->...
  +------+     +------+
             |     |
             v     v
           +-----+-----+
           | 黑(bo) | 黑(bo) |
           +-----+-----+
             |     |
             v     v
           +------+------+
           | node | node |
           +------+------+
           |      |      |
           v      v      v
           .      .      .
           .      .      .
           .      .      .

五、代码演示

以下代码演示了如何创建HashMap，添加键值对和遍历HashMap：

import java.util.*;

public class HashMapDemo {
    public static void main(String[] args) {
        // 创建HashMap并添加键值对
        Map map = new HashMap();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);

        // 遍历HashMap
        for (Map.Entry entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

输出：

Key: orange, Value: 3
Key: banana, Value: 2
Key: apple, Value: 1

六、总结

本文对Java HashMap进行了详细的阐述，包括哈希表的结构、扩容机制、实现原理以及在Java8中的优化。HashMap是Java中非常重要的数据结构之一，在实际开发中经常用来存储大量的键值对。熟悉HashMap的实现原理，有助于我们更好地理解其使用方法，避免出现一些隐晦的问题。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/199212.html