知识卡片

普通读书笔记卡 · 3629.d.2.a

四分之一收缩留缓冲区

理解等级:中级

动态表仍在满时倍增,但删除后装载率低于四分之一才缩半;收缩后装载率回到二分之一。

扩缩阈值相隔一段区间,可避免一两次操作就在两种重分配间反复切换,同时装载率保持常数下界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.