The Complete Rust Programming Reference Guide

Maps and sets

Rust's maps and sets are based largely on two strategies: B-Tree search and hashing. They are very distinct implementations, but achieve the same results: associating a key with a value (map) and providing a fast unique collection based on keys (set).

Hashing in Rust works with a Hasher trait, which is a universal, stateful hasher, to create a hash value from an arbitrary byte stream. By repeatedly calling the appropriate write() function, data can be added to the hasher's internal state and finished up with the finish() function.

Unsurprisingly the B-Tree in Rust is highly optimized. The BTreeMap documentation provides rich details on why the regular implementation (as previously shown) is cache inefficient and not optimized ...