HashMap原理详解，包括底层原理
简介：
【11月更文挑战第14天】本文介绍了数据结构基础，重点讲解了哈希表的概念及其实现方式，包括数组与链表的特点及其在HashMap中的应用。详细分析了Java 7及Java 8版本中HashMap的底层存储结构，特别是Java 8中引入的红黑树优化。此外，还探讨了哈希函数的设计、哈希冲突的解决策略以及HashMap的重要方法实现原理，如put、get和remove方法，最后讨论了HashMap的容量与扩容机制。
- 数据结构基础
- 哈希表是一种数据结构，它通过一个哈希函数将键（key）映射到一个特定的索引位置，以实现快速的插入、删除和查找操作。理想情况下，哈希函数能够将不同的键均匀地分布到哈希表的各个位置，这样可以减少冲突（多个键映射到同一个位置）。
- 数组（Array）与链表（Linked List）：
- HashMap 在 Java 中底层主要是基于数组和链表（在 Java 8 之后还引入了红黑树）来实现的。数组的特点是可以通过索引快速访问元素，时间复杂度为。但是数组的大小是固定的，在创建后不易扩展。链表则可以动态地添加和删除节点，适合存储不确定数量的元素，但查找元素的时间复杂度为。
- HashMap 的底层存储结构
- HashMap 内部维护了一个数组，数组的每个元素是一个链表的头节点。当通过
put方法添加一个键值对时，首先会计算键的哈希值，然后通过哈希值与数组长度取余（hash % length）来确定这个键值对在数组中的存储位置（桶，bucket）。如果这个桶中已经有元素（即发生了哈希冲突），则将新的键值对添加到链表的头部（头插法）。
- 仍然以数组作为底层存储结构，但当链表的长度达到一定阈值（默认为 8），并且数组长度大于等于 64 时，这个链表会被转换为红黑树。红黑树是一种自平衡二叉查找树，它可以保证在最坏情况下查找、插入和删除操作的时间复杂度为，相比链表在数据量较大且分布不均匀时性能更好。
- 哈希函数与哈希冲突解决
- 在 Java 中，
Object类有一个hashCode方法，它返回一个整数哈希值。HashMap 在计算键的存储位置时，会先调用键的hashCode方法获取哈希值，然后对这个哈希值进行进一步的处理。在 Java 8 中，hash函数的实现大致如下：
static final int hash(Object key) {
int h;
return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 这个函数对
hashCode值进行了扰动操作（异或和右移），目的是为了让哈希值的高位信息也能参与到数组索引的计算中，这样可以更好地分布键值对，减少哈希冲突。
- 哈希冲突（Hash Collision）解决：
- 如前面所述，当发生哈希冲突时，将新的键值对添加到链表中。在查找一个键时，先通过哈希函数找到对应的桶，然后遍历链表来查找键是否存在。
- 当同一个桶中的链表长度过长时，将链表转换为红黑树可以提高查找效率。当需要删除元素使得红黑树的节点数小于等于 6 时，红黑树又会转换回链表。
- 重要的方法实现原理
- 首先根据键计算哈希值，找到对应的桶位置。如果桶为空，则直接将键值对放入桶中。如果桶不为空，并且键已经存在（通过
equals方法判断），则更新键对应的旧值。如果发生哈希冲突，按照前面提到的链表或红黑树的方式进行插入。
- 同样先计算键的哈希值，找到桶位置。如果桶为空，则返回
null。如果桶不为空，在链表或红黑树中查找键，找到后返回对应的键值。
- 计算键的哈希值，定位到桶位置。在链表或红黑树中找到并删除对应的键值对，同时可能会涉及到链表转红黑树或者红黑树转链表的操作。
- 容量与扩容机制
- 初始容量（Initial Capacity）与加载因子（Load Factor）：
- HashMap 有一个初始容量，默认值为 16。加载因子默认是 0.75。加载因子用于衡量哈希表的填满程度，当哈希表中的元素个数超过
容量*加载因子时，就会触发扩容。
- 扩容是一个比较复杂的操作。当触发扩容时，会创建一个新的数组，其容量是原来的 2 倍。然后将旧数组中的所有键值对重新计算哈希值，并放入新的数组中。这个过程比较耗时，因为需要重新计算每个键值对的存储位置，所以在使用 HashMap 时，尽量预估数据量，合理设置初始容量，以减少扩容的次数。
