在开发程序时,我们常会使用 HashMap 来保存 key-value 结构的数据。但很多时候我们的 key-value 数据会有不只一层,例如一个男女分班的学校,我们就需要有性别、班级、学号这三层的 key-value 结构,以确保各层的数据不会有重复的情况发生。或是可以分成国家、一级行政区、二级行政区等多层数据的世界地图。

Leveled HashMap

「Leveled HashMap」是笔者开发的套件,提供了 LeveledHashMap 结构体,用来处理阶层式的 key-value 数据,LeveledHashMap 结构体的每一层都是一个 HashMap 结构实体,并非是每个 key-value 条目底下都自带一个 HashMap 结构实体,因此可以确保每层的 key 皆不会相同。如此一来,在搜索时可以直接指定要从哪个层级开始搜索,效率极高。

Crates.io

Cargo.toml

leveled-hash-map = "*"

使用方法

使用 use 关键字将 leveled_hash_map 这个 crate 下的 LeveledHashMap 结构体给引用到当前的程序范围下。LeveledHashMap 结构体的 new 关联函数可以创建出 LeveledHashMap 结构体的实体。

use leveled_hash_map::LeveledHashMap;

let map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

以下介绍 LeveledHashMap 结构实体的增、删、查、改之方式。

添加

LeveledHashMap 结构实体提供了 insert 方法,可以将一个值,添加到一个 Key 链下。例如:

use std::sync::Arc;

use leveled_hash_map::LeveledHashMap;

let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();
map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜点".to_string()).unwrap();

如果该 Key 链已经有存在的值,就会被回传出来。

如果想要在同一层下,添加多个值,可以使用 LeveledHashMap 结构实体提供的 insert_many 方法,直接将一个 HashMap 结构实体添加至 LeveledHashMap 结构实体中的某个 Key 链的子 Key 中。例如:

use std::sync::Arc;
use std::collections::HashMap;

use leveled_hash_map::LeveledHashMap;

let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();

let mut insert_map = HashMap::new();

insert_map.insert("dessert", "甜点".to_string());
insert_map.insert("meat", "肉类".to_string());

map.insert_many(&[Arc::new("food")], insert_map, 0).unwrap();

如果该 Key 链的子 Key 中已经有存在的值,就会被回传出来。

删除

LeveledHashMap 结构实体提供了 remove 方法,可以将一个值从一个 Key 链上移除。例如:

use std::sync::Arc;

use leveled_hash_map::LeveledHashMap;

let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();

map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜点".to_string()).unwrap();

map.insert(&[Arc::new("food"), Arc::new("meat")], "肉类".to_string()).unwrap();

let result = map.remove(&[Arc::new("food"), Arc::new("dessert")]).unwrap();

assert_eq!("甜点", result.0);
assert_eq!(0, result.1.len());

let result = map.remove(&[Arc::new("food")]).unwrap();

assert_eq!("食物", result.0);
assert_eq!(1, result.1.len());
assert_eq!(&(Some(Arc::new("food")), "肉类".to_string()), result.1[0].get(&Arc::new("meat")).unwrap());

如果该 Key 链上确实有值,就会将该值和该 Key 链下所有层级的子 Key 和值回传出来。

也可以使用 LeveledHashMap 结构实体提供的 remove_advanced 方法,来直接从某个层级开始,移除指定的 Key 链。可以省下检查前面几层 Key 链正确性的时间。例如:

use std::sync::Arc;

use leveled_hash_map::LeveledHashMap;

let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();

map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜点".to_string()).unwrap();

map.insert(&[Arc::new("food"), Arc::new("meat")], "肉类".to_string()).unwrap();

let result = map.remove_advanced(&[Arc::new("dessert")], 1).unwrap();

assert_eq!("甜点", result.0);
assert_eq!(0, result.1.len());

let result = map.remove_advanced(&[Arc::new("food")], 0).unwrap();

assert_eq!("食物", result.0);
assert_eq!(1, result.1.len());
assert_eq!(&(Some(Arc::new("food")), "肉类".to_string()), result.1[0].get(&Arc::new("meat")).unwrap());
查找

LeveledHashMap 结构实体提供了 get 方法,可以取得一个 Key 链上之值的不可变参考。例如:

use std::sync::Arc;

use leveled_hash_map::LeveledHashMap;

let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();

map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜点".to_string()).unwrap();

let desert = map.get(&[Arc::new("food"), Arc::new("dessert")]);

也可以使用 LeveledHashMap 结构实体提供的 get_advanced 方法,来直接从某个层级开始,取得指定 Key 链的值的不可变参考。可以省下检查前面几层 Key 链正确性的时间。例如:

use std::sync::Arc;

use leveled_hash_map::LeveledHashMap;

let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();

map.insert(&[Arc::new("food"), Arc::new("dessert")], "甜点".to_string()).unwrap();

let desert = map.get_advanced(&[Arc::new("dessert")], 1);

如果要取得某指定层级的 HashMap 结构实体的(不可变)参考,可以使用 LeveledHashMap 结构实体提供的 keys 方法。例如:

use std::sync::Arc;
use std::collections::HashMap;

use leveled_hash_map::LeveledHashMap;

let mut map: LeveledHashMap<&'static str, String> = LeveledHashMap::new();

map.insert(&[Arc::new("food")], "食物".to_string()).unwrap();

let mut insert_map = HashMap::new();

insert_map.insert("dessert", "甜点".to_string());
insert_map.insert("meat", "肉类".to_string());

map.insert_many(&[Arc::new("food")], insert_map, 0).unwrap();

let result = map.keys(0).unwrap();

assert_eq!(1, result.len());

let result = map.keys(1).unwrap();

assert_eq!(2, result.len());
修改

LeveledHashMap 结构实体提供的各类 get 方法,方法名称后面皆可以加上 _mut,来取得值的可变参考,如此就可以直接改变 LeveledHashMap 结构实体内的值。

使用案例

以下简单创建一个拥有多国语言名称的抽象「世界地图」:

use std::sync::Arc;
use std::collections::HashMap;

use leveled_hash_map::LeveledHashMap;

#[derive(Debug)]
struct MultiName {
    us: &'static str,
    tw: &'static str,
    cn: &'static str,
}

fn main() {
    let earth_map: LeveledHashMap<&'static str, MultiName> = {
        let mut map = LeveledHashMap::new();

        map.insert(&[Arc::new("US")], MultiName {
            us: "United States of America",
            tw: "美国",
            cn: "美国",
        }).unwrap();

        let mut us_states = HashMap::new();

        us_states.insert("New York", MultiName {
            us: "New York",
            tw: "纽约州",
            cn: "纽约州",
        });
        us_states.insert("Utah", MultiName {
            us: "Utah",
            tw: "犹他州",
            cn: "犹他州",
        });

        map.insert_many(&[Arc::new("US")], us_states, 0).unwrap();

        map.insert(&[Arc::new("CN")], MultiName {
            us: "China",
            tw: "中国",
            cn: "中国",
        }).unwrap();

        let mut cn_provinces = HashMap::new();

        cn_provinces.insert("Guangdong", MultiName {
            us: "Guangdong",
            tw: "广东省",
            cn: "广东省",
        });
        cn_provinces.insert("Fujian", MultiName {
            us: "Fujian",
            tw: "福建省",
            cn: "福建省",
        });

        map.insert_many(&[Arc::new("CN")], cn_provinces, 0).unwrap();

        map.insert(&[Arc::new("TW")], MultiName {
            us: "Taiwan",
            tw: "台湾",
            cn: "台湾",
        }).unwrap();

        let mut tw_counties = HashMap::new();

        tw_counties.insert("Taipei", MultiName {
            us: "Taipei",
            tw: "台北",
            cn: "台北",
        });

        tw_counties.insert("Taichung", MultiName {
            us: "Taichung",
            tw: "台中",
            cn: "台中",
        });

        map.insert_many(&[Arc::new("TW")], tw_counties, 0).unwrap();

        map
    };

    println!("{:?}", earth_map);

    let countries = earth_map.keys(0).unwrap();

    println!("{:?}", countries); // {"CN": {"Fujian", "Guangdong"}, "US": {"Utah", "New York"}, "TW": {"Taichung", "Taipei"}}

    let new_york = earth_map.get(&[Arc::new("US"), Arc::new("New York")]).unwrap();

    println!("{:?}", new_york); // MultiName { us: "New York", tw: "纽约州", cn: "纽约州" }

    let new_york = earth_map.get_advanced(&[Arc::new("New York")], 1).unwrap();

    println!("{:?}", new_york); // MultiName { us: "New York", tw: "纽约州", cn: "纽约州" }

    let new_york_suspicion = earth_map.get(&[Arc::new("TW"), Arc::new("New York")]);

    println!("{:?}", new_york_suspicion); // None
}