README

This is meant as a replacement for the current QHash implementation for Qt 6.

The implementation doesn't yet support QMultiHash (which will come as a fully
seperated class, not inheriting QHash).

The data structure here is a bit inspired by tsl_spare_map
(https://github.com/Tessil/sparse-map), but did significant changes to it.

The hash table uses open addressing and a two level data structure.

The hash table contains a vector of Span(s), that can each hold up to 128
entries. The hash table has thus nBuckets/128 Spans.

Each Span contains a 128 byte large offset table into a vector of Nodes (key/value
pairs). The vector of nodes grows on demand and is managed by a singly linked free
list. Newly inserted items allocate one new node in the vector, and set the offset
byte in the offsets table to point to this entry.

Collisions are handled by quadratic probing, and the hash table is always kept between
25% and 50% full.

The amount of buckets in the hash table is a power of two for most types (as we assume
reasonably good hashing functions). For integer and pointer types the hash functions
usually are the identity function and thus give relatively bad distributions. For those
types, we statically switch the hash table to use prime number based bucket sizing.

The table performs extremely well compared to many other hash tables. For comparisons,
the hash_table_shootout (see https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html
and https://github.com/Tessil/hash-table-shootout) benchmark was used, which measures both
performance and memory consumption.

Results against some major hash table implementations (tested on Linux using gcc) can be found
in the results folder.