C++面试问题合集之哈希-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++面试问题合集之哈希。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.什么是哈希

哈希（Hash）是一种将数据映射到固定大小的值（哈希值）的过程。在计算机科学中，哈希函数将任意长度的数据（输入）转换为固定长度的哈希值（输出）。哈希函数通过对输入数据进行计算和转换，生成一个唯一的哈希值。

哈希函数具有以下特点：

唯一性：不同的输入数据应该生成不同的哈希值，确保哈希值的唯一性。
一致性：相同的输入数据始终生成相同的哈希值，保证了数据的一致性。
散列性：即使输入数据的稍微变化，生成的哈希值也应该有较大的差异，避免碰撞（不同数据生成相同哈希值）的发生。

需要注意的是，由于哈希函数将无限数量的输入映射到有限数量的哈希值，因此可能会出现哈希碰撞的情况，即不同的输入数据生成相同的哈希值。

2.哈希冲突是什么

哈希冲突（Hash Collision）指的是不同的输入数据经过哈希函数计算后，生成了相同的哈希值。也就是说，在哈希函数的映射过程中，不同的输入数据被映射到了同一个位置或同一个哈希桶。

3.解决哈希冲突的方法

链表法（Chaining）：将哈希表的每个位置（桶）维护一个链表，当发生哈希冲突时，将冲突的元素插入到对应位置的链表中。这样可以解决同一个位置多个元素的哈希冲突问题。
开放寻址法（Open Addressing）：当发生哈希冲突时，通过一定的探查序列（如线性探查、二次探查等）去寻找下一个可用的位置进行插入。这样可以在哈希表中直接找到元素的位置，避免了链表的使用，提高了内存的利用效率。
再哈希法（Rehashing）：当发生哈希冲突时，在哈希表中重新计算一个哈希值，然后将元素插入到新的位置。再哈希法可以采用不同的哈希函数或者在同一个哈希函数上应用不同的哈希算法来计算新的哈希值，以期望分布更均匀，减少冲突的概率。
建立公共溢出区域（Overflow Area）：为哈希表设置一个特殊的区域，用于存储发生冲突的元素。当发生哈希冲突时，将冲突的元素插入到该区域中，以避免链表和探查序列的使用。但是，这种方法会增加查找的复杂性。

4.链地址法的弊端与优化

弊端：

内存占用：链表需要额外的存储空间来存储指针或链接信息，因此在哈希表的每个位置上都有一个链表节点会增加内存的开销。
缓存效率低：由于链表节点在内存中不一定是连续存储的，降低了访问效率。
链表长度不均衡：长时间运行后，可能会出现某些链表过长，导致查找、插入和删除等操作的时间复杂度变高，影响性能。

优化措施：

动态调整哈希表大小：随着元素的插入和删除，动态调整哈希表的大小，使得哈希表的负载因子保持在一个合理的范围内。当链表过长时，可以考虑增大哈希表的大小，以减少冲突的概率。
使用更好的哈希函数：选择高散列性的哈希函数，使得元素能够均匀地分布在不同的链表中，减少链表长度差异。
链表优化：可以采用一些优化策略来提高链表的性能，例如使用双向链表或跳表替代普通链表，减少遍历的时间复杂度。

5.为什么哈希表采用链地址法而不是开放地址法

冲突处理效率：

链地址法相对于开放地址法，在处理冲突时更加高效。因为链地址法在哈希表的每个位置上维护一个链表，当发生冲突时，只需要将冲突元素插入到对应链表中即可，操作简单且时间复杂度是 O(1)。而开放地址法需要逐个地探测下一个可用位置，直到找到一个空闲槽位或者探测次数达到某个限制，从而导致插入、查找和删除操作的时间复杂度增加。

存储空间利用率：

链地址法不需要保持元素间的顺序，可以让每个位置存储多个元素（通过链表等数据结构连接），因此可以更好地利用存储空间。而开放地址法需要保持元素间的顺序，因此在处理冲突时会需要额外的空间来存储探测冲突的元素，这会导致存储空间的浪费。

动态调整：

链地址法相对于开放地址法，更容易进行动态调整。在链地址法中，当负载因子较高时，可以通过增加哈希桶的数量来分散元素，从而减少冲突发生的概率，并保持较低的平均查找时间。而开放地址法需要考虑到探测序列的连续性，因此在动态调整时会比较复杂。文章来源地址https://www.toymoban.com/news/detail-794074.html

到了这里，关于C++面试问题合集之哈希的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！