hash_table.h File Reference

Header for a basic hash table that stores one value per key. More...

#include "definitions.h"
#include "hash_functions.h"
#include <cstdio>
#include <cudpp.h>

Classes
class	CudaHT::CuckooHashing::HashTable
	Basic hash table that stores one value for each key. More...

Namespaces
	CudaHT
	Encapsulates the hash table library.
	CuckooHashing
	Encapsulates the cuckoo hash table that uses stashes.

Functions
void	CudaHT::CuckooHashing::CUDAWrapper::ClearTable (const unsigned slots_in_table, const Entry fill_value, Entry *d_array)
	Fills a 64-bit array with a particular value.
void	CudaHT::CuckooHashing::CUDAWrapper::CallCuckooHash (const unsigned n_entries, const unsigned num_hash_functions, const unsigned *d_keys, const unsigned *d_values, const unsigned table_size, const Functions< 2 > constants_2, const Functions< 3 > constants_3, const Functions< 4 > constants_4, const Functions< 5 > constants_5, const unsigned max_iteration_attempts, Entry *d_contents, uint2 stash_constants, unsigned *d_stash_count, unsigned *d_failures, unsigned *d_iterations_taken)
	Calls the Cuckoo Hash construction kernel.
void	CudaHT::CuckooHashing::CUDAWrapper::CallHashRetrieve (const unsigned n_queries, const unsigned num_hash_functions, const unsigned *keys_in, const unsigned table_size, const Entry *table, const Functions< 2 > constants_2, const Functions< 3 > constants_3, const Functions< 4 > constants_4, const Functions< 5 > constants_5, const uint2 stash_constants, const unsigned stash_count, unsigned *values_out)
	Calls the kernel that performs retrievals.
Internal
dim3	CudaHT::CuckooHashing::ComputeGridDim (unsigned threads)
	Compute how many thread blocks are required for the given number of threads.
unsigned	CudaHT::CuckooHashing::ComputeMaxIterations (const unsigned num_keys, const unsigned table_size, const unsigned num_functions)
	Compute how long an eviction chain is allowed to become for a given input size. More...

Detailed Description

Header for a basic hash table that stores one value per key.

Function Documentation

unsigned CudaHT::CuckooHashing::ComputeMaxIterations	(	const unsigned	num_keys,
		const unsigned	table_size,
		const unsigned	num_functions
	)

Compute how long an eviction chain is allowed to become for a given input size.

Parameters

[in]	num_keys	Number of keys in the input.
[in]	table_size	Number of slots in the hash table.
[in]	num_functions	Number of hash functions being used.

Returns

The number of iterations that should be allowed.

The latter two parameters are only needed when using an empirical formula for computing the chain length.