HashMap整体结构概述
HashMap 的核心结构是一个数组，数组中的每个元素被称为一个桶（bucket）。每个桶可以存储一个链表或一棵红黑树，用于处理哈希冲突。当一个键值对被插入到 HashMap 中时，首先会根据键的哈希值计算出它应该存储在数组中的位置（桶的索引）。如果该位置已经有其他元素（即发生了哈希冲突），则会根据具体情况将新元素添加到链表或红黑树中。
HashMap 的作用
HashMap 是 Java 中 java.util 包下的一个非常重要的类，它实现了 Map 接口，用于存储键值对（key - value）映射，以下是其主要作用：
1. 数据存储与检索
可以通过唯一的键来存储和快速查找对应的值，类似于现实生活中的字典，通过单词（键）可以快速找到其释义（值）。例如，在一个学生信息管理系统中，可以使用学生的学号作为键，学生的详细信息（如姓名、年龄、成绩等）作为值存储在 HashMap 中，方便根据学号快速获取学生的详细信息。
2. 缓存数据
由于 HashMap 的查找操作效率较高，因此可以用于缓存一些经常使用的数据，避免重复计算或频繁访问数据库。例如，在一个网站中，对于一些不经常变化的数据（如商品分类信息），可以将其存储在 HashMap 中，当需要使用这些数据时，先从 HashMap 中查找，如果存在则直接使用，不存在再从数据库中获取并更新到 HashMap 中。
3. 统计元素出现的次数
可以使用键表示元素，值来表示该元素出现的次数。例如，统计一段文本中每个单词出现的次数，将单词作为键，出现的次数作为值存储在 HashMap 中，遍历文本中的每个单词，更新 HashMap 中对应单词的值。
HashMap 的原理
1. 基本结构
HashMap 内部使用数组 + 链表 + 红黑树的结构来存储数据。数组被称为哈希桶数组，数组中的每个元素称为一个桶（bucket），每个桶可以存储一个链表或一棵红黑树。
2. 哈希函数
在插入或查找元素时，首先需要计算键的哈希值。HashMap 会对键的 hashCode() 方法返回值进行二次哈希处理，以减少哈希冲突。
java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这段代码将键的哈希码的高 16 位与低 16 位进行异或运算，使得哈希码的高位也能参与到桶索引的计算中，从而减少哈希冲突的概率。
3. 确定桶的索引
根据计算得到的哈希值，通过位运算 (n - 1) & hash（其中 n 是数组的长度）来确定键值对应该存储在数组中的位置。这种方式比取模运算效率更高，因为位运算在计算机中执行速度更快。
java
int index = (table.length - 1) & hash;
4.处理哈希冲突
当两个不同的键计算得到的桶索引相同时，就会发生哈希冲突。HashMap 使用链表和红黑树来处理哈希冲突：
链表：当发生哈希冲突时，新的元素会被添加到对应桶的链表中。链表是一种简单的线性数据结构，通过
next引用将各个节点连接起来。在查找元素时，需要遍历链表，直到找到目标元素或遍历完整个链表。红黑树：当链表长度达到一定阈值（默认为 8）且数组长度达到 64 时，链表会转换为红黑树。红黑树是一种自平衡的二叉搜索树，它可以保证在最坏情况下的查找、插入和删除操作的时间复杂度为 O(log**n)。当红黑树的节点数减少到一定阈值（默认为 6）时，红黑树会转换回链表。
总结
HashMap通过哈希函数和数组、链表、红黑树的结合，实现了高效的键值对存储和查找。在大多数情况下，HashMap的插入、查找和删除操作的时间复杂度可以达到 (O(1))，但在极端情况下（如大量哈希冲突），性能可能会下降。