Basic hash table that stores one value for each key. More...

#include <hash_table.h>

Inherited by CudaHT::CuckooHashing::CompactingHashTable, and CudaHT::CuckooHashing::MultivalueHashTable.

Public Member Functions
virtual bool	Initialize (const unsigned max_input_size, const float space_usage=1.25, const unsigned num_functions=4)

virtual void	Release ()
	Free all memory.

virtual bool	Build (const unsigned input_size, const unsigned d_keys, const unsigned d_vals)
	Build the hash table. More...

virtual void	Retrieve (const unsigned n_queries, const unsigned d_query_keys, unsigned d_query_results)
	Query the hash table. More...

Accessors
Mainly needed to use the device CudaHT::retrieve() function directly.
unsigned	get_table_size () const
	Returns how many slots the hash table has.

unsigned	get_stash_count () const
	Returns how many items are stored in the stash.

uint2	get_stash_constants () const
	Returns the constants used by the stash.

const Entry *	get_contents () const
	Returns the hash table contents.

unsigned	get_num_hash_functions () const
	Returns the number of hash functions being used.

Functions< 2 >	get_constants_2 () const
	When using two hash functions, returns the constants.

Functions< 3 >	get_constants_3 () const
	When using three hash functions, returns the constants.

Functions< 4 >	get_constants_4 () const
	When using four hash functions, returns the constants.

Functions< 5 >	get_constants_5 () const
	When using five hash functions, returns the constants.

void	setTheCudpp (CUDPPHandle theCudpp_)
	Set the internal CUDPP instance.

Protected Attributes
unsigned	table_size_
	Size of the hash table.

unsigned	num_hash_functions_
	Number of hash functions being used.

Entry *	d_contents_
	Device memory: The hash table contents. The stash is stored at the end.

unsigned	stash_count_
	Number of key-value pairs currently stored.

uint2	stash_constants_
	Hash function constants for the stash.

Functions< 2 >	constants_2_
	Constants for a set of two hash functions.

Functions< 3 >	constants_3_
	Constants for a set of three hash functions.

Functions< 4 >	constants_4_
	Constants for a set of four hash functions.

Functions< 5 >	constants_5_
	Constants for a set of five hash functions.

unsigned *	d_failures_
	Device memory: General use error flag.

CUDPPHandle	theCudpp
	CUDPP instance.

Detailed Description

Basic hash table that stores one value for each key.

The input consists of two unsigned arrays of keys and values. None of the keys are expected to be repeated.

Todo:: Templatize the interface without forcing the header file to have CUDA calls.

Member Function Documentation

bool CudaHT::CuckooHashing::HashTable::Initialize	(	const unsigned	max_input_size,
		const float	space_usage = `1.25`,
		const unsigned	num_functions = `4`
	)

virtual

Initialize the hash table's memory. Must be called before Build() and after the random number generator has been seeded.

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.

Returns: Whether the hash table was initialized successfully (true) or not (false).

The minimum space usage is dependent on the number of functions being used; for two through five functions, the minimum space usage is 2.1, 1.1, 1.03, and 1.02 respectively.

Reimplemented in CudaHT::CuckooHashing::MultivalueHashTable, and CudaHT::CuckooHashing::CompactingHashTable.

bool CudaHT::CuckooHashing::HashTable::Build	(	const unsigned	input_size,
		const unsigned *	d_keys,
		const unsigned *	d_vals
	)

virtual

Build the hash table.

Parameters

[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.

Returns: Whether the hash table was built successfully (true) or not (false).

Several attempts are allowed to build the hash table in case of failure. The input keys are expected to be completely unique. To reduce the chance of a failure, increase the space usage or number of functions. Keys are not allowed to be equal to CudaHT::CuckooHashing::kKeyEmpty.

Reimplemented in CudaHT::CuckooHashing::CompactingHashTable, and CudaHT::CuckooHashing::MultivalueHashTable.

void CudaHT::CuckooHashing::HashTable::Retrieve	(	const unsigned	n_queries,
		const unsigned *	d_query_keys,
		unsigned *	d_query_results
	)

virtual

Query the hash table.

Parameters

[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.

kNotFound is returned for any query key that failed to be found in the table.

Reimplemented in CudaHT::CuckooHashing::CompactingHashTable, and CudaHT::CuckooHashing::MultivalueHashTable.

The documentation for this class was generated from the following files:

/home/edmund/tree/cudpp/src/cudpp_hash/hash_table.h
/home/edmund/tree/cudpp/src/cudpp_hash/hash_table.cpp

Public Member Functions

Protected Attributes

Detailed Description

Member Function Documentation