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