[哈希表中不仅反映数据元素的存储位置]哈希表的存在是为了解决获取元素的时间复杂度问题

沉淀，分享，成长，让自己和他人都有所收获！

哈希表的存在是为了解决可以以O时间复杂度直接索引到指定元素的问题。

这是什么意思？我们使用数组来按顺序存储元素。当我们需要获取一个元素时，我们需要遍历数组来获取指定的值。如图所示；

这样，通过循环遍历比较获得指定元素的操作的时间复杂度为O，也就是说如果你的业务逻辑实现中存在这样的代码，那就很蹩脚了。那我该怎么办？这就介绍了哈希表的设计。

在计算机科学中，哈希表是一种实现关联数组的抽象数据结构，它通过哈希计算将键映射到值。

也就是说，我们计算一个键值的hash，从一个长度为2的n次方的数组中减去一来做and运算，从而计算出槽对应的索引，并将数据存储在索引下。这样，在获取指定数据时，只需要根据存储的方式重新计算索引ID，就可以获取并处理槽上对应的数据，这样时间复杂度为o .如图所示；

虽然哈希解决了获取元素的时间复杂度问题，但大多数时候只是一种理想的情况。随着元素数量的增加，很可能会出现哈希冲突，或者哈希值波动很小，导致索引计算相同，即一个索引位置会有多个元素。如图所示；

当下标索引03与中的槽发生冲突时，情况变得更糟，因为它不能满足O时间复杂度获取元素的需求。

只要哈希桶的长度由负载因子合理控制，每个元素搜索的平均时间复杂度与桶中存储的元素数量无关。此外，许多哈希表设计允许任意插入和删除键值对，并且每个操作的平均成本是摊销的。

好了，那么介绍了这么多，付晓哥就带大家做一些关于哈希的数据结构，通过练习会更容易理解。

从测试结果可以看出，map.get在碰撞前的值为，两次索引碰撞后存储的值为。

这是使用哈希时必须解决的问题。无论元素的数量是已知的，都可以通过扩展数组的长度或将冲突的元素存储在链表中来解决。

此时，当元素发生冲突时，相同位置的所有元素都将存储在链表中。获取时，需要遍历存储多个元素的链表。

此时，第一次和第二次获得的01位置的元素都是，不替换元素。因为此时的元素存储在链表中。

开放式寻址设计将在哈希桶上搜索冲突元素的新位置，并且该位置将从当前冲突位置向后搜索，直到找到空位置用于存储。

通过测试结果可以看出，开放寻址也可以通过寻址和存储碰撞元素来解决哈希索引冲突的问题。

说明：合并哈希是开放寻址和单独链接的混合，冲突节点在哈希表中链接。该算法适用于内存分配固定的哈希桶，存储元素时通过识别哈希桶上最大的空槽可以解决哈希合并中的冲突。

哈希的最大目的是链接碰撞元素，避免需要寻找碰撞元素而导致的循环遍历。也就是说，元素A和B在存储时会发生冲突，所以在找到元素A时可以快速索引元素B的位置。

与直接使用开放式寻址相比，这种链接方式可以提高索引的性能。因为在实际的数据存储中，一个元素的下一个位置不一定是空的，可能已经被其他元素占用了，这样就增加了索引的数量。因此，使用直接指向地址的方式会更好地提高索引性能。

说明：这个名字很有意思，也代表了它的数据结构。布谷鸟孵化时，小鸡将其他蛋或幼崽推出巢穴；像这样的数据结构将使用两组键哈希表将冲突的元素推入另一个键哈希表。

当多个键被映射到同一个单元格时，就会发生这种情况。杜甫hash的基本思想是用两个hash函数而不是只用一个来解决冲突。

这为哈希表中的每个键提供了两个可能的位置。在该算法的一个常见变体中，哈希表被分成两个大小相等的较小的表，每个哈希函数为这两个表中的一个提供一个索引。两个散列函数也可以为单个表提供索引。

在实践中，布谷鸟哈希法比线性检测慢20-30%左右，线性检测是常用方法中最快的。但是，由于其最坏情况下的搜索时间保证，当需要实时响应速度时，cuckoo hash仍然是有价值的。hash的一个优点是它的非链表属性，非常适合GPU处理。

从测试结果可以看出，cuckoo hash可以通过两个哈希函数解决索引冲突问题。然而，这个检测过程是耗时的。

说明：跳房子散列法是一种基于开放寻址的算法。它结合了cuckoo散列线性检测和链接元素，并且通过桶邻域3354的概念，结合了给定被占用桶周围的任何后续桶，也称为“虚拟”桶。该算法旨在当哈希表的负载因子增加超过90%时提供更好的性能。它还在并发设置中提供了高吞吐量，因此非常适合实现可调整大小的并发哈希表。

该算法使用n个桶的数组。对于每个桶，其邻域是h个连续桶的小集合。邻域的期望属性是在邻域的桶中找到一个项目的成本接近于在桶本身中找到它的成本。在最坏的情况下，邻域必须足够大以容纳几个项目，但平均值只能是一个常数。如果桶的邻域被填满，则调整表格的大小。

通过测试我们可以看到，hopscotch hash会在它原来的hash数组条目中找到，或者在下一个H-1的相邻条目之一中找到对应的冲突元素。

说明：罗宾汉哈希是一种基于开放寻址的冲突解决算法；通过移动离其“原始位置”最远或最长的元素来检测序列长度，从而解决冲突。

0912和01有哈希索引冲突，计算并调整偏移量。碰撞元素的位移由最长位置检测。

从测试结果和调试可以看出，哈希索引冲突是通过探针序列长度最远或最长的元素与其“原始位置”的位移来解决的。您可以将断点调试验证添加到该块中。

介绍哈希表。

为什么要用哈希表？

拉链寻址和开放式寻址的区别

有没有其他方法可以解决hash哈希索引冲突

在对应的Java源代码中，对于哈希索引冲突提供了怎样的解决方案？