正式开端
Rust 的哈希表
- 哈希表最核心的特色便是：巨量的或许输入和有限的哈希表容量
- 这就会引发哈希抵触，也便是两个或许多个输入的哈希被映射到了同一个方位，所以咱们要能够处理哈希抵触
Rust 哈希表不是用抵触链来解决哈希抵触，而是用敞开寻址法的二次探查来解决的
怎么解决抵触？
首要的抵触解决机制有链地址法（chaining）和敞开寻址法（open addressing）
链地址法
- 把落在同一个哈希上的数据用单链表或许双链表连接起来
- 在查找的时分，先找到对应的哈希桶（hash bucket），然后再在抵触链上挨个比较，直到找到匹配的项
敞开寻址法
- 把整个哈希表看做一个大数组，不引进额外的内存，当抵触产生时，按照一定的规矩把数据刺进到其它闲暇的方位。
- 比如线性探寻（linear probing）在出现哈希抵触时，不断往后探寻，直到找到闲暇的方位刺进。
- 二次探查，理论上是在抵触产生时，不断探寻哈希方位加减 n 的二次方，找到闲暇的方位刺进
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>,
}
- HashMap 有三个泛型参数，K 和 V 代表 key / value 的类型，S 是哈希算法的状况，它默许是 RandomState，占两个 u64
- RandomState 运用 SipHash 作为缺省的哈希算法，它是一个加密安全的哈希函数（cryptographically secure hashing）
- 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 表的首要意图是快速查找
- 一张 ctrl 表里，有若干个 128bit 或许说 16 个字节的分组（group）
- group 里的每个字节叫 ctrl byte，对应一个 bucket，那么一个 group 对应 16 个 bucket
- 假如一个 bucket 对应的 ctrl byte 首位不为 1，就表明这个 ctrl byte 被运用
- 假如一切位都是 1，或许说这个字节是 0xff，那么它是闲暇的。
一组 control byte 的整个 128 bit 的数据，能够经过一条指令被加载进来，然后和某个值进行 mask，找到它地点的方位。这便是一开端说到的 SIMD 查表
HashMap 是怎么经过 ctrl 表来进行数据查询的
假设这张表里现已添加了一些数据，咱们现在要查找 key 为 ‘c’ 的数据
- 首要对 ‘c’ 做哈希，得到一个哈希值 h；
- 把 h 跟 bucket_mask 做与，得到一个值，图中是 139；
- 拿着这个 139，找到对应的 ctrl group 的开端方位，因为 ctrl group 以 16 为一组，所以这里找到 128；
- 用 SIMD 指令加载从 128 对应地址开端的 16 个字节；
- 对 hash 取头 7 个 bit，然后和刚刚取出的 16 个字节一同做与，找到对应的匹配，假如找到了，它（们）很大概率是要找的值；
- 假如不是，那么以二次探查（以 16 的倍数不断累积）的办法往后查找，直到找到为止。
- ctrl 表是一切操作最先触及的内存
- 在 HashMap 的结构中，堆内存的指针直接指向 ctrl 表，而不是指向堆内存的开端方位 这样能够减少一次内存的拜访
哈希表重新分配与增长
哈希表按幂扩容
- 分配新的堆内存后，原来的 ctrl table 和对应的 kv 数据会被移动到新的内存中。
- 完成了Copy trait的会复制，不然被移动，移动的话就会触及哈希的重分配
删去一个值
- 先要找到要被删去的 key 地点的方位
- 在找到具体方位后，并不需要实际清除内存，只需要将它的 ctrl byte 设回 0xff（或许标记成删去状况）
当 key/value 有额外的内存时，比如 String，它的内存不会当即回收，只有在下一次对应的 bucket 被运用时，让 HashMap 不再具有这个 String 的一切权之后，这个 String 的内存才被回收
能够经过 shrink_to_fit / shrink_to 释放掉不需要的内存
让自界说的数据结构做 Hash key
- 要运用到三个 trait：Hash、PartialEq、Eq
- 这三个 trait 都能够经过派生宏主动生成
- 完成了 Hash ，能够让数据结构计算哈希；
- 完成了 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
- 用来寄存无序的调集，界说直接是 HashMap<K,()>
- 运用 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 的简化版，能够用来寄存有序调集。
链接
- HashMap
- 标准调集 HashMap
- Swiss Table
- hashbrown
- Hash
- PartialEq
- Eq
- BTree
- collections
- Rust调集复杂度
- SipHash 概念
- aHash
- gdb
- lldb
- rust-gdb
- rust-lldb
- gdb手册
- gdb-lldb对应手册
精选问答
-
hashmap 在刺进的时分，对key进行hash，这个当地怎么区别hash出来的key要不要进行二次探查呢？
a. hash 抵触，hash 本来对应的 bucket 被占用，这个时分就需要进行哈希抵触的处理了，需要找出来一个闲暇的 bucket，这个时分用二次探查
b. 对原来的 key 的更新，查到 hash 对应的 slot 后，还会进一步和 key 做比照。发现key 相同，则做更新操作
-
说一下对 hashbrown 的理解。
a. 一般的哈希表是对数组大小取模（hash % len）来定位方位的，可是 hashbrown 把 hash 分两部分运用：
1. 低几位（& bucket_size）定位在数组中的方位 2. 高 7 位存到对应方位的 ctrl 块里，相似指纹的效果b. 一般哈希表获取时，取模定位到方位后，要完好比照 key 才能知道是找到（key相同）仍是要探查（key 不同）
c. hashbrown 能够运用 ctrl 里存起来的高 7 位快速发现抵触的状况（低几位相同但高7 位不同），直接进入下一步探查
-
为什么 Rust 的 HashMap 要缺省选用加密安全的哈希算法？
a. 把 SipHash 作为 HashMap 的缺省的哈希算法，Rust 能够避免开发者在不知情的状况下被 DoS
b. 假如你确认运用的 HashMap 不需要 DoS 防护（比如一个完全内部运用的 HashMap），那么能够用 Ahash 来替换。你只需要运用 Ahash 提供的 RandomState 即可
-
怎么运用 rust-gdb / rust-lldb？
a. gdb 适合在 Linux 下，lldb 能够在 OS X 下调试 Rust 程序
