第 16 章 集合(2)
吉姆•布兰迪
16.5 HashMap<K, V> 与 BTreeMap<K, V>
Map 是键 - 值对[称为条目(entry)]的集合。任何两个条目都不会有相同的键,并且这些条目会始终按某种数据结构进行组织,从而使你可以通过键在 Map 中高效地查找对应的值。简而言之,Map 就是一个查找表。
Rust 提供了两种 Map 类型:HashMap<K, V> 和 BTreeMap<K, V>。这两种类型共享许多相同的方法,区别在于它们如何组织条目以便进行快速查找。
HashMap 会将键和值存储在哈希表中,因此它需要一个实现了 Hash 和 Eq 的键类型 K,即用来求哈希与判断相等性的标准库特型。
图 16-4 展示了 HashMap 在内存中的排列方式。深灰色区域表示未使用。所有键、值和缓存的哈希码都存储在一个分配在堆上的表中。添加条目最终会迫使 HashMap 分配一个更大的表并将所有数据移入其中。
图 16-4:内存中的 HashMap
BTreeMap 会在树结构中按键的顺序存储条目,因此它需要一个实现了 Ord 的键类型 K。图 16-5 展示了一个 BTreeMap。同样,深灰色区域表示未使用的备用容量。
BTreeMap 中存储条目的单元称为节点。BTreeMap 中的大多数节点仅包含键 - 值对。非叶节点(比如图 16-5 中所示的根节点)中也有一些空间用于存储指向子节点的指针。(20, 'q') 和 (30, 'r') 之间的指针会指向包含 20 和 30 之间所有键的子节点。添加条目通常需要将节点的一些现有条目向右平移,以保持它们的顺序,并且偶尔需要创建新节点。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
Rust语言中的HashMap和BTreeMap是两种不同的Map类型,分别基于哈希表和树结构实现。它们需要实现Hash和Eq的键类型,以及Ord的键类型。文章还介绍了创建Map的几种方法,以及它们的核心方法,如获取长度、判断是否为空、按键获取值、插入、移除等。此外,还介绍了Map的一些特性,如允许对存储的值进行可变访问,但不允许对键进行可变访问,以及使用方括号查询Map时可能出现的panic。同时,还介绍了Map的Entry类型,以及对Map进行迭代的方法。 另外,文章还介绍了HashSet和BTreeSet的特点,以及它们的基本方法和对整个Set进行运算的方法。HashSet和BTreeSet是通过对HashMap和BTreeMap的浅层包装实现的,它们有一些公共的基本方法,如len()、is_empty()、contains()、insert()、remove()等。此外,还介绍了对Set进行迭代的方法,以及Set之间的关系运算方法,如交集、并集、差集、对称差集等。 此外,文章还介绍了哈希的相关内容,包括可哈希类型的标准库特型std::hash::Hash,以及如何实现自定义哈希算法。还介绍了默认的哈希算法SipHash-1-3算法以及如何使用自定义的哈希算法。最后,还提到了在标准集合之外创建自定义集合类型的方法。 总的来说,本文深入介绍了Rust语言中Map和Set的实现原理、特性以及相关的哈希算法知识,对于想深入了解Rust集合类型的读者来说,是一篇值得阅读的文章。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Rust 程序设计(第 2 版)》
《Rust 程序设计(第 2 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论