哈希表

苓渊大约 3 分钟

哈希表是什么

哈希表（Hash Table），也称为 散列表，是一种数据结构，它通过使用 哈希函数 将数据的键（Key）映射到数组中的位置（索引），从而实现高效的查找、插入和删除操作。哈希表的核心思想是将键映射为数组中的索引，使用数组的随机访问特性来加速数据的操作。

哈希表在海量数据处理中有着广泛应用，查找、插入、删除，接近 O(1) 的时间复杂度。

基本概念

哈希函数 是将输入（通常是键）映射为固定长度的整数值（通常是数组的索引）的函数。理想情况下，不同的输入应该映射到不同的索引，避免冲突。

键值对（Key-Value Pair）： 哈希表中的每个元素通常由一个 键（Key） 和对应的 值（Value） 组成。键通过哈希函数映射为索引，值存储在对应的索引处。

哈希冲突（Hash Collision）： 由于哈希函数的映射空间有限，不同的键有时会映射到相同的数组位置，这种情况称为 哈希冲突。

负载因子（Load Factor）： 是表中存储的元素数量与数组容量的比值。较高的负载因子意味着哈希表中装入的元素接近数组容量，可能会增加冲突的几率。通常，当负载因子超过一定阈值时，哈希表会自动扩展数组的大小以保持高效操作。

拉链法是哈希表的一种实现方法，结构是数组中嵌套链表，是 Java 中的实现方式。

底层结构首先是一个数组，每个成员存储一个指针，指向一个链表的头，链表可能为空，也可能有很多元素。

基于数组的实现创建后难于扩展，某些哈希表被基本填满时，性能严重下降，最好是在创建时需要清楚将要存储多少数据，或者定期把数据转移到更大的哈希表中（这是个费时的过程）。

fn(key) 映射函数，一个用从 key 计算元素位置的函数。

其基本计算思想是根据元素的特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，找出这个元素。

一个数组容量是有限的，映射函数可能将不同的 value 计算得出同一个地址，此时发生哈希冲突。

如果是拉链法实现的哈希表，则只需要在当前数组元素存储一个链表指针，将所有 value 存入。

开放定址法（再散列法）：以计算得出的地址为基础再次计算，直到得出一个不冲突的地址。

再 Hash 法：使用不同的映射函数，直到得出一个不冲突的地址。

负载因子是哈希表的重要参数，其定义为：哈希表中已存有的元素与哈希表长度的比值。

它是一个浮点数，表示哈希表目前的装满程度。由于表长是定值，而表中元素越大，表中空余位置就会更少，发生碰撞的可能性也会进一步增大。

哈希表的扩容策略依赖于负载因子阈值。基于性能与空间的选择，JDK 标准库将 HashMap 的负载因子阈值定为 0.75.