知识卡片

普通读书笔记卡 · 5654.d.1.a.3.d.13 · 生成模型:未记录

开地址冲突改用槽位序列

理解等级:中级

开地址表把成员放在表的槽中,不为每槽另建链。冲突后按同一键对应的探查序列继续找位置;插入、查找、删除必须采用相容的序列,才能找到此前被放到后续位置的成员。

h(k,i)由键k和探查编号i共同决定位置。对于m槽,通常要求i=0,…,m−1覆盖全部槽,避免还有空槽却因提前循环而找不到。每槽至多一个成员,成员数不能超过槽数;数组存数据地址也属于这种表示,不意味着对象本体都内嵌在数组。

133应理解为若需要继续查找,m次不重复探查能覆盖全表;找到目标或合法终止空槽仍可提前停止。起始编号必须包括i=0,正文部分“i大于0”与自身算例不符。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      元素存放在表本身中。这种特性对于某些依赖于固定大小表的应用来说非常有用。然而,因为在每个槽位上没有一个“桶”来存储冲突的元素,所以开地址哈希表需要通过另一种方法来解决冲突。

    • · 查看原书依据

      第二次访问任何槽位之前,表中所有的槽位都必须访问过一遍;否则,就说明不需要探查所有的槽位就能找到结果。 线性探查 开地址哈希表中一种简单的探查方法就是探查表中连续的槽位。正式地表述为,如果i大于0小于m-1(m为表中的槽位个数),那么一个线性探查方法的哈希函数定义为: h(k,i)=(h'(k)+i

    参考来源

    - 位置:《算法精解:C语言描述》第8章《开地址哈希表的描述》(spine1276;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1243.html;u132-ch08-014)。 - 结论依据:132短节全文与133探查定义全文已读,135/141实际table为void**支撑地址存储边界;未把开地址解释为裸数据连续内嵌。 - 原始内容:元素存放在表本身中。这种特性对于某些依赖于固定大小表的应用来说非常有用。然而,因为在每个槽位上没有一个“桶”来存储冲突的元素,所以开地址哈希表需要通过另一种方法来解决冲突。 - 位置:《算法精解:C语言描述》第8章《冲突解决》(spine1276;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1243.html;u133-ch08-014)。 - 结论依据:133应理解为若需要继续查找,m次不重复探查能覆盖全表;找到目标或合法终止空槽仍可提前停止。起始编号必须包括i=0,正文部分“i大于0”与自身算例不符。 - 原始内容:第二次访问任何槽位之前,表中所有的槽位都必须访问过一遍;否则,就说明不需要探查所有的槽位就能找到结果。 线性探查 开地址哈希表中一种简单的探查方法就是探查表中连续的槽位。正式地表述为,如果i大于0小于m-1(m为表中的槽位个数),那么一个线性探查方法的哈希函数定义为: h(k,i)=(h'(k)+i