CUDPP 2.0
CUDA Data-Parallel Primitives Library
|
Hash table that provides O(1) translation between keys and unique identifiers. More...
#include <hash_compacting.h>
Inherits CudaHT::CuckooHashing::HashTable.
Public Member Functions | |
virtual bool | Initialize (const unsigned max_input_size, const float space_usage=1.25, const unsigned num_functions=4) |
Initializes the compacting hash table's memory. | |
virtual bool | Build (const unsigned input_size, const unsigned *d_keys, const unsigned *d_vals) |
Builds a compacting hash table. | |
virtual void | Retrieve (const unsigned n_queries, const unsigned *d_query_keys, unsigned *d_query_results) |
Queries the hash table for the unique identifiers of the query keys. | |
virtual void | Release () |
Releases all of the memory. | |
unsigned | get_unique_keys_size () const |
Returns the number of unique keys found in the input. | |
const unsigned * | get_unique_keys () const |
Returns the unique keys found in the input. |
Hash table that provides O(1) translation between keys and unique identifiers.
bool CudaHT::CuckooHashing::CompactingHashTable::Initialize | ( | const unsigned | max_input_size, |
const float | space_usage = 1.25 , |
||
const unsigned | num_functions = 4 |
||
) | [virtual] |
Initializes the compacting hash table's memory.
See HashTable::Initialize() for an explanation of the parameters.
[in] | max_input_size | Largest expected number of items in the input. |
[in] | space_usage | Size of the hash table relative to the input. Bigger tables are faster to build and retrieve from. |
[in] | num_functions | Number of hash functions to use. May be 2-5. More hash functions make it easier to build the table, but increase retrieval times. |
Reimplemented from CudaHT::CuckooHashing::HashTable.
bool CudaHT::CuckooHashing::CompactingHashTable::Build | ( | const unsigned | input_size, |
const unsigned * | d_keys, | ||
const unsigned * | d_vals | ||
) | [virtual] |
Builds a compacting hash table.
See HashTable::Build() for an explanation of the parameters. Keys may be repeated; the structure will compact them down into a list of unique keys and assign each a unique key an ID from 0 to K-1, where K is the number of unique keys. The values are not used with this structure and are ignored.
[in] | input_size | Number of key-value pairs being inserted. |
[in] | d_keys | Device memory array containing all of the input keys. |
[in] | d_vals | Device memory array containing the keys' values. |
Reimplemented from CudaHT::CuckooHashing::HashTable.
void CudaHT::CuckooHashing::CompactingHashTable::Retrieve | ( | const unsigned | n_queries, |
const unsigned * | d_query_keys, | ||
unsigned * | d_query_results | ||
) | [virtual] |
Queries the hash table for the unique identifiers of the query keys.
[in] | n_queries | Number of keys in the query set. |
[in] | d_query_keys | Device memory array containing all of the query keys. |
[in] | d_query_results | Values for the query keys. |
CUDPP_HASH_KEY_NOT_FOUND is returned for any query key that failed to be found in the table.
Reimplemented from CudaHT::CuckooHashing::HashTable.