Lib.rs

› 数据结构
#hash-table #array #hash #table #array-vec

ahtable

数组哈希表实现

作者 Nattapong Sirilappanich

7个版本

0.2.0 2020年8月22日
0.1.5 2020年8月19日
0.1.2 2020年6月14日

2183 in 数据结构

每月27次下载
用于 hat_trie

BSD-3-Clause

55KB
822 行

ahtable

这是一种数组哈希数据结构，数组在初始化时分配了特定的大小，每个元素根据哈希函数分配到每个索引。数组中的每个元素都是一个Vec。每个哈希冲突都会被推入Vec。当添加的元素数量达到一定大小时，它将通过将数组大小加倍并从旧数组移动所有旧条目到新数组来扩展数组大小。所有这些都在幕后发生。用户不会受到此类操作的影响。

如何使用

  1. 使用 ArrayHashBuilder::default()
  2. 使用构建器配置数组哈希所需的所有规格
  3. 在实例上使用 build() 方法以获取 ArrayHash
  4. 使用以下方法操作数组
    1. put() 将新数据放入数组。此方法始终放置或替换现有值。
    2. try_put() 如果它尚未存在，则将新数据放入数组。
    3. get() 通过哈希且可比较的键检索放入其中的值。
    4. smart_get() 当 key 为智能指针类型时检索值。这有助于减少构建与键本身相同类型的智能指针所需的时间处理器。
    5. coerce_get() 当 key 为可以借用为不是实现 PartialEq<K> 的另一个类型的类型时检索值。
    6. remove() 通过哈希且可比较的键从该数组中删除值。
    7. smart_remove() 用于在 key 是智能指针类型时检索值。这将有助于减少构造与键本身相同类型的智能指针所需的时间处理器。
    8. coerce_remove() 用于在 key 是可以借用为不实现 PartialEq<K> 的原始类型的类型时删除值。
    9. contains_iter 用于测试当前数组是否包含迭代器产生的每个条目。
    10. to_builder 用于从现有数组中获得具有当前规范的 ArrayHashBuilder。
    11. iter() 用于遍历数组条目。
    12. iter_mut() 用于遍历和修改数组条目。这个迭代器不应该用来修改条目键。
    13. drain() 用于获取一个迭代器，该迭代器会从该数组中持续清除所有数据。
    14. drain_with() 用于获取一个迭代器，当谓词返回 true 时，从中清除一些特定条目。
    15. split_by() 返回另一个数组，并将满足谓词的所有值移动到新数组中。
    16. is_hasher_eq() 用于检查两个数组是否有等价的哈希器。

从 0.1 到 0.2 的破坏性更改

  • ArrayHash::try_put 现在返回 Result。当它无法插入时，返回包含给定键/值以及与给定键关联的当前值的 Err。当它成功时，返回包含已放入数组的值的 Ok。

从 0.1 迁移到 0.2 的指南

  1. 对于任何 if let Some(v) = array_hash.try_put(key, value)，它将变为 if let Err((key, value, cur_val) = array_hash.try_put(key, value)
  2. 对于任何 if array_hash.try_put(key, value).is_some()，它将变为 if array_hash.try_put(key, value).is_err()
  3. 对于任何 if array_hash.try_put(key, value).is_none()，它会变成 if array_hash.try_put(key, value).is_ok()
  4. 对于任何语句 array_hash.try_put(key, value);，它会变成 array_hash.try_put(key, value).unwrap()
  5. 对于任何 let cur_v = array_hash.try_put(key, value).unwrap()，它会变成 let (_, _, cur_v) = array_hash.try_put(key, value).unwrap_err()

重要提示

  1. PartialEq 的 ArrayHash 需要比较者和比较对象完全相同。这包括 Hasher，它必须使用相同的数字进行初始化。理想的使用方法是首先填充最大的数组，然后使用 ArrayHash::to_builder 来构建第二个数组。如果不可能，可以考虑构建一个足够大的 ArrayHash 以存储所有内容，而不达到 max_load_factor，然后使用 ArrayHash::to_builder 或克隆该 ArrayHashBuilder 来构建每个数组。
  2. 存在一个方法 ArrayHash::is_hasher_eq 来测试两个数组是否可以比较。如果两个数组使用不同类型的哈希器，它将立即产生编译错误。如果它使用相同的哈希器类型，但使用不同的种子，它将返回 false。否则，它可以通过 == 运算符进行比较。
  3. 直接在两个数组上使用 == 运算符是安全的。它将产生类似于 ArrayHash::is_hasher_eq 的编译错误。实际上，在 PartialEq 实现中，它使用 ArrayHash::is_hasher_eq 首先检查它是否可以比较。然而，如果两个数组使用不同的种子，即使两个数组中都有完全相同的元素，它也会始终返回 false。
  4. 使用 == 运算符比较两个数组比使用 ArrayHash::contains_iter 要快得多，因为 contains_iter 需要为迭代返回的每个键进行哈希。该方法在两个数组使用不同类型的哈希器或由不同的 ArrayHashBuilder 构建时适用。

新功能

0.2.0

  • ArrayHash::try_put 将指定的 key 和 value 放入，但并不保证一定放入。现在它返回 Result。如果 key 和 value 成功放入，则返回 Ok((&V))，其中 &V 是放入的值的引用。如果放入失败，则返回 Err((K, V))，其中 K 是给定的 key，而 V 是给定的值。

0.1.5

  • 修复哈希缺陷。当在 ArrayHash 自身上哈希时，即使两个数组相等，也可能会导致两个哈希不同。这是因为 PartialEq 不比较 max_load_factor，而是在 0.1.4 哈希时使用 max_load_factor 来计算哈希。

0.1.4

  • ArrayHash 和 ArrayHashBuilder 现在实现了 Hash 和 PartialEq
  • ArrayHash::is_hasher_eq 用于检查两个数组是否使用完全相同的哈希器。
  • ArrayHash::coerce_get 和 ArrayHash::coerce_remove 可以接受一个未实现 PartialEq 的借用类型，并使用存储的条目。
  • ArrayHash::smart_remove 与 ArrayHash::smart_get 是对应的，当存储和查询可以下引用到同一类型时可以使用。
  • 为 ArrayHashBuilder 实现 core::convert::From::ArrayHash。
  • ArrayHash::to_builder 可以获取一个可以构建具有与当前 ArrayHash 相同规范的 ArrayHashBuilder。
  • ArrayHash::contains_iter 检查这个数组是否包含给定迭代器产生的每个条目。

0.1.3

  • ArrayHash::get 和 ArrayHash::remove 参数现在是泛型的，而不是固定为与键相同的类型。现在任何实现了 PartialEq + Hash 的类型都可以作为参数使用。
  • ArrayHash 的键和值不再需要实现克隆。原因在于需要克隆键和值的地方有两个，这两个地方都是为了分配 Vec。然而，在这两个地方，都不需要对键和值进行实际的克隆。它们分配了一个空的 Vec。因此，克隆空 Vec 对性能的影响与循环构造空 Vec 没有区别。因此，对库用户来说，可以减少对键/值的约束。

依赖关系

~145KB