知识卡片

专业/工作

散列表与平衡树的映射实现取舍

理解等级:未标注

映射类容器通常有两种底层实现:散列表把元素按散列函数算出的特征值分桶存放,平均查找复杂度是 O(1),但发生哈希碰撞时退化到 O(n),且桶数量不够时需要整体扩容重新分配,这个过程较为耗时;平衡树按元素比较建立父子关系,查找复杂度稳定维持在 O(log n),不存在碰撞退化的风险。发散:这组取舍的本质是”平均更快但有最坏情况波动”对”始终稳定但整体稍慢”,选择散列表意味着 Go 团队判断典型业务场景。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《Go语言从入门到进阶实战》第3章《容器:存储和组织数据的方式》(源文件:_epub-src/OEBPS/Text/00004.xhtml) - 结论依据:原文在该章节围绕“映射类容器通常有两种底层实现:散列表把元素按散列函数算出的特征值分桶存放,平均查找复杂度是O(1),但发生哈希…”给出定义、示例或限制条件;摘录中的术语、代码片段或对比关系直接支撑本卡片的结论。 - 原始内容:“避坑”与技巧 本章首先介绍了作者多年使用Go语言的开发经验和技巧总结,以及一些使用Go语言中可能发生的错误及优化建议,例如合理使用并发、在性能与灵活性中做出取舍后再使用反射等;接着介绍了Go语言中一个不为人知的特性——map的多键索引,利用该特性可以方便地对数据进行多个条件的索引;最后介绍了使用Go语言的Socket处理TCP粘包问题。…