Stores unique signed integer values in a contiguous array. More...
#include <hashset.h>
Collaboration diagram for Ponca::HashSet< N, T, _HashFunctor >:Public Member Functions | |
| void | clear () |
| Empty the array. | |
| bool | insert (int _value) |
| Tries to insert a value in the HashSet. | |
| bool | contains (int _value) const |
| Tries to find a value in the HashSet. | |
Protected Member Functions | |
| bool | search (int _value, int &_searchedIdx) const |
| Search for a value in the HashSet. | |
Detailed Description
class Ponca::HashSet< N, T, _HashFunctor >
Stores unique signed integer values in a contiguous array.
A simple HashMap implementation that mimics a set of indices, by only stores the keys in a Set-like structure (Hence the name HashSet). The internal logic of this HashMap is similar to a std::unordered_map, but is compatible with CUDA.
- Note
- This HashSet type doesn't allow for removal of a single element from the set. It was implemented this way to provide the simplest search and insert method possible
- Warning
- The stored values must never be equal to -1, because it will be mistaken as being empty in the HashSet, and will break the search logic. If you must store -1, change the OFFSET value to something else, by following this simple rule : illegal_value = EMPTY-OFFSET (e.g. set OFFSET to 2 to allow to store -1, but make -2 illegal to store).
For the search, the best case complexity is O(1), and the worst case complexity is O(n). The complexity is entirely dependent on the hashing function, and the given values : If our hashing function produce sparser result for our set of indices, it will reduce the complexity of the searches for both the HashSet::insert and HashSet::contains method.
- See also
- HashDefaultFunctor::hash for the default hashing function
- BitSet For alternative data structure with compatible API
- Template Parameters
-
N The maximum size of the HashSet T The value type stored in the HashSet (Default to int) _HashFunctor For the hashing function (Default to HashDefaultFunctor)
Constructor & Destructor Documentation
◆ HashSet()
|
inlineconstexpr |
Member Function Documentation
◆ clear()
| void Ponca::HashSet< N, T, HF >::clear | ( | ) |
Empty the array.
Iterates over every element and sets their values to the EMPTY flag value (default to -1)
Definition at line 11 of file hashset.hpp.
◆ contains()
| bool Ponca::HashSet< N, T, HF >::contains | ( | int | _value | ) | const |
Tries to find a value in the HashSet.
- Parameters
-
_value The value to search for
Definition at line 63 of file hashset.hpp.
◆ insert()
| bool Ponca::HashSet< N, T, HF >::insert | ( | int | _value | ) |
Tries to insert a value in the HashSet.
- Note
- The hashing function doesn't guarantee that we always get different results, sometimes two different values can happen to have the same storage address in our data array. When the hashing function provokes a collision with another value, the HashSet will store the other value in the next available array address. The search will have to keep looking for the value if it isn't stored at the hashing result, which is why the search isn't always of a O(1) complexity.
- Parameters
-
_value The value to be inserted in the HashSet
- Returns
- True if the value was inserted successfully, and false if the value was already inserted or if the HashSet is full
Definition at line 44 of file hashset.hpp.
◆ search()
Search for a value in the HashSet.
Use the hashing function to check if a value is inside the internal array.
- The value isn't considered inside if the value at the address corresponds to the EMPTY flag, (will stop the search and return false as a result)
- If there is already an element at address, but which doesn't correspond to the value, we keep looking at the next address for our value until we either find it, or until we searched everywhere.
Use a reference to either output the id of the last element that was searched in the m_data array or will output -1 if the array is completely full.
- Parameters
-
_value The value to be inserted in the HashSet _searchedIdx Reference to the last searched index or -1 if the array is full. _hash The hashing function
Definition at line 17 of file hashset.hpp.
