The hash_arr_map Crate

This crate contains a different implementation of a hash map that, instead of always storing both the key and the value, can, for specific keys, just store the value, inferring the key from the value's context.

This results in the map having separate array and hash parts, where the hash part stores both keys and values, while the array part stores just values. The array part's indices are 1-based, meaning that a key of 0 will not be stored in it.

The design is based on Lua's table design, which is the language's associative hash map. Due to it being Lua's only data structure, it was used with integer keys very frequently. In order to improve the performance of tables with integer keys, a separate array section was created that was only indexed by integer, meaning that keys did not need to be hashed.

As an example, say you make a new [Ham] with a capacity of 2 in the array part and 2 in the hash part.

use hash_arr_map::Ham;
let mut map = Ham::with_capacity(2, 2);

You then feed it the key-value pairs 1, 10, 2, 20, 3, 30, and 4, 40.

map.insert(1, 10);
map.insert(2, 20);
map.insert(3, 30);
map.insert(4, 40);

The map will not have allocated, since there is ample capacity.

One possible layout of the map would be this:

+----------------------------+
|             Ham            |
| +------------+-----------+ |   +----+----+----+----+
| | array_part | hash_part ----> |  4 | 40 |  3 | 30 |
| +-----|------+-----------+ |   +----+----+----+----+
+-------|--------------------+
        |    +----+----+
        '--> | 10 | 20 |
             +----+----+

Note that the keys of 1 and 2 have not been stored. This is because they can be recalculated from the index into the array part.