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
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》