java集合框架面试题-解释HashMap的工作原理

什么是HashMap？

HashMap是Java中的一种数据结构，用来存储键值对（key-value pairs）。它允许通过键快速查找对应的值。HashMap特别适合用在需要快速插入、删除和查找操作的场景。

HashMap的工作原理

1. 哈希函数（Hash Function）：

   • 当你向HashMap添加一个键值对时，首先会通过一个哈希函数将键转换成一个整数值，这个整数值叫做哈希码（hash code）。
   • 哈希函数的作用是将任意类型的键映射到一个固定范围内的整数，这样就可以在数组中定位到存储位置。

2. 数组和链表（或红黑树）结合：

   • HashMap内部维护了一个数组，这个数组的每个位置称为“桶”（bucket）。
   • 每个桶中可以存放多个键值对。当哈希码确定了某个键应该放在哪个桶时，如果这个桶已经有其他键值对了，那么就会用链表（或红黑树）来存储这些键值对。

3. 处理冲突（Collision Handling）：

   • 当两个不同的键通过哈希函数得到了相同的哈希码（即映射到同一个桶），这就叫做哈希冲突（collision）。
   • HashMap使用链表（在Java 8之后，当链表长度超过一定阈值时，会转换为红黑树）来处理这种冲突。每个桶中会有一个链表，链表中的每个节点存储一个键值对。

4. 查找操作：

   • 查找时，首先用哈希函数计算出键的哈希码，然后找到对应的桶。
   • 在桶中，如果是链表结构，就遍历链表找到匹配的键；如果是红黑树结构，就在树中查找匹配的键。
   • 找到匹配的键后，就可以返回对应的值。

5. 扩容（Rehashing）：

   • 当HashMap中的元素数量超过一定比例（称为负载因子，默认是0.75）时，HashMap会进行扩容。
   • 扩容的过程包括创建一个更大的数组，并将所有现有的键值对重新分配到新的数组中。这一过程叫做rehashing。

总结

HashMap通过哈希函数将键映射到数组中的某个位置（桶），并使用链表或红黑树来处理哈希冲突。查找、插入和删除操作都可以通过这种结构快速完成。扩容机制确保了HashMap在元素数量增加时仍然能高效运行。