基于密钥外部数据的自定义哈希

Question

我有一张只读地图：

struct Map {
    inner: HashMap<Key, Value>,
}

我正在尝试将其转换为以下布局：

struct Map {
    keys: Vec<Key>,
    inner: HashMap<usize /* index in [keys] */, Value>,
}

（我这样做是为了优化内存消耗 - 在实际代码中

Key

在堆中存储一些数据，并且

keys

将是自定义的

Vec

，它会进行一个大堆分配并“内联”存储键）

是否可以为这样的布局编写

get

方法？

impl Map {
    pub fn get(&self, key: &Key) -> Option<&Value> {
        
    }
}

Answer 1

是否可以按照您的要求编写这样的方法？是的。例如：

use std::collections::HashMap;

struct Map<K, V> {
    keys: Vec<K>,
    inner: HashMap<usize /* index in [keys] */, V>,
}

impl<K, V> Map<K, V> {
    pub fn get(&self, key: &K) -> Option<&V>
    where
        K: std::cmp::Eq
    {
       let index = self.keys.iter().position(|k| k == key);
       index.map(|i| self.inner.get(&i).unwrap())
    }
}

但是你应该使用它吗？可能不是。

我不太明白你想要做什么，但是将键放在

Vec

中并将值存储在以 vec 的索引作为键的映射中是真的很奇怪，并且总是比使用单一 vec 效率更低且更不符合人体工程学，或单张地图。

请注意，在

get

中，您必须执行以下操作：

1. 线性搜索

   Vec

中的键
2. 计算给定索引的哈希值
3. 保持不变，

   0..keys.len()

   中的每个键都是

   HashMap

中的有效键

（通常）这比仅仅将

(K, V)

对存储在

Vec

中并对键进行线性搜索，或者对键进行哈希处理并在

HashMap

中进行查找（就像在第一个示例中一样）要更多的工作。

此外，这会导致更大的碎片（键和值可能位于内存中的不同页面上（因为它们是单独分配的），并且实际上您只能轻松地从

Vec

的末尾删除键，因为从中间删除键会导致索引发生变化，并且需要重新计算哈希图。

结论是，这是可能的，但你可能不应该这样做。如果您想执行线性搜索，请继续使用

HashMap<K, V>

或使用

Vec<(K, V)>

。如果您想进一步优化，请先进行测量，并确保您知道自己想要做什么。