Home

hot_set

This container models the concept of an unordered set. It is implemented using Hashing, Open-addressing, and a Tombstone value. Unlike for example google dense_hash, only one tombstone needs to be supplied.

The basic idea is as follows:

The set is a single contiguous array of values. Empty buckets are filled in with a user-supplied "tombstone" representing the empty state. The tombstone may be a compile time constant or may be supplied at runtime. A central conceit is that the user may never insert the tombstone into the container. For example, in a hot_set<Object*> with tombstone nullptr, you may never insert nullptr (or anything comparing equal to nullptr) into the set.

As elements are inserted, they get hashed into empty bucket locations and the tombstone is overwritten with the inserted value.

Collisions are resolved through linear probing. If the probe reaches the last bucket, the probing is restarted from the beginning of the container. IE, we probe from [hash_pos, end) then from [begin, hash_pos).

Erasing an element reassigns that bucket to the tombstone and then rehashes any collisions to restore the table to a consistent state.

Example: hot_set<int> with tombstone 0 and 8 buckets

empty: [ 0 0 0 0 0 0 0 0 ]
insert 4: [ 0 0 4 0 0 0 0 0 ]
insert 6: [ 0 0 4 0 6 0 0 0 ]
insert 5 (collision with 6): [ 0 0 4 0 6 5 0 0 ]
remove 6: [ 0 0 4 0 5 0 0 0 ]
insert 10: [ 0 0 4 0 5 0 0 10 ]
insert 11 (collision with 10): [ 11 0 4 0 5 0 0 10]

The container can be configured with a "load policy" template parameter which defines the growth, occupancy, and hashing behavior of the class.

examples

hot_set<int> my_set( 64 /* number of buckets */, -1 /*tombstone*/);
my_set.insert(0);
assert(my_set.tombstone() == -1);
assert(!my_set.contains(33));
assert(my_set.contains(0);

//same as above, but with compile-time tombstone
//hoc_set can be up to 15% more efficient in some of our tests 
hoc_set<int, -1> my_set(64);

benchmarks

The insertion test simply measures the amount of time to construct the container and insert items.

The abuse test measures the amount of time to insert, query, and conditionally erase items.

hot_map

This class is still under development but will behave almost identically to hot_set. Keys and values are stored in separate memory locations and there will be no need to supply a "value tombstone".