Ben Chuanlong Du's Blog

It is never too late to learn.

Map in Rust

In [ ]:
:timing
:sccache 1

Tips and Traps

  1. Summary of Collections in Rust has a good summary on when to each which collection in Rust.

  2. std::collections::HashMap has a good discussions on implementation details of HashMap and things to note when use it.

  3. BTreeMap is a sorted alternative to HashMap.

  4. hashbrown is a Rust port of Google's high-performance SwissTable hash map, adapted to make it a drop-in replacement for Rust's standard HashMap and HashSet types.

  5. indexmap is a hash table which preserves (in a limited sense) insertion order. It is similar to dict in Python 3.7+.

  6. fnv is an implementation of the Fowler–Noll–Vo hash function.

  7. Fast Hashing Algorithms has a good discussion of fast hashing algorithms.

Hash code and Hash Maps

  • hashbrown is a Rust port of Google's high-performance SwissTable hash map, adapted to make it a drop-in replacement for Rust's standard HashMap and HashSet types since Rust 1.36. However, you might still want to use hashbrown for a few reasons.

    • hashbrown uses AHash as the default hasher, which is less secure but much faster than SipHash (default hash used in the Rust standard library).
    • It can be used in an environment without std.

  • fnv is an implementation of the Fowler–Noll–Vo hash function.

  • phf provides runtime support for perfect hash function data structures

  • indexmap A hash table with consistent order and fast iteration. The indexmap is a hash table where the iteration order of the key-value pairs is independent of the hash values of the keys. It has the usual hash table functionality, it preserves insertion order except after removals, and it allows lookup of its elements by either hash table key or numerical index.

  • dashmap is a blazing fast concurrent HashMap for Rust.

  • TinySet provides a few collections that are optimized to scale in size well for small numbers of elements, while still scaling well in time (and size) for numbers of elements.

  • schnellru is a fast and flexible LRU map.

  1. For simple integer hashing functions, integer modulo is a very BAD (in terms of speed) hashing function while the multiplicative hashing is a much better alternative.

  2. By default, Rust hash tables use Siphash 1-3, a hash function that is high quality but fairly slow. In contrast, the Rust compiler uses as hash function called FxHasher, which is surprisingly simple yet effective.

  3. FNV Hash and AHash.

std::collections::HashMap

In [2]:
use std::collections::HashMap;
In [6]:
let mut map: HashMap<i32, i32> = HashMap::new();
In [11]:
map.get(&1)
Out[11]:
None
In [10]:
map.contains_key(&1)
Out[10]:
false
In [12]:
map.insert(1, 1000)
In [13]:
map.get(&1)
Out[13]:
Some(1000)
In [14]:
map.get(&1).unwrap()
Out[14]:
1000
In [15]:
map.contains_key(&1)
Out[15]:
true

Update the value of the key 1.

In [22]:
*map.get_mut(&1).unwrap() += 1;
In [23]:
map.get(&1)
Out[23]:
Some(1001)

with_capacity

In [3]:
let mut m2: HashMap<i32, i32> = HashMap::with_capacity(10);
m2
Out[3]:
{}
In [4]:
m2.len()
Out[4]:
0
In [5]:
m2.capacity()
Out[5]:
14
In [6]:
m2.insert(1,1);
In [7]:
m2.len()
Out[7]:
1
In [8]:
m2.capacity()
Out[8]:
14

std::collections::BTreeMap

In [2]:
use std::collections::BTreeMap;
In [3]:
let mut m: BTreeMap<u32, Vec<usize>> = BTreeMap::new();
In [6]:
m.insert(1000, vec![2, 7]);
In [16]:
m.insert(100, vec![3, 4]);
In [19]:
m.insert(333, vec![36, 21]);
In [15]:
m.get(&0)
Out[15]:
None
In [13]:
m.get_mut(&1000).unwrap().push(111);
In [14]:
m.get(&1000)
Out[14]:
Some([2, 7, 111])

Confirm that keys of BTreeMap are sorted.

In [20]:
for k in m.keys() {
    println!("{}", k);
}

100
333
1000
Out[20]:
()

References

In [ ]:

Comments