A hash map whose entries can be indexed into. This is just like indexmap, but the indices are stable (i.e., indices are not perturbed upon removal of an entry). This makes it an ideal data structure for implementing graphs.
The underlying hash map implementation (linear probing) is not particularly fast or smart. I'm more interested in the stable indices property than having a super-fast hash map at the moment. However, it'd be great to switch to either Robin Hood Hashing or to the SwissTable approach. The idea of stable indices can be applied to any hash map implementation.
- A drop-in replacement of Rust's
HashMap. - Inserting a key-value pair gives back an index to refer back to it. Using the index bypasses the need to compute the hash of the key.
- Removing a key-value pair frees up the index that was using it. A future insertion will reuse the index. Thus, indices are not compact after a removal.
Add this to your Cargo.toml
[dependencies]
holyhashmap = "0.1"For serde support, add this instead to your Cargo.toml:
[dependencies]
holyhashmap = { version = "0.1", features = ["serde"] }Here's how one might implement a graph data structure utilizing indices:
extern crate holyhashmap;
use holyhashmap::{HolyHashMap, EntryIndex};
type NodeIndex = EntryIndex;
struct Neighbors {
incoming: Vec<NodeIndex>,
outgoing: Vec<NodeIndex>,
}
pub struct Graph<N, E>
where
N: Eq + Hash,
{
// The nodes in the graph. A mapping of the node key `N` to its neighbors.
nodes: HolyHashMap<N, Neighbors>,
// The edges in the graph. A mapping between node index pairs and the edge
// weight `E`.
edges: HolyHashMap<(NodeIndex, NodeIndex), E>,
}This was developed at Environmental Systems Research Institute (Esri) who have graciously allowed me to retain the copyright and publish it as open source software.