Compact Cuckoo hashing (Algorithm 4 from the paper). More...

Public Member Functions
int	Run (std::span< const In > as, int m, int4 sigma, __uint128_t n, int b_size, int ch_retry, std::span< std::pair< int, int > > table)
	Run Cuckoo hashing to place elements into a table.

Detailed Description

template<typename Prp, typename In, int kappa = 3>
requires Permutable<Prp>
struct fss::cuckoo_hash::Compact< Prp, In, kappa >

Compact Cuckoo hashing (Algorithm 4 from the paper).

Inserts elements into m buckets using kappa hash functions via Cuckoo hashing with random walk eviction.

Template Parameters

Prp	PRP type satisfying Permutable.
In	Input domain type (unsigned integer up to __uint128_t).

Member Function Documentation

template<typename Prp , typename In , int kappa = 3>

int fss::cuckoo_hash::Compact< Prp, In, kappa >::Run	(	std::span< const In >	as,
		int	m,
		int4	sigma,
		__uint128_t	n,
		int	b_size,
		int	ch_retry,
		std::span< std::pair< int, int > >	table
	)

inline

Run Cuckoo hashing to place elements into a table.

Each table entry stores (index_into_as, hash_fn_k), or (-1, -1) if empty.

Parameters

as	Input elements.
m	Number of buckets.
sigma	PRP seed.
n	Domain size (N = 2^{in_bits}).
b_size	Bucket size B.
ch_retry	Max eviction attempts before failure.
table	Pre-allocated span of size m. Filled on success.

The documentation for this struct was generated from the following file: