知识卡片
按键定位不保留键的排序次序
哈希把键分散到槽中,以便直接从键去找对应数据;槽的相邻关系并不表示键的大小相邻。找到某个键后,沿数组下一个槽或桶内下一节点走,不能据此得到按键排序的下一个成员。
若任务需要按键顺序逐个输出、找相邻大小键或范围访问,还需另有排序/有序索引支持。哈希表可以遍历全部已存项,只是这种遍历默认不等于按键顺序;原文“不支持顺序访问”应限定到这一语境。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
下一个最小或最大键所处的槽位。与一个包含已排序元素的链表作比较,假设在链表中指定某个初始位置,那么下一个键很容易确定:只需要查找链表中的下一个元素即可。 问:在一个链式哈希表中查找元素时,什么是最坏的性能?我们如何确保这种情况不会发生? 答:当所有元素散列到同一个“桶”中时,链式哈希表的性能最差。在
参考来源
- 位置:《算法精解:C语言描述》第8章《问与答》(spine1284;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1251.html;u142-ch08-023)。
- 结论依据:142第二问完整问答实读,保留排序键的next语义并区别任何存储遍历,不引入具体产品索引建议。
- 原始内容:下一个最小或最大键所处的槽位。与一个包含已排序元素的链表作比较,假设在链表中指定某个初始位置,那么下一个键很容易确定:只需要查找链表中的下一个元素即可。 问:在一个链式哈希表中查找元素时,什么是最坏的性能?我们如何确保这种情况不会发生? 答:当所有元素散列到同一个“桶”中时,链式哈希表的性能最差。在