### 3 releases

0.1.2 | Jan 11, 2019 |
---|---|

0.1.1 | Nov 17, 2018 |

0.1.0 | Nov 16, 2018 |

#**293** in Data structures

**82** downloads per month

**MIT**license

67KB

2K
SLoC

# holyhashmap

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.

## Features

- 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.

## Usage

Add this to your `Cargo .toml`

`[``dependencies``]`
`holyhashmap ``=` `"`0.1`"`

and this to your crate root:

`extern` `crate` holyhashmap`;`

For serde support, add this instead to your

:`Cargo .toml`

`[``dependencies``]`
`holyhashmap = { version = "0.1", features ``=` `[``"`serde`"``]` }

## Example

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`>`,
`}`