结构体的简单“查找”类型

Question

我有一个昂贵的结构，有时我想将其用作键：

#[derive(Hash, Eq, PartialEq)]
struct Cat {
    name: String,
    image: Image,
}

如何为这个昂贵的结构定义一个简单的“查找”类型 - 即对关键结构的每个字段类型的引用的结构？

这很有用，这样我就可以拥有

HashMap<Cat, V>

和

find(CatRef) -> &V

。

find(&Cat)

更糟糕，例如即使有免费的

String

可用，也需要实例化

&'static str

。

我可以像这样自己输入它，但我冒着“拥有”类型与“参考”类型不同步的风险：

struct CatRef<'a> {
    name: &'a str,
    image: &'a Image,
}

// Implement Hash, etc. consistently with Cat

Answer 1

如果您将“Key”和“Value”都作为查找映射的

V

，并使用“Key”的哈希值作为查找句柄，会怎样

这样你就可以将它存储在

BTreeMap

中，并且只执行一次散列，这节省了一些对于大型结构可能昂贵的计算。

如果您希望在程序中的其他地方使用大型结构体，您可以简单地使用

Rc<RefCell<_>>

或

Arc<Mutex<_>>

作为

K

 中的 

LookUpTable

示例

#[derive(Hash, Eq, PartialEq, Debug)]
struct Cat {
    pub name: String,
}

use std::collections::BTreeMap;
use std::hash::{DefaultHasher, Hash, Hasher};
use std::marker::PhantomData;
#[derive(Debug)]
pub struct LookUpTable<K: Hash, V> {
    map: BTreeMap<u64, (K, V)>,
    //            ^     ^  ^
    //            |     |  L hold the value
    //            |     L--- hold the key
    //            L--------- hole the handle for looking up
}

impl<K: Hash, V> LookUpTable<K, V> {
    pub fn new() -> Self {
        LookUpTable {
            map: Default::default(),
        }
    }
    pub fn insert(&mut self, key: K, value: V) -> u64 {
        // get the hash value of K(the large struct)
        let handle = {
            let mut s = DefaultHasher::new();
            key.hash(&mut s);
            s.finish()
        };

        // insertion
        self.map.insert(handle, (key, value));

        // return the handle for later use
        handle
    }
    pub fn update(&mut self, handle: u64, new_v: V) {
        self.map.get_mut(&handle).unwrap().1 = new_v;
    }

    pub fn get(&self, handle: u64) -> &(K, V) {
        self.map.get(&handle).unwrap()
    }

    pub fn get_mut(&mut self, handle: u64) -> &mut (K, V) {
        self.map.get_mut(&handle).unwrap()
    }
}

pub fn main() {
    let mut table: LookUpTable<Cat, String> = LookUpTable::new();

    // create a new Cat instance
    let cat_1: Cat = Cat {
        name: "Cat 1".to_string(),
    };

    // --------------------------------------------------
    println!("\n\n{}", "-".repeat(50));
    println!("Empty Table");
    println!("{:#?}", table);

    // --------------------------------------------------
    println!("\n\n{}", "-".repeat(50));
    println!("Insertion");
    // insert the Cat into the table and get a handle back
    let cat_1_handle: u64 = table.insert(cat_1, "This is a value of cat 1.".to_string());
    println!("{:#?}", table);

    // --------------------------------------------------
    println!("\n\n{}", "-".repeat(50));
    println!("get()");
    {
        let (cat_1, value_1): &(Cat, String) = table.get(cat_1_handle);
        println!("cat 1   : {:?}", cat_1);
        println!("value 1 : {:?}", value_1);
    }

    // --------------------------------------------------
    println!("\n\n{}", "-".repeat(50));
    println!("update()");
    table.update(cat_1_handle, "This is a new value of cat 1.".to_string());
    println!("{:#?}", table);

    // --------------------------------------------------
    println!("\n\n{}", "-".repeat(50));
    println!("get_mut()");
    {
        let (cat_1, value_1): &mut (Cat, String) = table.get_mut(cat_1_handle);
        cat_1.name.push_str(": Mister Whisker");
        value_1.push_str(" Appended string at the end.");
    }

    println!("{:#?}", table);
}

输出

--------------------------------------------------
Empty Table
LookUpTable {
    map: {},
}


--------------------------------------------------
Insertion
LookUpTable {
    map: {
        16159386690693546360: (
            Cat {
                name: "Cat 1",
            },
            "This is a value of cat 1.",
        ),
    },
}


--------------------------------------------------
get()
cat 1   : Cat { name: "Cat 1" }
value 1 : "This is a value of cat 1."


--------------------------------------------------
update()
LookUpTable {
    map: {
        16159386690693546360: (
            Cat {
                name: "Cat 1",
            },
            "This is a new value of cat 1.",
        ),
    },
}


--------------------------------------------------
get_mut()
LookUpTable {
    map: {
        16159386690693546360: (
            Cat {
                name: "Cat 1: Mister Whisker",
            },
            "This is a new value of cat 1. Appended string at the end.",
        ),
    },
}

额外

由于句柄只是

u64

，为了避免误用它，你可以将它包裹在另一个结构体中，如下所示：

pub struct LookUpTableHandle<T> {
    _handle: u64,
    _p: PhantomData<T>,
}

impl<K: Hash, V> LookUpTable<K,V> {
    pub fn insert_key_value(&mut self, key: K, value: V) -> LookUpTableHandle<Self> {
        let _handle = {
            let mut s = DefaultHasher::new();
            key.hash(&mut s);
            s.finish()
        };

        self.map.insert(_handle, (key, value));

        LookUpTableHandle { _handle, _p: PhantomData::default() }
    }
    pub fn get_by_handle(&mut self, handle: &LookUpTableHandle<Self>) -> &(K,V) {
        self.map.get(&handle._handle).unwrap()
    }
}

// usage
{
    let cat_2 = Cat{name: "Cat 2".to_string()};
    let handle: LookUpTableHandle<LookUpTable<Cat, String>> = table.insert_key_value(cat_2, "Some String".to_string());
}