基于键外部数据的自定义哈希：改造后只读Map的get方法能否实现？

要实现这个新布局下的get方法，核心问题是快速将输入的Key映射到keys向量中的索引，再通过索引从inner哈希表中获取对应Value。以下是具体实现思路和代码：

核心思路 #

新结构中inner的键是keys的索引，但直接通过输入Key查找索引的话，线性遍历keys的时间复杂度是O(n)，完全失去了哈希表的性能优势。因此必须额外维护一个反向映射表，用于快速将Key映射到对应的索引，保证get方法的时间复杂度仍为O(1)。

代码实现 #

1. 调整Map结构（添加反向映射） #

use std::collections::HashMap;
use std::hash::Hash;

struct Map<Key: Eq + Hash, Value> {
    // 存储所有Key的自定义Vec（一次大堆分配优化内存）
    keys: Vec<Key>,
    // 反向映射：Key -> 其在keys中的索引
    key_to_index: HashMap<Key, usize>,
    // 索引 -> Value的哈希表
    inner: HashMap<usize, Value>,
}

2. 实现get方法 #

impl<Key: Eq + Hash, Value> Map<Key, Value> {
    pub fn get(&self, key: &Key) -> Option<&Value> {
        // 先通过反向映射找到索引，再用索引查inner表
        self.key_to_index.get(key)
            .and_then(|&index| self.inner.get(&index))
    }
}

3. 优化内存的替代方案（避免Key副本） #

如果Key的克隆成本较高，不想在反向映射表中存储Key的副本，可以使用带生命周期的引用实现，前提是Map构建完成后保持只读：

use std::collections::HashMap;
use std::hash::Hash;

struct Map<'a, Key: Eq + Hash + 'a, Value> {
    keys: Vec<Key>,
    key_to_index: HashMap<&'a Key, usize>,
    inner: HashMap<usize, Value>,
}

impl<'a, Key: Eq + Hash + 'a, Value> Map<'a, Key, Value> {
    // 构建Map的示例方法，确保引用生命周期安全
    pub fn new(mut entries: impl IntoIterator<Item = (Key, Value)>) -> Self {
        let mut keys = Vec::new();
        let mut key_to_index = HashMap::new();
        let mut inner = HashMap::new();

        for (key, value) in entries {
            let index = keys.len();
            // 插入即将存入keys的Key的引用
            key_to_index.insert(&key, index);
            keys.push(key);
            inner.insert(index, value);
        }

        Map {
            keys,
            key_to_index,
            inner,
        }
    }

    pub fn get(&self, key: &Key) -> Option<&Value> {
        self.key_to_index.get(key)
            .and_then(|&index| self.inner.get(&index))
    }
}

不推荐的低效率实现 #

如果不维护反向映射，只能通过线性遍历keys查找索引，仅适合极小数据量场景：

// 仅作示例，不推荐用于大数据量
pub fn get(&self, key: &Key) -> Option<&Value> {
    self.keys.iter()
        .position(|k| k == key)
        .and_then(|index| self.inner.get(&index))
}

内容的提问来源于stack exchange，提问作者diralik