dede网站被黑,网站做com合net的区别,建立网站需要多少钱稻挺湖南岚鸿有名,金牛区建设审批网站我们面试时经常被问到HashMap是怎么解决哈希冲突的#xff0c;很多同学对其含糊其词、一知半解。因此小编对相关知识进行了总结#xff0c;希望帮助读者加深对其理解。
哈希表就是通过散列函数将键映射到定值#xff0c;简单来说就是一个键对应一个值。
而通过散列函数映射…我们面试时经常被问到HashMap是怎么解决哈希冲突的很多同学对其含糊其词、一知半解。因此小编对相关知识进行了总结希望帮助读者加深对其理解。
哈希表就是通过散列函数将键映射到定值简单来说就是一个键对应一个值。
而通过散列函数映射时将两个键映射到了同一个值即这两个键将被哈希表映射到同一个位置这种情况就被称为哈希冲突。 解决哈希冲突通过有四种方法 链接法开放寻址法再哈希法哈希桶扩容 1. 链接法
每个哈希表的槽位维护一个链表或其他数据结构当多个元素被哈希到同一个槽位时它们会被放在这个槽位的链表中。查找时会遍历链表插入时也会直接加到链表中。
假设我们有一个哈希表哈希函数将键值映射到以下槽位
0: [5, 15]1: []2: [2]3: []4: [4]当我们插入键值 5 和 15 时它们都被映射到槽位 0。因此它们会形成一个链表
槽位 0: [5 - 15]槽位 1: []槽位 2: [2]槽位 3: []槽位 4: [4]
另外 推荐一个程序员免费学习的编程网站我爱编程网www.love-coding.com 涵盖 Java几乎覆盖了所有主流技术面试题还有市面上最全的技术精品系列教程免费提供。
2. 开放寻址法
当发生冲突时算法会寻找下一个可用的槽位。常见的探查方式有线性探查、二次探查和双重哈希等。这种方法不使用额外的存储结构而是在哈希表内部处理所有元素。开放寻址法的几种常见探测方法确实包括线性探测、二次探测和双重散列。以下是每种方法的详细说明和示例
2.1. 线性探测
在发生冲突时线性探测会逐个检查后续的槽位直到找到一个空槽。例如
假设哈希函数为 h(k) k % 5。 插入 1 → 槽位 1成功插入 6 → 槽位 1冲突检查 2成功插入 11 → 槽位 1冲突2冲突3成功 最终哈希表
槽位 0: []
槽位 1: [1]
槽位 2: [6]
槽位 3: [11]
槽位 4: []2.2. 二次探测
二次探测在发生冲突时采用平方递增的方式查找空槽。例如
哈希函数仍然假设是 h(k) k % 5。
插入 1 → 槽位 1成功插入 6 → 槽位 1冲突检查 1^2 → 2成功插入 11 → 槽位 1冲突检查 1^2冲突2^2 → 4成功
最终哈希表
槽位 0: []
槽位 1: [1]
槽位 2: []
槽位 3: []
槽位 4: [6]2.3. 双重哈希
双重散列使用第二个哈希函数来决定步长以解决冲突。例如
假设第一个哈希函数 h1(k) k % 5第二个哈希函数 h2(k) 1 (k % 4)。
插入 1 → 槽位 1成功插入 6 → 槽位 1冲突步长 h2(6) 1 (6 % 4) 3检查 1 3 4成功插入 11 → 槽位 1冲突步长 h2(11) 1 (11 % 4) 3检查 1 3 4冲突再检查 4 3 2成功
最终哈希表
槽位 0: []
槽位 1: [1]
槽位 2: [11]
槽位 3: []
槽位 4: [6]3. 再哈希法
在发生冲突后可以使用另一个哈希函数对该元素进行再哈希找到一个新的槽位。
使用初始哈希函数 h1(k) k % 5当插入 10 时 h1(10) 0槽位 0 已占用 使用新的哈希函数 h2(k) (k / 5) % 5计算 h2(10) 2槽位 2 已占用 再次使用 h1计算 h1(10 1) 1槽位 1 已占用h1(10 2) 3放入槽位 3
最终哈希表如下
槽位 0: [0]
槽位 1: [1]
槽位 2: [2]
槽位 3: [10]
槽位 4: [4]4. 哈希桶扩容
如果哈希表的负载因子超过某个阈值可以增加哈希表的大小并重新计算所有元素的哈希值并重新分配到新的槽位。这有助于减少冲突并提高性能
哈希表的负载因子是一个衡量哈希表填充程度的重要指标通常用公式表示为负载因子 哈希表中的元素数量 / 哈希表的槽位总数负载因子的意义高负载因子当负载因子接近或超过 1 时表示哈希表的槽位几乎被填满可能导致更多的哈希冲突从而影响查找、插入和删除的性能。
低负载因子负载因子较低时哈希表的空槽较多冲突较少性能较好但会导致内存浪费。
负载因子的调整通常当负载因子超过某个设定的阈值例如 0.7 或 0.75就会进行扩容。扩容时哈希表的槽位数量增加所有元素需要重新哈希并放入新的槽位中。假设哈希表的大小为 5当前负载因子超过 0.7我们决定扩容到 10。在扩容时所有元素的哈希值需要重新计算
原哈希表
槽位 0: [0]
槽位 1: [1]
槽位 2: [2]
槽位 3: [3]
槽位 4: [4]扩容后哈希函数改为 h(k) k % 10插入后的哈希表
槽位 0: []
槽位 1: [1]
槽位 2: [2]
槽位 3: [3]
槽位 4: [4]
槽位 5: [5]
槽位 6: []
槽位 7: []
槽位 8: []
槽位 9: []5.方法比较
5.1. 链接法
优点
容易实现简单明了。动态性好可以存储任意数量的元素只受限于内存。插入和删除操作较快不需要重新哈希。
缺点
在某些情况下链表可能会很长导致查找性能下降。如果链表过长可能导致性能接近于线性查找。需要额外的内存来存储链表节点。
5.2. 开放寻址法
优点
所有元素都存储在哈希表内部节省了额外的内存。不需要额外的链表查找时不需要遍历。
缺点
哈希表的负载因子需要控制在较低水平通常小于 0.7否则性能显著下降。在频繁冲突的情况下查找效率会下降且可能需要进行多次探测。删除操作复杂可能导致“探测链”的问题影响后续查找性能。
5.3. 再哈希法
优点
通过使用不同的哈希函数能有效地减少冲突。可与其他方法结合使用灵活性高。
缺点
需要额外的计算和存储开销可能导致性能下降。在大量元素插入时可能需要频繁地进行哈希计算。
5.4. 哈希桶扩容
优点
通过扩容可以有效降低负载因子从而减少冲突。能够保持较高的性能特别是在处理大量数据时。
缺点
扩容过程可能需要遍历整个哈希表重新计算哈希值导致短时间内性能下降。增加了内存的使用和管理复杂度。
