哈希表怎么解决冲突?

0 链地址法

链地址法(Chainin):即在哈希表中使用链表来存储冲突的元素，同一个哈希值对应的元素被存储到同一个桶中的链表上。
当需要查询或删除某个元素时，首先根据哈希值找到对应的桶，然后搜索链表找到对应的元素。
链地址法是最常见的冲突解决方法，可适用于任何哈希函数。

开放地址法(Open Addressing): 即在哈希表中寻找另一个空槽来存储冲突的元素。
最常见的开放地址法有三种实现方式

1 线性探测法

线性探测法(Linear Probing): 若原哈希函数得到的槽为且已经被占用，则尝试存储到$i+1$、$i+2$等位置，直到找到一个空槽为止;

2 二次探测法

当发生冲突时，二次探测法通过使用二次探测序列来寻找下一个空闲的桶。二次探测序列是一个与哈希值相关的数列，它可以根据以下公式计算得出：

$$h(k,i)=(h(k)+c1\ast i^2+c2\ast i)\%tableSize$$

其中，h(k, i) 是通过二次探测法计算出的下一个桶的位置，h(k) 是键的哈希值，i 是探测的步长（第几次探测），c1 和 c2 是常数，tableSize 是哈希表的大小。

通过不断增加探测步长 i，可以遍历哈希表的下一个位置，直到找到一个空闲的桶或者达到了某个停止条件（如哈希表已满），然后将冲突的元素插入或查找位置。注意，哈希表的大小应该为一个素数，以保证探测序列能够覆盖整个哈希表。

二次探测法相对于线性探测法（逐个查找下一个桶）具有一定的优势，它可以更好地分散冲突元素，减少聚集现象，并且能够更高效地利用哈希表中的空间。

然而，二次探测法也存在一些问题，比如容易产生二次探测的聚集现象，并且需要解决负载因子过高时的填充问题。

3 双重散列法

哈希表的双重散列法（Double Hashing）是一种用于解决哈希冲突的方法。它在插入或查找键值对时，通过应用两个不同的哈希函数来计算步长，以找到下一个可用的桶。

双重散列法的实现步骤如下：

1. 首先，选择两个不相同的哈希函数 hash1 和 hash2。这两个哈希函数应该能够将键值对均匀地映射到哈希表的桶上。

2. 当需要插入或查找一个键值对时，首先使用 hash1 计算键的哈希值。

3. 如果对应的哈希桶为空，即未发生冲突，直接在该桶中存储或查找键值对。

4. 如果发生冲突，在哈希表的桶中进行第一次探索，计算第一步探索的步长。可以使用以下公式计算：

   step = hash2(key)
   

   其中 hash2 是第二个哈希函数。步长 step 应该始终大于0。

5. 在发生冲突的桶上进行第二次探索，并计算第二步探索的位置。使用以下公式计算：

   position = (hash1 + i * step) % tableSize
   

   其中 i 是探索的步数（第几次探索），tableSize 是哈希表的大小。

6. 重复步骤5，直到找到一个空闲桶或达到停止条件（如哈希表已满），然后在该桶中插入或查找对应的键值对。

双重散列法的优点是它能够有效地分散冲突，避免聚集现象，并且不需要额外的空间来存储其他的探测序列。此外，双重散列法通常与合适的哈希函数一起使用，能够提供较低的冲突率和较好的查询性能。

装载因子是什么

在哈希表中，装填因子（Load Factor）是指哈希表当前存储的元素数量与哈希表容量（桶数）的比例。装填因子用来衡量哈希表的填充程度，即哈希表中已经存储的元素在哈希表容量中所占的比例。

通常情况下，装填因子用小数表示，取值范围在 0 到 1 之间。例如，装填因子为 0.75 表示哈希表中已存储元素的数量是哈希表容量的 75%。

装填因子的计算公式如下：

$装填因子=元素数量/哈希表容量$

为什么装填因子很重要？

根据装填因子的大小，哈希表会采取不同的策略。当装填因子超过某个阈值时，通常会触发哈希表的扩容操作，重新调整哈希表的容量，以保持装填因子在一个合适的范围内。例如，Java中的 HashMap 类在装填因子超过默认阈值（0.75）时，会自动进行扩容。

一般来说，在装填因子较低时，哈希表会占用更多的内存空间，但查找效率较高；
而在装填因子较高时，哈希表的内存利用率更高，但查找效率可能会降低。