正式开端

Rust 的哈希表

  1. 哈希表最核心的特色便是：巨量的或许输入和有限的哈希表容量
  2. 这就会引发哈希抵触，也便是两个或许多个输入的哈希被映射到了同一个方位，所以咱们要能够处理哈希抵触

Rust 哈希表不是用抵触链来解决哈希抵触，而是用敞开寻址法的二次探查来解决的

怎么解决抵触？

首要的抵触解决机制有链地址法（chaining）和敞开寻址法（open addressing）

链地址法

  1. 把落在同一个哈希上的数据用单链表或许双链表连接起来
  2. 在查找的时分，先找到对应的哈希桶（hash bucket），然后再在抵触链上挨个比较，直到找到匹配的项
    17｜数据结构：软件系统核心部件哈希表，内存如何布局？

敞开寻址法

  1. 把整个哈希表看做一个大数组，不引进额外的内存，当抵触产生时，按照一定的规矩把数据刺进到其它闲暇的方位。
  2. 比如线性探寻（linear probing）在出现哈希抵触时，不断往后探寻，直到找到闲暇的方位刺进。
  3. 二次探查，理论上是在抵触产生时，不断探寻哈希方位加减 n 的二次方，找到闲暇的方位刺进

17｜数据结构：软件系统核心部件哈希表，内存如何布局？

HashMap 的数据结构


use hashbrown::hash_map as base;
#[derive(Clone)]
pub struct RandomState {
    k0: u64,
    k1: u64,
}
pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}
  1. HashMap 有三个泛型参数，K 和 V 代表 key / value 的类型，S 是哈希算法的状况，它默许是 RandomState，占两个 u64
  2. RandomState 运用 SipHash 作为缺省的哈希算法，它是一个加密安全的哈希函数（cryptographically secure hashing）
  3. Rust 的 HashMap 复用了 hashbrown 的 HashMap。hashbrown 是 Rust 下对 Google Swiss Table 的一个改进版完成

HashMap 的内存布局


use std::collections::HashMap;
fn main() {
    let map = HashMap::new();
    let mut map = explain("empty", map);
    map.insert('a', 1);
    let mut map = explain("added 1", map);
    map.insert('b', 2);
    map.insert('c', 3);
    let mut map = explain("added 3", map);
    map.insert('d', 4);
    let mut map = explain("added 4", map);
    map.remove(&'a');
    explain("final", map);
}
// HashMap 结构有两个 u64 的 RandomState，然后是四个 usize，
// 分别是 bucket_mask, ctrl, growth_left 和 items
// 咱们 transmute 打印之后，再 transmute 回去
fn explain<K, V>(name: &str, map: HashMap<K, V>) -> HashMap<K, V> {
    let arr: [usize; 6] = unsafe { std::mem::transmute(map) };
    println!(
        "{}: bucket_mask 0x{:x}, ctrl 0x{:x}, growth_left: {}, items: {}",
        name, arr[2], arr[3], arr[4], arr[5]
    );
    unsafe { std::mem::transmute(arr) }
}
/*
empty: bucket_mask 0x0, ctrl 0x562cc5eda400, growth_left: 0, items: 0
added 1: bucket_mask 0x3, ctrl 0x562cc74419f0, growth_left: 2, items: 1
added 3: bucket_mask 0x3, ctrl 0x562cc74419f0, growth_left: 0, items: 3
added 4: bucket_mask 0x7, ctrl 0x562cc7441a50, growth_left: 3, items: 4
final: bucket_mask 0x7, ctrl 0x562cc7441a50, growth_left: 4, items: 3
*/

ctrl 表

ctrl 表的首要意图是快速查找

  1. 一张 ctrl 表里，有若干个 128bit 或许说 16 个字节的分组（group）
  2. group 里的每个字节叫 ctrl byte，对应一个 bucket，那么一个 group 对应 16 个 bucket
  3. 假如一个 bucket 对应的 ctrl byte 首位不为 1，就表明这个 ctrl byte 被运用
  4. 假如一切位都是 1，或许说这个字节是 0xff，那么它是闲暇的。

一组 control byte 的整个 128 bit 的数据，能够经过一条指令被加载进来，然后和某个值进行 mask，找到它地点的方位。这便是一开端说到的 SIMD 查表

HashMap 是怎么经过 ctrl 表来进行数据查询的

假设这张表里现已添加了一些数据，咱们现在要查找 key 为 ‘c’ 的数据

  1. 首要对 ‘c’ 做哈希，得到一个哈希值 h；
  2. 把 h 跟 bucket_mask 做与，得到一个值，图中是 139；
  3. 拿着这个 139，找到对应的 ctrl group 的开端方位，因为 ctrl group 以 16 为一组，所以这里找到 128；
  4. 用 SIMD 指令加载从 128 对应地址开端的 16 个字节；
  5. 对 hash 取头 7 个 bit，然后和刚刚取出的 16 个字节一同做与，找到对应的匹配，假如找到了，它（们）很大概率是要找的值；
  6. 假如不是，那么以二次探查（以 16 的倍数不断累积）的办法往后查找，直到找到为止。

17｜数据结构：软件系统核心部件哈希表，内存如何布局？
当 HashMap 刺进和删去数据，以及因而导致重新分配的时分，首要工作便是在维护这张 ctrl 表和数据的对应

  1. ctrl 表是一切操作最先触及的内存
  2. 在 HashMap 的结构中，堆内存的指针直接指向 ctrl 表，而不是指向堆内存的开端方位 这样能够减少一次内存的拜访
哈希表重新分配与增长
哈希表按幂扩容
  1. 分配新的堆内存后，原来的 ctrl table 和对应的 kv 数据会被移动到新的内存中。
  2. 完成了Copy trait的会复制，不然被移动，移动的话就会触及哈希的重分配
    17｜数据结构：软件系统核心部件哈希表，内存如何布局？
删去一个值
  1. 先要找到要被删去的 key 地点的方位
  2. 在找到具体方位后，并不需要实际清除内存，只需要将它的 ctrl byte 设回 0xff（或许标记成删去状况）

17｜数据结构：软件系统核心部件哈希表，内存如何布局？

当 key/value 有额外的内存时，比如 String，它的内存不会当即回收，只有在下一次对应的 bucket 被运用时，让 HashMap 不再具有这个 String 的一切权之后，这个 String 的内存才被回收

能够经过 shrink_to_fit / shrink_to 释放掉不需要的内存

17｜数据结构：软件系统核心部件哈希表，内存如何布局？

让自界说的数据结构做 Hash key

  1. 要运用到三个 trait：Hash、PartialEq、Eq
  2. 这三个 trait 都能够经过派生宏主动生成
  3. 完成了 Hash ，能够让数据结构计算哈希；
  4. 完成了 PartialEq/Eq，能够让数据结构进行相等和不相等的比较。Eq 完成了比较的自反性（a == a）、对称性（a == b 则 b == a）以及传递性（a == b，b == c，则 a == c），PartialEq 没有完成自反性。

use std::{
    collections::{hash_map::DefaultHasher, HashMap},
    hash::{Hash, Hasher},
};
// 假如要支持 Hash，能够用 #[derive(Hash)]，条件是每个字段都完成了 Hash
// 假如要能作为 HashMap 的 key，还需要 PartialEq 和 Eq
#[derive(Debug, Hash, PartialEq, Eq)]
struct Student<'a> {
    name: &'a str,
    age: u8,
}
impl<'a> Student<'a> {
    pub fn new(name: &'a str, age: u8) -> Self {
        Self { name, age }
    }
}
fn main() {
    let mut hasher = DefaultHasher::new();
    let student = Student::new("Tyr", 18);
    // 完成了 Hash 的数据结构能够直接调用 hash 办法
    student.hash(&mut hasher);
    let mut map = HashMap::new();
    // 完成了 Hash / PartialEq / Eq 的数据结构能够作为 HashMap 的 key
    map.insert(student, vec!["Math", "Writing"]);
    println!("hash: 0x{:x}, map: {:?}", hasher.finish(), map);
}

HashSet / BTreeMap / BTreeSet

HashSet

  1. 用来寄存无序的调集，界说直接是 HashMap<K,()>
  2. 运用 HashSet 检查一个元素是否属于调集的功率非常高

use hashbrown::hash_set as base;
pub struct HashSet<T, S = RandomState> {
    base: base::HashSet<T, S>,
}
pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
    pub(crate) map: HashMap<T, (), S, A>,
}

BTreeMap

BTreeMap 是内部运用 B-tree 来安排哈希表的数据结构，是有序的

BTreeSet

BTreeSet是 BTreeMap 的简化版，能够用来寄存有序调集。

链接

  1. HashMap
  2. 标准调集 HashMap
  3. Swiss Table
  4. hashbrown
  5. Hash
  6. PartialEq
  7. Eq
  8. BTree
  9. collections
  10. Rust调集复杂度
  11. SipHash 概念
  12. aHash
  13. gdb
  14. lldb
  15. rust-gdb
  16. rust-lldb
  17. gdb手册
  18. gdb-lldb对应手册

精选问答

  1. hashmap 在刺进的时分，对key进行hash，这个当地怎么区别hash出来的key要不要进行二次探查呢？

    a. hash 抵触，hash 本来对应的 bucket 被占用，这个时分就需要进行哈希抵触的处理了，需要找出来一个闲暇的 bucket，这个时分用二次探查

    b. 对原来的 key 的更新，查到 hash 对应的 slot 后，还会进一步和 key 做比照。发现key 相同，则做更新操作

  2. 说一下对 hashbrown 的理解。

    a. 一般的哈希表是对数组大小取模（hash % len）来定位方位的，可是 hashbrown 把 hash 分两部分运用：

     1. 低几位（& bucket_size）定位在数组中的方位
 2. 高 7 位存到对应方位的 ctrl 块里，相似指纹的效果

    b. 一般哈希表获取时，取模定位到方位后，要完好比照 key 才能知道是找到（key相同）仍是要探查（key 不同）

    c. hashbrown 能够运用 ctrl 里存起来的高 7 位快速发现抵触的状况（低几位相同但高7 位不同），直接进入下一步探查

  3. 为什么 Rust 的 HashMap 要缺省选用加密安全的哈希算法？

    a. 把 SipHash 作为 HashMap 的缺省的哈希算法，Rust 能够避免开发者在不知情的状况下被 DoS

    b. 假如你确认运用的 HashMap 不需要 DoS 防护（比如一个完全内部运用的 HashMap），那么能够用 Ahash 来替换。你只需要运用 Ahash 提供的 RandomState 即可

  4. 怎么运用 rust-gdb / rust-lldb？

    a. gdb 适合在 Linux 下，lldb 能够在 OS X 下调试 Rust 程序