OrdMap & HashMap

• AVL不比RBTree差，也是解决哈希冲突攻击的一种可行方式。
• 此包公开了两个公共结构：由优化的AVL实现的 OrdMap，每个索引包含AVL-Tree的 HashMap。
• 为了提高性能，经常使用原始指针。因为Rust使用与C/C++类似的内存模型，使用了两个经典宏 offset_of 和 container_of 来将成员变量解引用到主结构中。实现了 Fastbin 以减少内存分配的成本。
• insert 和 remove 操作通过选择性跳过 AVL Rebalance 来优化，因为低于95%的索引中，节点数少于3个。
• 由于 SipHash 性能不佳，使用 FnvBuildHasher 作为默认的 BuildHasher。
• HashMap的整体结构如下

 HashMap:
         ------------------------------------------
         |   HashIndex   |   HashIndex   |   ...
         ------------------------------------------
                                                 ----------------
 HashIndex:                                      |    ......    |
         ----------------    ----------------    |   AVL Node   |
         |   ........   |    |   AVL Root   |==> ----------------
 ... <==>|   ListHead   |<==>|   ListHead   |<==> ... <==> HEAD <==> ...
         ----------------    ----------------

 InternalHashEntry
             ----------------
             |   HashNode   |
             |     Value    |
             ----------------

 HashNode
          ----------------    -----------------
          |    ......    |    |   HashValue   |
          |    ......    |    |      Key      |
  ... <==>|   AVL Node   |<==>|    AVL Node   |<==> ...
          ----------------    -----------------

使用方法

注意特质。大多数函数的使用方法与STL HashMap相同，您可以在测试用例或文档中找到示例。

impl<K, V, S> HashMap<K, V, S> where K: Ord + Hash, S: BuildHasher
impl<K, V> OrdMap<K, V> where K: Ord

性能测试

AVL与RBTree比较

cargo run --release --example avl_cmp_rbtree

• 显然，优化的AVL不比RBTree差，并且具有更小的树高和 Fastbin 的优势，因此性能更好。

avl tree
size 1000000
build time PT0.086414625S 
contain count 1000000
find time PT0.079008516S 
remove time PT0.047414057S 
insert after remove time PT0.068621561S 
clear time PT0.020838042S 

rbtree
size 1000000
build time PT0.255747347S 
contain count 1000000
find time PT0.128373407S 
remove time PT0.129552620S 
insert after remove time PT0.256210620S 
clear time PT0.051735117S 
--------------------------------------------

avl tree
size 10000000
build time PT0.996452066S 
contain count 10000000
find time PT0.862577411S 
remove time PT0.641826155S 
insert after remove time PT0.779849807S 
clear time PT0.206050905S 

rbtree
size 10000000
build time PT3.348531156S 
contain count 10000000
find time PT1.482958388S 
remove time PT1.538498453S 
insert after remove time PT3.361221077S 
clear time PT0.505872813S 
--------------------------------------------

HashMap竞争

• 由于 String 操作本身需要太多时间，我们只展示了与键 usize 的竞争。

运行命令

cargo run --release --example hash_map_cmp_usize

我们的实现性能更好，尤其是在 searching 的情况下。

test hash avl map
insert time PT0.111996300S
max node num of single index: 1
find 1000000, time PT0.042600200S
remove time PT0.108599100S

test stl hash map
insert time PT0.141726400S
find 1000000, time PT0.117749600S
remove time PT0.139572800S
--------------------------------

test hash avl map
insert time PT0.661286300S
max node num of single index: 2
find 5000000, time PT0.251113S
remove time PT0.638360800S

test stl hash map
insert time PT0.746569600S
find 5000000, time PT0.647037200S
remove time PT0.828150S
--------------------------------

test hash avl map
insert time PT1.385713200S
max node num of single index: 2
find 10000000, time PT0.521490300S
remove time PT1.368300300S

test stl hash map
insert time PT1.632164300S
find 10000000, time PT1.426744300S
remove time PT1.703507200S
--------------------------------

• 面对冲突攻击时，STL HashMap的运行时间复杂度可以是 O(n^2)，但我们的为 O(n log n)。

cargo run --release --example hash_map_cmp_collision

test hash avl map
insert time PT0.000739762S
max node num of single index: 10000
find 10000, time PT0.000690444S
remove time PT0.000497103S

test stl hash map
insert time PT0.093169479S
find 10000, time PT0.079600027S
remove time PT0.089153558S
--------------------------------

变更日志

• 版本 0.1.9

  • 由于rust nightly频繁更改alloc api，使用 libc::{malloc, free} 代替；
  • 请使用稳定的 ops::RangeBounds(自 1.28.0 版本以来稳定) 而不是 collections::range::RangeArgument;

• 版本 0.1.10

  • 函数 avl_node_tear 未能按预期工作；此错误未引起任何错误；