Flat Multimap

A multimap and multiset implementation using a flattened hash table

lib.rs:

A multimap and multiset implementation using a flattened hash table.

FlatMultimap is a multimap implementation where entries are stored as a flattened hash map:

• a -> 1
• a -> 2
• b -> 3

as opposed to the common implementation using a hash map which maps keys to a collection of values:

• a -> 1, 2
• b -> 3

FlatMultiset is a multiset implementation where items are stored as a flattened hash set:

• a
• a
• b

as opposed to the common implementation using a hash map which maps items to a variable counting the number of occurances:

• a -> 2
• b -> 1

Storing elements as a flattened hash table can have the benefit that it saves space compared to the common implementations. This can be the case when there are very few duplicates and/or the size of the elements is very small.

Disadvantages of storing elements this way compared to the common implementations is that much more space is required when there are many duplicates. Furthermore, there are no efficient operations which can get all the values associated with a single key (in the case of a map), and no efficient operations to count the number of duplicates.