FcHashMap

固定容量的no_std hashmap。

Hashmap是一种实现关联数组的抽象数据类型，可以将键映射到值。插入、删除和搜索条目速度快。这个容量有限的hashmap适用于小型系统，不需要动态堆分配器，可以在栈上使用。这个实现的基础是所谓的罗宾汉哈希，最初由Pedro Celis开发。在Emmanuel Goossaert的以下两篇论文中（1，2）对该功能进行了很好的解释。

备注

HashMap的实现基于罗宾汉哈希算法。这种方法
简单、稳健，性能合理。然而，固定容量的实现有一些限制

• HashMap的大小必须在编译时固定
• 每个条目（不含键和值）消耗8字节RAM
• 最大容量限制为32768个条目
• 容量必须选择为2的幂
• 不应将HashMap使用到其全部容量，否则它会变得很慢。应始终保持10到20%的容量空闲。

示例

use fchashmap::FcHashMap;
use hash32_derive::Hash32;
use hash32::Hash;

#[derive(Debug)]
struct Reading {
    temperature: f32,
    humidy: f32,
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash32)]
struct DeviceId([u8; 8]);

impl DeviceId {
    fn new(input: &[u8; 8]) -> Self {
        let mut id = [0_u8; 8];
        id.copy_from_slice(input);
        Self(id)
    }
}

let mut fc_hash_map = FcHashMap::<DeviceId, Reading, 128>::new();

let dev1 = DeviceId::new(b"12345678");
let dev2 = DeviceId::new(b"12345679");
let dev3 = DeviceId::new(b"12345680");

fc_hash_map.insert(dev1, Reading { temperature: 23.1, humidy: 76.3 }).unwrap();
fc_hash_map.insert(dev2, Reading { temperature: 22.7, humidy: 55.5 }).unwrap();

let reading = fc_hash_map.get(&dev1).unwrap();
assert_eq!(reading.temperature, 23.1);
assert_eq!(reading.humidy, 76.3);

let reading = fc_hash_map.get(&dev2).unwrap();
assert_eq!(reading.temperature, 22.7);
assert_eq!(reading.humidy, 55.5);

assert!(fc_hash_map.get(&dev3).is_none());

性能

以下图表显示了在72 MHz的Cortex M4f系统（STM32F3）上的时间行为。可以看到，当填充率约为80%时，hashmap的性能显著下降。

其他说明

在我使用的一个项目中，由于Heapless::Vec缺少功能，我使用了crate ArrayVec。由于我还需要HashMap，我不得不发现没有合适的独立HashMap，它不进行内存分配并且与no_std兼容。由于我无论如何都在学习Rust，所以我决定编写自己的HashMap。

为了实现哈希表，我从上述论文开始着手。在实现过程中，我从Japarics Heapless::FnvIndexMap获得了许多灵感。我发现这个HashMap也使用了Robin Hood哈希，最终我得到了几乎相同的解决方案。无论如何，FcHashMap不幸地比它大近200字节，但仍然比FnvIndexMap快约10%。哪种实现更容易理解和维护，请让每个人自己决定。非常感谢FnvHashMap的作者提供了许多有用的灵感。

许可证

根据您选择的Apache License，Version 2.0或MIT许可证。