OpmphmEdge Struct Reference

Order Preserving Minimal Perfect Hash Map. More...

#include <kdbopmphm.h>

Public Attributes
uint32_t	order
uint32_t *	nextEdge
uint32_t *	vertices

Detailed Description

Order Preserving Minimal Perfect Hash Map.

Based on the work of

Fabiano C. Botelho and Nivio Ziviani "Near-Optimal Space Perfect Hashing Algorithms"

and

Zbigniew J. Czech, George Havas, and Bohdan S. Majewski "An Optimal Algorithm for Generating Minimal Perfect Hash Functions" In: Information Processing Letters 43 (1992), pp. 257–264

For usage look in /doc/dev/datastructures.md "datastructures.md"

Theoretical limit of elements:

The whole OPMPHM is limited to the opmphmHashfunction (...) that returns a uint32_t. The limit of elements is than ((2^32) - 1) * r / c, since (2^32) - 1 is the maximum component size of the r-uniform r-partite hypergraph.

To save space the limit of elements is set to (2^32) - 1. The r-uniform r-partite hypergraph

Member Data Documentation

nextEdge

uint32_t* OpmphmEdge::nextEdge

arary with Opmphm->rUniPar indices of the next edge in the lists

order

uint32_t OpmphmEdge::order

desired hash map return value

vertices

uint32_t* OpmphmEdge::vertices

array with Opmphm->rUniPar indices of vertices that the edge connects

---

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

• kdbopmphm.h