Crate hash_arr_map[][src]

Expand description

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.


pub use map::Ham;
pub use set::HashArrSet;



A value represented as an index.


This is partly like Cow, but the ‘owned’ type is always the same as the ‘borrowed’ type.


Conversion from an Idx.

An attempted conversion into an Idx.

Whether a new index can be created out of thin air for the value.