File DenseHashMap.h

↰ Parent directory (ADS/dictionary)

A hash map whose pairs lie in a dense vector, beyond the book: the pairs ( key , value ) are the elements :math:` 0 , ldots , n - 1 ` of a vector, in the order of their insertions up to the removals, and a separate index of open addressing maps a key to the position of its pair in the vector.

Definition (ADS/dictionary/DenseHashMap.h)

Detailed Description

A visit of the pairs is then a scan of n contiguous pairs, with no empty place in between, and the index is rebuilt from the vector without moving a pair; the price is one more access per search (the index, then the pair) and iterators that an insertion or a removal may invalidate, as for a vector [see File FlatHashTable.h for the table whose pairs never move].

The index is made of groups of one line of cache, 64 bytes: 16 control bytes, of which the first 12 are those of the 12 places of the group, empty (0) or full, in which case the byte is a fingerprint of 8 bits of the hash of the key, never 0, and the 16th is a byte of overflow, and 12 positions of 32 bits in the vector. The control bytes are compared with the fingerprint of a key all at once, by SSE2, NEON or broadword operations as in FlatHashTable, and the positions of the places that match are in the same line, so that a search costs one miss in the index and one in the vector. The hash is mixed as in FlatHashTable: the top bits give the first group, the low 8 bits the fingerprint and the bits 8 to 10 the bit of the key in the bytes of overflow; the G groups, a power of 2, are inspected in the triangular order :math:` g_i = ( g_0 + i ( i + 1 ) / 2 ) bmod G `, an insertion that goes past a full group sets in its byte of overflow the bit of its key, and a search stops at the first group whose overflow lacks the bit of its key.

A removal empties the place of the key in the index and moves the last pair of the vector into the position left free (a swap with the last and a pop), so that the vector stays dense: the place of the last pair in the index is found by the inspection of its key, comparing the positions and not the keys, and takes the new position. The place emptied is written as a whole group, at an address that depends only on the hash, so that the loads of the next operations need not wait for the control bytes [see File FlatHashTable.h]. A place emptied in a group with some overflow still counts as full until the next rebuild; the places counted are bounded by one more per removal and counted exactly only when the full places and the bound reach :math:` 7 m / 8 ` of the m places, the index being rebuilt if fewer than :math:` m / 16 ` places are left, twice as large if the pairs exceed half of :math:` 7 m / 8 . A rebuild reads the keys in the vector in order, hashes them again and fills the new groups, each in the order of its places; so each operation costs :math: O( 1 ) ` expected amortized time, with the expected number of groups inspected by a search bounded by a constant for a load at most 7 / 8 and a hash that behaves as random.

Space: :math:` 16 n ` bytes for pairs of 16 bytes, plus 64 bytes per 12 places of the index, about :math:` 5.3 ` bytes per place, at a load between 7 / 16 and 7 / 8 after the first growth.

The iterators are those of the vector of the pairs, constant, in the order of the positions; an insertion of a new key may move the vector and invalidates them, a removal moves the last pair into the position of the removed one, and an insertion of a key already there replaces its value in place. find() gives a value to change in place. The keys and the values must be movable; there are fewer than :math:` 2^{32} ` pairs.

The contracts [see File Contract.h]: after insert() the key is in the map and after remove() it is not; the invariant is that each position of the vector is held by exactly one full place of the index, reached by the inspection of its key, and that the full places and the bound of those counted stay at most 7 / 8 of the places; on an index of more than 1024 places, only the inspection of the key of the operation is checked. The operations are defined in DenseHashMap.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, 1998, section 6.4 (open addressing, the multiplicative hashing)

  1. Kulukundis, Designing a fast, efficient, cache-friendly hash table, step by step, CppCon 2017 (the control bytes and the groups)

    1. Lopez Munoz, Inside boost::unordered_flat_map, 2022 (the groups with a byte of overflow, the mixing of the hash), https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html

  1. Hettinger, More compact dictionaries with faster iteration, python-dev, 2012, https://mail.python.org/pipermail/python-dev/ 2012-December/123028.html (the pairs in a dense vector apart from an index of positions, the layout of the dictionaries of CPython 3.6)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes