网站模块是啥,重庆建设网站哪个好,h5响应式网站建设,大型商城购物平台开发基本概念
哈希函数#xff08;Hash Function#xff09;是一种将输入的数据#xff08;通常是任意大小的#xff09;映射到固定大小的输出#xff08;通常是一个固定长度的值#xff09;的函数。这个输出值通常称为“哈希值”#xff08;Hash Value#xff09;或“哈希…基本概念
哈希函数Hash Function是一种将输入的数据通常是任意大小的映射到固定大小的输出通常是一个固定长度的值的函数。这个输出值通常称为“哈希值”Hash Value或“哈希码”Hash Code。
基本特点 确定性同样的输入必须产生相同的输出。快速计算哈希函数应该能够快速计算出来特别是在处理大量数据时。输出固定大小无论输入数据的大小如何哈希函数的输出应该是固定长度的。均匀分布哈希值应该尽量均匀地分布在输出空间中以减少哈希冲突。哈希冲突Hash Collision是指不同的输入数据经过哈希函数处理后映射到相同的哈希值或相同的哈希槽桶中。由于哈希表的槽位是有限的而输入的可能性是无限的因此哈希冲突是不可避免的。为了有效地管理哈希冲突我们需要使用冲突解决策略。
选择冲突解决策略的考虑因素
负载因子负载因子是指哈希表中元素个数与表的大小之比。如果负载因子过高冲突会增多性能也会下降。链式法在负载因子较高时性能依然较好而开放地址法则可能出现性能瓶颈。存储需求链式法需要额外的空间来存储链表或其他数据结构而开放地址法则不需要额外的空间但可能会在高负载因子时导致查找效率下降。查找和插入频率如果哈希表中的查找操作多于插入操作使用链式法可能更合适因为在链式法中查找冲突的元素比较简单。对于插入和查找都频繁的场景开放地址法或渐进式哈希可能表现得更好。
哈希冲突解决方法
链式法Chaining
在这种方法中每个哈希桶不仅仅存储一个元素而是存储一个元素链表或其他数据结构如链表、二叉树等。当多个元素哈希到同一个桶时它们就以链表的形式存储在该桶中。优点 实现简单。不需要额外的空间重新哈希如果槽位已满只需动态扩展链表即可。哈希表大小可以灵活扩展不需要预先确定哈希表的大小。 缺点 在极端情况下所有元素都哈希到同一个桶查找的时间复杂度可能退化为 O(n)。链表的管理和扩展可能需要额外的空间开销。
开放地址法Open Addressing
在开放地址法中所有元素都存储在哈希表的主数组中而不使用额外的数据结构如链表。当发生冲突时形成某个探测序列按此序列逐个探测散列表中的其他地址直到给定的关键字或一个空地址开放的地址为止将发生冲突的记录放到该地址中。
散列地址的计算公式Hi(key)(H(key)di) MOD m,i1,2,…,k(km-1)
H(key):哈希函数m:散列表长度di:第i次探测时的增量序列Hi(key)经过i次探测后得到的散列地址。常见的开放地址法有
1.线性探测Linear Probing
将散列表T[0,…m-1]看成循环向量。当发生冲突时从初次发生冲突的位置依次向后探测其他的地址。 增量序列di0,1,2,3,…m-1 设初次发生冲突的地址是h则依次探测T[h1]T[h2]…直到T[m-1]时又循环到表头再次探测T[0]T[1]…直到T[h-1] 探测终止的情况 1.表中对应位置已经存在该元素 2.直到循环完成仍为探测到空地址散列表满。 - 优点只要散列表未满总能快速简单的找到一个不冲突的散列地址。 - 缺点容易形成聚集clustering每个产生冲突的记录被散列到离冲突最近的空地址上从而又增加了更多的冲突机会。
2.二次探测Quadratic Probing
增量序列d ±1^2、±2^2、±3^2…±n^2 等。(具体增量序列根据题目要求来 - 优点探测序列跳跃式的散列到整个表中比线性探测减少了聚集问题。 - 缺点不能保证探测到散列表的所有地址。
3.伪随机探测法
增量序列使用一个伪随机函数来产生一个落在闭区间[1,m-1]的随机序列。
双重哈希Double Hashing
使用第二个哈希函数来计算冲突元素的探测间隔。具体来说若一个元素哈希到的位置已被占用则使用另一个哈希函数来决定下一个探测位置。 优点冲突的概率较小避免了聚集问题。 缺点需要额外的哈希函数且实现较为复杂。 再哈希法Rehashing
再哈希法是解决哈希冲突的一种方法它涉及使用多个哈希函数。当使用第一个哈希函数产生冲突时再哈希法会尝试第二个哈希函数如果仍然冲突就继续使用第三个以此类推直到找到一个没有冲突的哈希值。优点 能够降低冲突率提高查找效率。适用于处理大量数据的场景。 缺点 再哈希会导致重新计算所有元素的哈希值增加计算时间和空间开销。当哈希表扩展时可能会出现性能问题尤其是在元素非常多时。
渐进式哈希Cuckoo Hashing
渐进式哈希是一种更复杂的解决冲突的方法。在这种方法中每个元素有两个哈希位置。如果一个位置已经被占用新的元素会“逐出”原来的元素原来的元素会被移动到它的备用位置通过另一个哈希函数。这样逐步交换直到没有冲突。优点 查找操作时间复杂度始终保持在 O(1)。极低的冲突率适合大规模数据。 缺点 插入操作较为复杂。需要较多的空间且逐出和迁移元素的过程可能导致性能下降。 以人言善我必以人言罪我。 —韩非
