Hash Table

哈希表定义

在计算机科学中，哈希表是一种实现关联数组的数据结构，也称为字典或简单地称为映射；关联数组是一种将键映射到值的抽象数据类型。哈希表使用哈希函数计算一个索引，也称为哈希码，指向一个桶或槽的数组，从中可以找到所需的值。在查找过程中，键被哈希处理，得到的哈希值指示相应的值存储在哪里。通过哈希表实现的映射被称为哈希映射。

哈希表特点

• 查询、插入、删除操作的时间复杂度都是 O(1)。
• 哈希表的键值对是无序的，不能通过键值对的有序性来遍历哈希表。
• 存在哈希冲突，即不同的键值对映射到同一个桶中，需要通过哈希冲突解决方法来解决。
• 当元素过多时需要扩容，扩容时需要重新计算哈希值，重新分配桶。

哈希函数

哈希函数是哈希表的核心，它将键映射到桶中。为了保证哈希表的查询、插入、删除操作的时间复杂度都是 O(1)，哈希函数需要满足以下两个条件：

• 哈希函数计算得到的哈希值必须均匀分布在所有桶中。
• 哈希函数计算得到的哈希值必须尽可能唯一，即不同的键值对映射到不同的桶中。

常用的哈希函数有除留余数法。

哈希冲突

哈希冲突是指不同的键值对映射到同一个桶中的情况。哈希冲突会导致查询、插入、删除操作的时间复杂度增加，因此需要通过哈希冲突解决方法来解决。

开放寻址法（线性探测）

开放寻址法是一种解决哈希冲突的方法，它通过在哈希表中寻找下一个空闲桶来解决哈希冲突。

常用的开放寻址法有线性探测、二次探测、双重哈希等。

链地址法（拉链法）

链地址法是一种解决哈希冲突的方法，它通过在哈希表的每个桶中存储一个链表来解决哈希冲突。

常用的链地址法有链表、符号表等。