返回主题:内置数据结构的底层实现

知识卡片

普通读书笔记卡 · 1710.b

集合内存有价

理解等级:未标注

数组、ArrayList、LinkedList、HashSet的单元素成本差异很大;HashSet用更多内存换常数级查找、去重和删除。发散:选集合时同时问两个问题:需要哪些操作,愿意为这些操作付多少空间。

散列表通常以额外槽位、节点或装箱对象换取期望常数时间访问,这需要相应散列与负载假设。原书以Trove的基本类型专用容器减少装箱,以SparseArray的平行键值数组和二分查找换取更紧凑表示;两者优化对象不同,不能仅凭元素数比较集合成本。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    参考来源

    - 位置:《你真的会写代码吗-2021》第4章《宝贵的内存:空间效率》"常见集合的内存需求"对比表及相邻讨论(源文件:_epub-src/OEBPS/Text/0014.xhtml) - 结论依据:原文对比数组、ArrayList、LinkedList、HashSet的内存需求,明确"HashSet处于一个不同的、更庞大的阵营中,特别是因为它将每个插入的元素包装到一个新对象中。但是,它在时间优化上提供了一些独特的能力……如果应用程序需要这些服务,而且内存不受限制,那么相对其较大的内存占用量,使用HashSet通常还是更划算的"。 - 原始内容:表4-4总结了这些内存需求……HashSet处于一个不同的、更庞大的阵营中,特别是因为它将每个插入的元素包装到一个新对象中。但是,它在时间优化上提供了一些独特的能力……如果应用程序需要这些服务,而且内存不受限制,那么相对其较大的内存占用量,使用HashSet通常还是更划算的。 - 补充来源:第 4 章 宝贵的内存:空间效率,4.7 真实世界的用例;`extracted/你真的会写代码吗-2021/_epub-src/OEBPS/Text/0014.xhtml`。