Template Class ApproxHashSet

Class Documentation

template <size_t unmasked_bits, size_t full_reset_threshold, typename IndexType, typename IndexTypeHasher>
class ApproxHashSet

Acts as a fast and thread safe set, with the serious limitation of both false-negatives and false positives being possible.

A false positive occurs if two different elements have the same hash, and the other element was already added to the set. A false negative occurs if an element was removed to add another element with the same masked hash. The chance of this happening is inversely proportional to 2^unmasked_bits. Uses at least (2^unmasked_bits + full_reset_threshold) * sizeof(StoreElement) bytes of ram. Note that the reset function is not thread safe.

Public Functions

ApproxHashSet()
bool isHashCurrentlyPresent(const size_t &hash)

Returns true if an element with the same hash is currently in the set, false otherwise.

Note due to the masking of bits, many elements that were previously inserted into the ApproxHashSet have been overwritten by other values.

bool isHashCurrentlyPresent(const IndexType &index, size_t *hash)
bool isHashCurrentlyPresent(const IndexType &index)
bool replaceHash(const size_t &hash)

Returns true if it replaced the element in the masked_hash’s with the hash of the given element.

Returns false if this hash was already there and no replacement was needed. THIS IS THE MOST EXPENSIVE FUNCTION IN ALL OF VOXBLOX. PROILE AND TEST AFTER EVEN THE MOST SUPERFICIAL CHANGE !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Also note that while the below layout of ifs and variables may not appear the most efficient the compiler seems to do some black magic with it that makes it come out ahead of other formulations.

bool replaceHash(const IndexType &index, size_t *hash)
bool replaceHash(const IndexType &index)
void resetApproxSet()

If unmasked_bits is large, the array takes a lot of memory, this makes clearing it slow.

However offsetting which bin hashes are placed into has the same effect. Once we run out of room to offset by (determined by full_reset_threshold) we clear the memory). This function is not thread safe.