哈希表也称为散列表，是一种通过哈希函数将键（Key）映射到表中一个位置以便快速访问记录的数据结构。
哈希表的基本原理：
1. 哈希函数：使用哈希函数来计算键的哈希值，这个哈希值决定了键值对在数组中的存储位置，以减少哈希冲突。
2. 数组：哈希表通常使用数组来存储数据，数组的每个位置称为一个“槽”或“桶”。哈希函数的输出用于索引数组，从而确定数据应该存储在数组的哪个位置。
哈希冲突和碰撞：
哈希冲突
是指两个不同的键通过哈希函数计算得到的哈希值相同，即被映射到同一个数组位置的情况。
哈希碰撞
是哈希冲突的另一种说法，它们是同一个概念。
处理哈希冲突的方法：
1. 开放定址法（Open Addressing）：
线性探测：如果发生冲突，顺序检查表中下一个空闲位置。 - **二次探测**：在发生冲突时，按照二次方程（例如 \(i^2\), \(i^2 + 1^2\), \(i^2 + 2^2\) 等）计算下一个位置。
2. 链地址法（Separate Chaining）： - 在每个数组位置维护一个链表，所有映射到同一个位置的元素都存储在这个链表中。当发生冲突时，新元素被添加到链表的末尾。
3. 再哈希法（Rehashing）： - 当哈希表的负载因子（已存储元素数量与数组大小的比率）超过某个阈值时，使用一个新的、更大的数组来存储所有元素，并重新计算所有元素的位置。
4. 建立公共溢出区： - 为所有冲突的元素设置一个公共溢出区，所有冲突的元素都存储在这个区域。
哈希表的性能：
时间复杂度：
理想情况下，哈希表的插入、删除和查找操作的时间复杂度为 O(1)。但在最坏情况下（例如，所有元素都映射到同一个位置），时间复杂度可能退化到 O(n)。
空间复杂度：
哈希表通常需要额外的空间来存储数组和可能的链表，因此空间复杂度通常为 O(n)。