18 stable releases

1.4.2 Oct 24, 2023
1.4.1 Dec 26, 2022
1.4.0 Jul 14, 2022
1.3.3 Mar 11, 2022
1.2.0 Nov 17, 2020

#50 in Memory management

Download history 45/week @ 2024-03-13 5/week @ 2024-03-20 13/week @ 2024-03-27 23/week @ 2024-04-03 24/week @ 2024-04-10 161/week @ 2024-04-17 243/week @ 2024-04-24 335/week @ 2024-05-01 192/week @ 2024-05-08 192/week @ 2024-05-15 213/week @ 2024-05-22 217/week @ 2024-05-29 241/week @ 2024-06-05 134/week @ 2024-06-12 112/week @ 2024-06-19 186/week @ 2024-06-26

687 downloads per month
Used in 3 crates

MIT license

49KB
1.5K SLoC

smallmap

A small table map using single byte key indecies. Designed for maps with tiny keys.

Pages are stored as 256 entry key-value arrays which are indexed by the byte key index. The key is compared for collision check and on collision the next page is checked or inserted if needed. smallmap does not ever need to allocate more than 1 page for types which all invariants can be represented as unique bytes.

Usage

The API is a similar subset to HashMap, containing the same insert, get, and entry functions:

fn max_char(chars: &str) -> (char, usize)
{
    let mut map = Map::new();
    for x in chars.chars() {
		*map.entry(x).or_insert(0usize) += 1;	
    }

	map.into_iter().max_by_key(|&(_, v)| v).unwrap_or_default()
}

Use cases

Designed for instances where you want a small map with relatively trivial keys (e.g. primitive type). Performance can greately outpace hash-based by an order of magnitude or more in these cases.

Maybe use if

  • You have small keys
  • Your map is not at risk of Denial of Service attacks.
  • Your keys are not expected to have a lot of collisions when represented as u8.

Don't use if

  • You have complex keys
  • Denial of service is a concern
  • Your map will contain a large volume of entries
  • Your keys may have a large number of collisions when represented as u8.

Benchmarks

Some crude and basic benchmarks

char

Which ns/iter
HashMap 16
smallmap::Map 7

Iterating a string's chars and counting each

Which ns/iter (entry) ns/iter (get/insert)
HashMap 8,418 8,367
BTreeMap 9,742 6,329
smallmap::Map 4,416 1,739

u8

Which ns/iter
HashMap 15
smallmap::Map 2

License

MIT licensed

Dependencies

~185KB