HashMap是大厂面试经常考察的内容，重点就会涉及到：数据结构与底层原理等，下面我就全面来详解@mikechen

本篇已收于mikechen原创超30万字《阿里架构师进阶专题合集》里面。

HashMap

HashMap是Java集合框架非常常用的一个类，主要用于实现哈希映射。

在Java中HashMap是基于AbstractMap类实现的，并且实现了Map接口。

如下图所示：

HashMap继承了AbstractMap类，并且同时实现了Map接口，使得它能够以键值对的形式存储和操作数据。

HashMap数据结构

从结构实现来讲，HashMap是(数组+链表+红黑树)来实现的，JDK1.8增加了红黑树部分的实现。

如下图所示：

1.数组（Array）

HashMap使用一个数组作为底层的数据存储结构，称为“桶数组”（bucket array）。

数组的每个位置被称为一个“桶”(就是上图的蓝色部分)，每个桶可以存储一个或多个键值对。

上图中的每个蓝色色圆点就是一个“桶”，也就是一个Node对象。

如下所示：

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;  // 下一个节点的引用

    // 构造函数等代码
    // ...

    // JDK 1.8中新增的红黑树相关字段
    TreeNode<K, V> parent;
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;
    boolean red;
}

Node节点是HashMap中用于存储键值对的基本单元，它包含：键、值、哈希值、下一个节点的引用等信息。

在JDK 1.8中，为了提高查找性能，当链表中的节点数量超过一定阈值时，链表会被转换为红黑树。

因此，Node在JDK 1.8中有两种形式：普通节点和红黑树节点。

2.链表（Linked List）

在哈希表中，不同的键可能会映射到相同的数组索引位置，从而引发哈希冲突。

为了解决哈希冲突的一种常见方法是链式法（Chaining），也就是链表。

如下图所示：

当哈希冲突发生时，具有相同哈希值的键值对会被存储在同一个桶中，形成一个链表。

下面是哈希冲突的链表过程：

1.哈希函数映射

当插入一个键值对时，首先通过哈希函数计算键的哈希值，然后将该哈希值映射到数组索引。

2.存储键值对

如果计算得到的数组索引上没有存储键值对，则直接将键值对存储在该位置上。

如果已经存在一个键值对，则发生哈希冲突。

3.链表存储

当哈希冲突发生时，采用链式法，在同一个哈希桶中，会创建一个链表，将具有相同哈希值的键值对链接在一起。

4.查找键值对

当查找一个键对应的值时，首先计算键的哈希值，然后根据哈希值找到数组索引。

在该索引位置的链表中搜索目标键，如果找到则返回对应的值。

3.红黑树（Red-Black Tree）

在JDK 1.8中，为了解决链表过长导致性能问题，当链表中的元素数量超过一定阈值（默认为8）时，会将链表转换为红黑树。

如下图所示：

红黑树具有更好的查找性能，因此能够在链表效率变差时提供更好的性能。

红黑树具有以下特性:

• 节点颜色： 每个节点要么是红色，要么是黑色。
• 根节点和叶子节点（NIL节点）： 根节点是黑色的，而叶子节点（NIL节点，通常是空节点）是黑色的。
• 红色节点规则： 红色节点的子节点必须是黑色的，这意味着在从根到叶子的任意路径上不能有两个连续的红色节点。
• 黑色高度平衡： 从任意节点出发，到达其叶子节点的所有路径中，黑色节点的数量必须相同。

当链表转换为红黑树时，HashMap将现有的链表节点按照键的比较顺序重新构建一棵红黑树。

这样，HashMap在平均情况下能够实现更快的查找操作，因为红黑树的查找时间复杂度为O(log n)，相比链表的O(n)要好。

总结而言，红黑树是一种用于自平衡的二叉搜索树，在HashMap中用于优化链表的性能。

4.哈希函数

HashMap的哈希函数（Hash Function）是用于将键（Key）映射到数组索引的算法。

HashMap中的哈希函数由以下步骤组成：

1)计算哈希码值（Hash Code）

对键调用其hashCode()方法，获得一个32位的整数哈希码值。

哈希码值在理想情况下应该是一个分布均匀、随机分布的整数。

2)哈希码值的处理

获得的哈希码值可能不在HashMap的数组索引范围内（即数组长度），因此需要将哈希码值映射到数组索引范围。

这通常通过对哈希码值取模操作来实现，即hashcode % 数组长度。

3)解决哈希冲突

如果不同的键获得了相同的哈希码值，即哈希冲突，HashMap使用链式法来解决冲突。

即当多个键映射到同一个索引时，它们被存储在同一个桶中，通过链表（或红黑树）链接在一起。

5.负载因子和扩容

HashMap还有一个负载因子（load factor）的概念，表示已存储的键值对数量与桶数组大小的比率。

当负载因子超过一定阈值时，HashMap会进行扩容操作。

扩容时，会创建一个更大的桶数组，将现有的键值对重新分配到新的桶中，以减少冲突，保持高效性能。

hashmap数据结构总结

综上所述，HashMap的数据结构基于哈希表，通过哈希函数将键映射到数组索引，使用链式法或红黑树来解决冲突，并通过负载因子和扩容来维持高效性能。

本篇已收于mikechen原创超30万字《阿里架构师进阶专题合集》里面。