CUDPP 2.0
CUDA Data-Parallel Primitives Library
Public Member Functions
CudaHT::CuckooHashing::CompactingHashTable Class Reference

Hash table that provides O(1) translation between keys and unique identifiers. More...

#include <hash_compacting.h>

Inherits CudaHT::CuckooHashing::HashTable.

List of all members.

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.

Detailed Description

Hash table that provides O(1) translation between keys and unique identifiers.


Member Function Documentation

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.

Parameters:
[in]max_input_sizeLargest expected number of items in the input.
[in]space_usageSize of the hash table relative to the input. Bigger tables are faster to build and retrieve from.
[in]num_functionsNumber of hash functions to use. May be 2-5. More hash functions make it easier to build the table, but increase retrieval times.
Returns:
Whether the hash table was initialized successfully (true) or not (false).
See also:
HashTable::Initialize()

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.

Parameters:
[in]input_sizeNumber of key-value pairs being inserted.
[in]d_keysDevice memory array containing all of the input keys.
[in]d_valsDevice memory array containing the keys' values.
Returns:
Whether the hash table was built successfully (true) or not (false).
See also:
HashTable::Build()

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.

Parameters:
[in]n_queriesNumber of keys in the query set.
[in]d_query_keysDevice memory array containing all of the query keys.
[in]d_query_resultsValues 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.


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines