5. HashMap的工作原理是什么？如何处理哈希碰撞？

PangHu大约 4 分钟

HashMap是Java集合框架中的一个用于存储键值对的集合。它基于哈希表（Hashtable）实现，允许以常数时间复杂度（O(1)）进行插入、删除和查找操作。以下是HashMap的工作原理和关键概念：

哈希函数:
- 当你将一个键值对插入到HashMap中时，HashMap会对键调用hashCode()方法，生成一个整数哈希码。然后，HashMap通过哈希函数将这个哈希码转换为数组中的索引位置，以确定键值对的存储位置。
- 哈希函数通常是通过对哈希码进行某种形式的压缩（如取模）来计算出数组的索引。
数组和链表（或红黑树）结构:
- HashMap底层维护了一个数组（称为桶或桶数组），每个桶存储一个链表（在Java 8及以后版本中，如果链表长度超过一定阈值，会转换为红黑树）。
- 当键的哈希码被映射到数组中的一个索引时，键值对被插入到该索引对应的链表（或树）中。
哈希碰撞:
- 哈希碰撞发生在不同的键被哈希到同一个索引时。此时，这些键值对会被存储在同一个桶中的链表或树结构中。
- 当有哈希碰撞时，HashMap会将新键值对添加到链表的头部（或树结构中）。
查找和删除操作:
- 在查找或删除键时，HashMap首先通过键的哈希码计算出对应的索引，然后遍历桶中的链表（或树）来查找匹配的键。
- 如果找到匹配的键，则返回对应的值或删除对应的键值对。
负载因子和再哈希:
- HashMap有一个负载因子（默认值为0.75），用于决定何时进行再哈希（扩容）。
- 当HashMap中存储的键值对数量超过负载因子与桶数组容量的乘积时，HashMap会自动扩展其容量（通常是原来的两倍），并重新分布所有的键值对到新的桶数组中。

如何处理哈希碰撞？

HashMap使用链地址法（Separate Chaining）**和**红黑树两种方式来处理哈希碰撞：

链地址法（Separate Chaining）:
- 当多个键映射到同一个数组索引时，HashMap使用链表在该索引处存储所有这些键值对。
- 当你插入一个新的键值对并且发生碰撞时，HashMap会将新键值对插入到链表的头部。
- 在查找和删除操作时，HashMap会遍历链表以找到匹配的键。
红黑树（Java 8及以上版本）:
- 在Java 8中，为了提高性能，当链表的长度超过一定阈值（默认是8）时，HashMap会将链表转换为红黑树。
- 红黑树是一种自平衡的二叉搜索树，可以将查找、插入和删除的时间复杂度从O(n)降低到O(log n)。
- 当桶中的元素较少时，HashMap会将红黑树转换回链表以节省内存。

示例：HashMap中的哈希碰撞处理

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();

        // 插入键值对
        map.put(1, "Value1");
        map.put(2, "Value2");
        map.put(3, "Value3");

        // 当发生哈希碰撞时，这些键值对会被存储在同一个桶中
        map.put(4, "Value4");
        map.put(5, "Value5");

        // 查找键值对
        System.out.println(map.get(1));  // 输出: Value1
        System.out.println(map.get(2));  // 输出: Value2
    }
}

总结

HashMap的工作原理: 基于哈希表，通过哈希函数将键映射到数组中的索引位置，并通过链地址法或红黑树处理哈希碰撞。
哈希碰撞的处理: 采用链表和红黑树的结合方式处理哈希碰撞，当链表长度超过阈值时，转换为红黑树。
负载因子和再哈希: 当存储的键值对超过一定数量时，HashMap会自动扩容，并重新分配键值对的位置。

理解HashMap的工作原理以及它如何处理哈希碰撞，可以帮助你在实际开发中有效地使用这个数据结构，并优化代码性能。