holyhashmap

一个可以索引条目的哈希表。这就像 indexmap，但是索引是稳定的（即，删除条目后索引不会受到影响）。这使得它成为实现图的最佳数据结构。

底层的哈希表实现（线性探测）并不特别快或智能。我目前更感兴趣的是稳定索引属性，而不是拥有一个超级快的哈希表。然而，切换到 Robin Hood 哈希 或 SwissTable 方法 会很棒。稳定索引的想法可以应用于任何哈希表实现。

特性

• Rust 的 HashMap 的直接替代品。
• 插入键值对会返回一个索引，用于回指它。使用索引可以绕过计算键的哈希值的需要。
• 删除键值对会释放使用该索引的索引。未来的插入将重用该索引。因此，删除后索引不是紧凑的。

用法

将此添加到您的 Cargo.toml

[dependencies]
holyhashmap = "0.1"

并将此添加到您的 crate 根目录

extern crate holyhashmap;

对于 serde 支持，请将此替代添加到您的 Cargo.toml

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

示例

以下是使用索引实现图数据结构的一个例子

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

许可证

MIT 许可证