10 HashMap和HashSet

1 HashMap

1.1 如何构建HashMap

今天我们来看Rust中的另一个集合容器：HashMap<K,V>。HashMap是编程语言最重要的数据结构之一，在设计时需要考虑以下几点：

1. 避免哈希冲突
2. 防止HashDos攻击
3. HashMap的性能
4. 并发安全问题

了解了HashMap的构建条件，我们再来看看Rust是如何构建HashMap的，先来看看HashMap是怎么封装的

Rust目前使用的哈希算法是SipHash 1-3 ，当key为中等大小时，这种算法很有竞争力，但是当key为较小或者较大时，比如整数和长字符串，其他算法可能更好（但要注意其他算法可能存在HashDos攻击）。并且Rust中HashMap的哈希算法是可插拔的，你可以使用with_hasher替换。这里推荐第三方库fxhash的实现

那Rust是如何避免哈希冲突的呢？使用二次探查和SIMD查找

二次探查是指当多个键映射到相同的哈希桶时（此时发生了哈希冲突）。二次探查通过在哈希表中探查一个固定的步长序列，以寻找下一个可用的哈希桶来解决哈希冲突。也就是在冲突发生时，不断探寻哈希位置加减 n 的二次方，找到空闲的位置插入

SIMD指单指令多数据流，它是一种指令级并行技术，也就是单指令多数据查找。在SIMD查找中，需要查找的元素可以被视为向量，通过并行计算多个向量的比较结果，可以加速查找过程。具体而言，SIMD查找会将要查找的元素和存储在内存中的数据同时加载到向量寄存器中，然后使用向量指令进行比较，得到一个向量表示每个元素是否匹配。最后，使用向量指令进行合并和选择操作，得到匹配元素的位置。SIMD查找具有高效的并行加速优势，适用于大规模数据集的查找任务

1.2 HashMap的使用

HashMap从访问安全来讲可以分为单线程访问和多线程访问，单线程情况下直接使用即可

HashMap默认不支持并发，需要使用多线程所有权共享容器Arc以及RwLock/Mutex包裹才能保证安全。如下仅仅是一个例子，并没有把它扔进其他线程。读者可以使用thread::spawn创建线程，然后在线程中访问或者修改HashMap

2 HashSet

了解完HashMap，HashSet就很简单了，它基于HashMap实现，只不过value为（），也就是只适合存储key的场景。其他使用方法基本和HashMap相同

示例代码Github地址：

https://github.com/shiyivei/from-principle-to-practice/blob/main/src/principle-and-practice/src/type_system/map.rs

更多内容欢迎关注公众号拾一维

#