hashmap底层实现原理和扩容机制

哈希表（Hashmap）是一种常见的数据结构，它的底层实现原理主要基于哈希函数和数组。当插入、查找或删除元素时，首先通过哈希函数将键（key）转换为一个索引值，然后在对应的数组位置存储或访问值。这种操作通常具有常数时间复杂度O(1)，但在哈希冲突较多时效率会下降。

哈希冲突是指不同的键可能计算出相同的索引。处理哈希冲突的方法有很多种，最常见的有两种：

1. **开放寻址法**（Open Addressing）：遇到冲突时，寻找下一个空闲的位置存放元素，直到找到合适的为止。比如线性探测（Linear Probing）、二次探测（Quadratic Probing）或双散列（Double Hashing）。

2. **链地址法**（Separate Chaining）：每个数组元素不再直接存储值，而是指向一个链表，将所有冲突的元素放在相应的链表中。当我们按索引查找时，如果该位置不是我们想要的值，就沿着链接链表继续查找。

扩容机制是为了应对数据增加导致的哈希冲突增多。当哈希表的装载因子（已存储元素数量/总容量）超过预设阈值，通常为0.75或0.8，系统会选择扩大哈希表的大小，新表通常是原表的两倍。扩容的具体步骤包括：
- 创建一个新的更大的哈希表。
- 遍历旧表中的每一个元素，重新计算新的键对应的索引，并把元素插入到新表的相应位置。
- 将旧表的数据迁移至新表。
- 更新旧表为只读状态，或者销毁旧表以释放内存。