Implementing Python-style dict with hashbrown. Ownership problem

Hi everyone!

I am trying to implement a Python-style dict in Rust. More information about the idea can be found here:

I thought of using hashbrown's RawTable to store indices into a Vec of (Key, Value) tuples. While writing the insert function I ran into an ownership problem that I need help with. The code looks like this:

pub struct OrderedHashMap<K, V, S = DefaultHashBuilder> {
    hash_builder: S,
    table: RawTable<usize>,
    entries: Vec<(K, V)>,

pub fn insert(&mut self, k: K, v: V) -> Option<V> {
    unsafe {
        let hash = make_hash(&self.hash_builder, &k);
        if let Some(item) = self.table.find(hash, |x| k.eq(&self.entries[*x].0)) {
            Some(std::mem::replace(&mut self.entries[].1, v))
        } else {
            // Insert (k,v) into dense entries vec.
            self.entries.push((k, v));
            let index = self.entries.len() - 1;

            // Insert index into hash map.
            let hash_builder = &self.hash_builder;
            let hasher = |x: &usize| make_hash(hash_builder, &self.entries[*x].0);
            self.table.insert(hash, index, hasher);

This does not compile with the following error message:

let hasher = |x: &usize| make_hash(hash_builder, &self.entries[*x].0);
             -----------                          ---- first borrow occurs due to use of `self` in closure
             immutable borrow occurs here
self.table.insert(hash, index, hasher);
|          |
|          immutable borrow later used by call
mutable borrow occurs here

The table needs to be able to index into entries in order to rehash all the keys when it sees fit. How can I work around the Rust ownership system to accomplish that?

That closure borrows all of self, because the desugaring of closures isn't smart enough yet to realize that only one field is used. Do

let entries = &self.entries;
let hasher = |x: &usize| make_hash(hash_builder, &entries[*x].0);

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.