#map #hash #cache #data-structure

trashmap

A HashMap and HashSet that operate directly on hashes instead of keys, avoiding rehashing

4 releases

0.1.3 May 20, 2019
0.1.2 Apr 10, 2019
0.1.1 Apr 10, 2019
0.1.0 Apr 10, 2019

#77 in #data-structure

21 downloads per month

MIT/Apache

13KB
227 lines

trashmap

Build Status Current Version License: MIT/Apache-2.0

This crate provides TrashMap and TrashSet types, which allow you to directly use the key hash to operate with your entries. This is typically useful for when it's cheap to hold on to the hash value (e.g. within a single stack frame) and you don't want to incur the cost of rehashing on each access (but you can't use Entry as the map may change in the process)

The Trash type is used to represent computed hashes, lookups via Trash are cheap.


lib.rs:

This crate provides TrashMap and TrashSet types, which allow you to directly use the key hash to operate with your entries. This is typically useful for when it's cheap to hold on to the hash value (e.g. within a single stack frame) and you don't want to incur the cost of rehashing on each access (but you can't use Entry as the map may change in the process)

The Trash type is used to represent computed hashes, lookups via Trash are cheap.

An example of using this would be to check for cycles when doing some kind of graph traversal:

use trashmap::TrashSet;
# fn lookup_children(entry: &str) -> &'static [&'static str] { &[] }
struct State {
   seen: TrashSet<str>,
}

impl State {
    fn step_into(&mut self, entry: &str) {
        let (id, empty) = self.seen.insert_check(entry);
        if !empty {
            panic!("found recursive loop!");
        }
        let children = lookup_children(entry);
        for child in children {
           self.step_into(child);
        }
        self.seen.remove(id);
    }
}

No runtime deps