seo网站关键词排名优化,长沙微信公众号,wordpress门户建站,网站页面维护系列文章#xff1a; 1. 先导片--MapSet之二叉搜索树 2. MapSet之相关概念 3. 哈希表如何避免冲突
目录
1.概念
2. 冲突-概念
3. 冲突-避免
3.1 冲突-避免-哈希函数设计
3.2 冲突-避免-负载因子调节
4. 冲突-解决
4.1 冲突-解决-闭散列
4.1.1 线性探… 系列文章 1. 先导片--MapSet之二叉搜索树 2. MapSet之相关概念 3. 哈希表如何避免冲突
目录
1.概念
2. 冲突-概念
3. 冲突-避免
3.1 冲突-避免-哈希函数设计
3.2 冲突-避免-负载因子调节
4. 冲突-解决
4.1 冲突-解决-闭散列
4.1.1 线性探测
4.1.2.二次探测
4.2 冲突-解决-开散列/哈希桶
5. 冲突严重时的解决办法 1.概念 在探讨数据结构的效率时我们常常关注于查找操作的速度。 在顺序结构中如数组或列表查找一个元素通常需要遍历整个结构这样的时间复杂度为O(N)其中N是元素的总数。 类似地在平衡树结构中查找的时间复杂度与树的高度相关也大致是O(N)。显然这两种结构的查找效率都依赖于搜索过程中进行的比较次数。 理想的搜索方法应该能够无需任何比较直接从表中获取所需元素。这可以通过构造一种特殊的存储结构来实现即通过一种称为哈希函数hashFunc的映射关系将元素的关键码直接映射到其存储位置。这样在查找时只需通过哈希函数即可快速定位到元素的具体位置。 具体操作如下 - 插入元素根据待插入元素的关键码使用哈希函数计算出该元素的存储位置并按此位置存放元素。 - 搜索元素对待查找元素的关键码应用相同的哈希函数将得到的函数值作为元素的存储位置。在结构中按此位置取元素进行比较如果关键码相等则搜索成功。 这种方法被称为哈希散列方法使用的转换函数称为哈希散列函数而构造出来的数据结构称为哈希表Hash Table或散列表。哈希表的优势在于它能够在平均情况下提供近乎常数时间的查找效率即O(1)从而极大地优化了数据的访问速度。 哈希函数hash(key) key % capacity; capacity为存储元素底层空间总的大小。 根据上面这个公式我们将1,2,3,6,7,8放入下面这个表格中得到 在使用哈希表进行搜索时由于通过哈希函数可以直接计算出数据存储的位置因此通常不需要进行多次关键码的比较这使得搜索速度非常快。然而尽管这种方法看起来非常有效但它并非没有潜在的问题。例如当我们尝试向表中插入一个关键码为33的元素时可能会出现哈希冲突问题。这是因为33计算的哈希值和3计算得出的哈希值相同导致它们在哈希表中的位置发生冲突。 2. 冲突-概念 对于两个数据元素其关键字分别为i和j如果它们通过哈希函数计算得出的哈希地址相同即Hash(i) Hash(j)这种现象称为哈希冲突或哈希碰撞。在这种情况下具有不同关键字但具有相同哈希地址的数据元素被称为“同义词”。 3. 冲突-避免 首先我们需要明确一点由于哈希表底层数组的容量通常小于实际要存储的关键字的数量冲突的发生是不可避免的。然而我们可以通过一些方法来尽量降低冲突率。 3.1 冲突-避免-哈希函数设计 引起哈希冲突的一个主要原因可能是哈希函数的设计不够合理。在设计哈希函数时应遵循以下几个原则 定义域覆盖哈希函数的定义域必须包括需要存储的全部关键码。 值域适配如果散列表允许有m个地址哈希函数的值域必须在0到m-1之间。 均匀分布计算出来的地址应能均匀分布在整个空间中以避免某些区域过于拥挤而其他区域则几乎没有数据。 简单高效哈希函数应该比较简单便于计算和实施。 常见的哈希函数包括 1. 直接定制法常用 取关键字的某个线性函数为散列地址例如Hash(Key) A*Key B。这种方法简单且能使得散列地址较均匀但需要事先知道关键字的分布情况。适合查找比较小且连续的情况。 2. 除留余数法常用 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key % pp m将关键码转换成哈希地址。 3. 平方取中法了解 假设关键字为1234对它平方得到1522756抽取中间的3位227作为哈希地址。这个方法比较适合不知道关键字的分布而位数又不是很大的情况。 4. 折叠法了解 折叠法是将关键字从左到右分割成位数相等的几部分最后一部分位数可以短些然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。适合事先不需要知道关键字的分布适合关键字位数比较多的情况。 5. 随机数法了解 选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key)其中random为随机数函数。通常应用于关键字长度不等时采用此法。 6. 数学分析法了解 设有n个d位数每一位可能有r种不同的符号。这些符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。 通过这些方法我们可以尝试减少哈希冲突的发生但在实际应用中冲突仍然是无法完全避免的。因此选择合适的冲突解决方法如链地址法或开放定址法对于提高哈希表的性能同样重要。 3.2 冲突-避免-负载因子调节 散列表的载荷因子定义α 填入表中的元素个数 / 散列表的长度 一般情况下我们的哈希表会有一个默认的负载因子--0.75f 。 负载因子和冲突率的关系粗略演示 负载因子和冲突率成反比 所以当冲突率达到一个无法忍受的程度时我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的那我们能调整的就只有哈希表中的数组的大小。 4. 冲突-解决 解决哈希冲突 两种常见的方法是 闭散列 和 开散列 4.1 冲突-解决-闭散列 闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以 把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。 那如何寻找下一个空位置呢 4.1.1 线性探测 以下是处理哈希冲突的线性探测法的具体步骤 以插入元素33为例我们首先使用哈希函数计算出其理论上的存储位置即下标为3。按照预期33应该被插入到这个位置。然而在该位置我们发现已经存在一个值为3的元素这时就发生了哈希冲突。 为了解决这种冲突我们采用线性探测的方法。这意味着我们从发生冲突的位置下标3开始依次向后查找直到找到一个空的位置。假设这个空位置的下标为j我们就将新元素33插入到这个位置。 具体步骤如下 1. 计算哈希地址通过哈希函数确定待插入元素的目标位置。 2. 检查冲突如果计算出的位置已经有元素存在说明发生了哈希冲突。 3. 线性探测从冲突发生的位置开始顺序探测下一个位置直至找到一个空位。 4. 插入元素在找到的空位处插入新元素。 在闭散列技术中处理哈希冲突时需要特别注意不能简单地物理删除哈希表中已有的元素。这是因为直接删除一个元素可能会影响其他元素的搜索。例如如果我们直接删除了元素3那么在查找元素33时可能会因为缺少原始键值3的信息而受到影响。 为了解决这个问题线性探测采用了一种标记的伪删除法。这种方法不真正删除元素而是将其标记为“已删除”。具体操作如下 1. 标记删除当需要“删除”一个元素时实际上并不从哈希表中移除它而是在该位置做一个特殊标记比如将该位置的值设置为一个特殊状态如“null”或其他标识。 2. 更新搜索在搜索时如果遇到被标记为“已删除”的位则跳过该位继续探测就像处理哈希冲突时的线性探测一样。 3. 插入和查找对于插入和查找操作遇到被标记为“已删除”的位置也按照线性探测的方式处理即继续向后寻找合适的位置。 这种方法的优点在于它避免了因删除元素而导致的连锁反应即一系列的元素都需要移动来填补被删除空间的情况。这样可以保持哈希表的稳定性并减少由于元素移动引起的潜在错误。 总结来说闭散列中的线性探测通过标记的伪删除法来处理元素的删除确保了哈希表的完整性和搜索的正确性同时最小化了由于删除操作带来的复杂性和性能损耗。 4.1.2.二次探测 线性探测的缺陷在于当发生哈希冲突时会导致数据在表中堆积起来。这是因为线性探测在寻找下一个空位置时会顺序地检查表中的每个位置直到找到空位为止。为了解决这个问题二次探测方法被提出来改善这一状况。 二次探测方法在寻找下一个空位置时采用的计算公式为Hi (H0 i^2) \% m或者 Hi (H0 - i^2) \% m。其中i 1, 2, 3…H0 是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置m 是表的大小。 例如如果要插入元素33而初始哈希位置已经有冲突使用二次探测方法可以找到合适的插入位置。 研究表明当表的长度为质数且表的装载因子 a 不超过0.5时新的表项总是能够被插入并且不会重复探查任何一个位置。这意味着只要表中有至少一半的空位置就不会出现表满的情况。在搜索时我们不需要担心表是否已满但在插入时必须确保表的装载因子 a 不超过0.5。如果超过这个阈值就必须考虑增大表的容量。 因此相比于线性探测二次探测的最大优点在于减少了冲突的发生提高了空间利用率。然而哈希表的这些方法都有其固有的缺陷即空间利用率相对较低。 4.2 冲突-解决-开散列/哈希桶 开散列法也称为链地址法或开链法首先使用散列函数为关键码集合计算散列地址。具有相同地址的关键码被归入同一个子集合每个这样的子集合被称为一个“桶”。每个桶中的元素通过一个单链表链接起来而这些链表的头结点则存储在哈希表中。 这种方法有效地将具有相同散列地址的元素组织在一起通过单链表解决冲突问题确保了元素的有序存储和高效访问。 5. 冲突严重时的解决办法 刚才我们提到了哈希桶实际上可以将一个大集合的搜索问题转化为多个小集合的搜索问题。然而如果冲突严重这意味着这些小集合的搜索性能也会受到影响。在这种情况下我们可以进一步优化这个所谓的小集合搜索问题例如 1. 每个桶的背后是另一个哈希表这种方法实际上是对冲突元素进行再次散列形成一个多层次的哈希结构。这样可以进一步减少冲突但增加了操作的复杂性。 2. 每个桶的背后是一棵搜索树这种方法使用搜索树如二叉搜索树、平衡树等来替代链表用于处理那些冲突的元素。这样可以利用搜索树的特性提高搜索、插入和删除的效率尤其是在冲突较多的情况下。 这两种方法都是对基本哈希桶方法的改进旨在提高在高冲突环境下的性能。选择合适的方法取决于具体的应用场景和数据特性。
