每日一 R「12」数据结构（三）哈希表

作者：Samson

2022 年 8 月 22 日
上海
本文字数：2685 字
阅读完需：约 9 分钟

在上节课程中，我们学习了 Rust 中的切片，今天我们将一块学习下哈希表。哈希表在任何一门开发语言中都是非常重要的容器数据结构，甚至很多语言都将哈希表作为一种内置的数据结构，例如 Java。

01-Rust 中的哈希表 HashMap

A hash map implemented with quadratic probing and SIMD lookup.译：实现了二次探查和 SIMD 查找的哈希表。

官方文档中对哈希表的描述如上。从中我们可以看到两个关键元素：二次探查和 SIMD 查找。首先，学过数据结构的同学应该了解，哈希表主要用于将大量的可能输入映射（或散列）到有限容量的哈希表中。因为输入远远大于容量，所以就可能存在两个不同的输入，根据散列算法映射到哈希表中的统一位置（哈希碰撞或散列碰撞）。为了解决碰撞，可采用不同的算法，例如链地址法，即将碰撞的元素串联到链表中，Java 中的 HashMap 采用的就是这种方法。例如开放寻址法，即将碰撞的元素存储在当前位置向后线性查找、或非线性查找到的空闲位置。从上面的描述中，我们知道 Rust 中 HashMap 采用的是开放寻址法处理冲突，而且使用得是二次探查（非线性）。所谓二次探查就是指，遇到碰撞时，从当前位置向后查找，每次增加 2 的 n 次方，直到找到空闲位置。至于另外一个关键点 SIMD，在学习完数据结构后，我们再回过头来学习。

01.1-哈希表结构

use hashbrown::hash_map as base;pub struct HashMap<K, V, S = RandomState> {    base: base::HashMap<K, V, S>,}pub struct RandomState {    k0: u64,    k1: u64,}// hashbrown::HashMappub struct HashMap<K, V, S = DefaultHashBuilder, A: Allocator + Clone = Global> {    pub(crate) hash_builder: S,    pub(crate) table: <(K, V), A>,}// hashbrown::raw::RawTablepub struct RawTable<T, A: Allocator + Clone = Global> {    table: RawTableInner<A>,    // Tell dropck that we own instances of T.    marker: PhantomData<T>,}struct RawTableInner<A> {    // Mask to get an index from a hash value. The value is one less than the    // number of buckets in the table.    bucket_mask: usize,
    // [Padding], T1, T2, ..., Tlast, C1, C2, ...    //                                ^ points here    ctrl: NonNull<u8>,
    // Number of elements that can be inserted before we need to grow the table    growth_left: usize,
    // Number of elements in the table, only really used by len()    items: usize,
    alloc: A,}

复制代码

从 HashMap 的源码中可以看到，标准库容器 HashMap 实际上底层实现是 hashbrown::HashMap。泛型 K/V 表示 key/value 键值对类型，S 是哈希算法的状态，默认为 RandomState（SipHash 作为缺省的哈希算法，是一个加密安全的哈希函数），占两个 u64。

HashMap 的底层是个 RawTable<T, A>，其中 T 是 (K, V)，A 是内存分配器。RawTable 中有一个域 marker，它是 PhantomData 类型，不占空间，仅用来高速静态分析器存储的结构是 (K, V) 类型。

RawTable 的关键域是 RawTableInner<A>，它包含了如下几个元素：

bucket_mask，值为桶数量减一
ctrl，指向哈希表末端的指针（后面会详细介绍其设计思想）
growth_left，下次扩容前，还能插入的数量
items，哈希表中元素数量
alloc，为使用的内存分配器

01.2-哈希表的基本用法

let mut map = HashMap::new();// 插入map.insert('a', 1);// 移除map.remove(&'a');// 缩小哈希表占用的内存空间map.shrink_to_fit();

复制代码

01.3-哈希表的内存布局

Rust 哈希表中最重要的或者说最精髓的地方在于 ctrl 表的设计。当使用 HashMap::new() 方法创建哈希表后，在栈内存中会存在下图右上角所示的胖指针。初始时哈希表中没有任何元素，ctrl 指向默认的空表地址。当逐渐向表中插入数据后，会在堆上分配空间，ctrl 指向 ctrl table 位置，哈希表的表头地址可以通过 ctrl 地址减去 bucket_size * (key + value) 得到。

ctrl 表是一个由若干个 128 bit 或 16 字节的 group 组成的。Group 中的每个字节称为 ctrl byte，对应一个 bucket。Ctrl byte 如果是 0xff 则表示为空。

Rust 在加载 ctrl table 时每次加载一个 group，即 16 字节。寻址时通过 hashCode 与 group 中的 ctrl byte 进行 mask 比较来确定位置。这就是前面提到的 Rust 中哈希表的第二个特性：SIMD 查表。SIMD 借助现代 CPU 单指令多数据集的能力，通过一个指令可以将多个相关数据（16 个 ctrl bytes）加载到内存，大大提高了查表的速度。