fss::cuckoo_hash::PrpHash< Prp, In, kappa > Struct Template Reference

PRP-based hash for Cuckoo hashing. More...

Public Member Functions
std::pair< int, int >	Locate (int4 sigma, In x, int k, __uint128_t n, int b_size)
	Compute bucket index and within-bucket index for hash function k.

Public Attributes
Prp	prp

Detailed Description

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

PRP-based hash for Cuckoo hashing.

Implements the hash functions from Equations (1) and (2) of the paper using a PRP.

Template Parameters

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

Member Function Documentation

Locate()

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

std::pair< int, int > fss::cuckoo_hash::PrpHash< Prp, In, kappa >::Locate ( int4  sigma, In  x, int  k, __uint128_t  n, int  b_size  )

inline

Compute bucket index and within-bucket index for hash function k.

Implements the paper's Equations (1) and (2): y = PRP(sigma, x + n * k) bucket = y / b_size index = y % b_size

Parameters

sigma	PRP seed.
x	Input element.
k	Hash function index (0-indexed, in [0, kappa)).
n	Domain size (N = 2^{in_bits}).
b_size	Bucket size B.

Returns

(bucket_index, within_bucket_index).

---

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

• include/fss/cuckoo_hash.cuh