如何通过部分键从键类型为(i64,usize)的HashMap中取值？

我有一个键类型为(i64, usize)的HashMap，需要仅通过键元组的第一部分检索对应数据。例如要获取所有键第一部分为-1的条目（即示例中归属-1的所有居民数据）。目前做法是遍历整个HashMap并手动检查键的第一部分，代码如下：

use std::collections::HashMap;

fn main(){
    let mut hmap: HashMap<(i64,usize), &str> = HashMap::new();
    hmap.insert((-1,0), "Oth -1 Resident");
    hmap.insert((-1,1), "1st -1 Resident");
    hmap.insert((-1,2), "2nd -1 Resident");
    
    hmap.insert((1,0), "Oth 1 Resident");
    hmap.insert((1,1), "1st 1 Resident");
    hmap.insert((1,2), "2nd 1 Resident");

    for (k,v) in &hmap {
        if k.0 == -1 {
            println!("{:?}",v);
        } 
    }
}

请问是否存在更优实现方式？

方案1：重构为嵌套HashMap #

最直接的优化是调整数据结构，使用HashMap<i64, HashMap<usize, &str>>。这样可以通过第一部分键直接定位到对应子集合，查询时间复杂度从全量遍历的O(n)降到O(1)（定位子Map）+ O(m)（遍历子Map条目，m为该键对应的条目数），效率提升显著。

示例代码：

use std::collections::HashMap;

fn main() {
    let mut hmap: HashMap<i64, HashMap<usize, &str>> = HashMap::new();
    
    // 插入数据
    hmap.entry(-1).or_default().insert(0, "Oth -1 Resident");
    hmap.entry(-1).or_default().insert(1, "1st -1 Resident");
    hmap.entry(-1).or_default().insert(2, "2nd -1 Resident");
    
    hmap.entry(1).or_default().insert(0, "Oth 1 Resident");
    hmap.entry(1).or_default().insert(1, "1st 1 Resident");
    hmap.entry(1).or_default().insert(2, "2nd 1 Resident");
    
    // 检索第一部分为-1的所有条目
    if let Some(residents) = hmap.get(&-1) {
        for (_, v) in residents {
            println!("{:?}", v);
        }
    }
}

方案2：使用BTreeMap做范围查询 #

如果不想改动原有数据结构设计，可以改用BTreeMap。Rust中元组的排序规则是优先比较第一个元素，再比较第二个，因此可以通过范围查询直接筛选出所有第一部分键匹配的条目，避免全量遍历。

示例代码：

use std::collections::BTreeMap;

fn main() {
    let mut bmap: BTreeMap<(i64, usize), &str> = BTreeMap::new();
    bmap.insert((-1,0), "Oth -1 Resident");
    bmap.insert((-1,1), "1st -1 Resident");
    bmap.insert((-1,2), "2nd -1 Resident");
    
    bmap.insert((1,0), "Oth 1 Resident");
    bmap.insert((1,1), "1st 1 Resident");
    bmap.insert((1,2), "2nd 1 Resident");
    
    // 范围查询：所有键的第一部分为-1的条目
    let range = bmap.range((-1, usize::MIN)..=(-1, usize::MAX));
    for (_, v) in range {
        println!("{:?}", v);
    }
}

方案对比 #

• 嵌套HashMap：查询效率最高，适合频繁按第一部分键检索的场景，但插入操作需要多一层处理，数据结构稍复杂。
• BTreeMap：无需修改原有结构设计，范围查询效率优于全量遍历，但整体读写性能略低于HashMap（BTree为有序结构，操作复杂度为O(log n)）。

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