知识卡片
四分之一收缩留缓冲区
动态表仍在满时倍增,但删除后装载率低于四分之一才缩半;收缩后装载率回到二分之一。
扩缩阈值相隔一段区间,可避免一两次操作就在两种重分配间反复切换,同时装载率保持常数下界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第16章 摊还分析 · 查看原书依据
halve the table size when deleting an item causes the table to become less than 1/4 full, rather than 1/2 full as before.
参考来源
- 位置:《算法导论(第4版)》第16章《摊还分析》(OEBPS/chapter016.xhtml,文本字符[35000,40000))。
- 结论依据:16.4.2 节改为满时倍增、删除后低于1/4才缩半;收缩后装载率为1/2、非空表最低装载率约1/4,避免紧贴半满阈值反复扩缩。
- 原始内容:halve the table size when deleting an item causes the table to become less than 1/4 full, rather than 1/2 full as before.