engineering-k-perfect-hashing
Science Score: 67.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
✓DOI references
Found 1 DOI reference(s) in README -
✓Academic publication links
Links to: arxiv.org -
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (11.3%) to scientific vocabulary
Repository
Basic Info
- Host: GitHub
- Owner: stefanfred
- License: gpl-3.0
- Language: C++
- Default Branch: master
- Size: 4.36 MB
Statistics
- Stars: 0
- Watchers: 2
- Forks: 0
- Open Issues: 0
- Releases: 0
Metadata Files
README.md
Engineering Minimal k-Perfect Hash Functions
A k-perfect hash function is a hash function that maps a set of keys to a set of integers. Each output value might collide with up to k other keys.
The techniques included in this repository are described in our paper. Please cite it if you use our code in an academic context.
This repository contains a selection of k-perfect hash function implementations. It also includes benchmarks comparing them to other approaches from the literature.
Construction Performance (100M keys)
Benchmark framework
The benchmark framework for k-perfect hash functions can be found in the contenders and benchmarklib folders.
To build the benchmarks, clone this repository (with submodules) and run the following commands.
cmake -B ./build -DCMAKE_BUILD_TYPE=Release
cmake --build build
You can then generate the plots using ./build/Comparison.
Use ./build/Comparison --help to view available command line arguments.
Library Usage
Clone this repository (with submodules) and add the following to your CMakeLists.txt.
add_subdirectory(path/to/kPerfectHashing)
target_link_libraries(YourTarget PRIVATE Kphf::<hash function to use>)
You can link with one of the following targets. Each target is a different k-perfect hash function with its own set of dependencies.
Kphf::PaCHashKphf::RecSplitKphf::HashDisplaceKphf::ThresholdBasedBumping
License
This code is licensed under the GPLv3.
If you use this work in an academic context or publication, please cite our paper:
@article{hermann2025engineering,
author = {Stefan Hermann and Sebastian Kirmayer and Hans-Peter Lehmann and Peter Sanders and Stefan Walzer},
title = {Engineering Minimal k-Perfect Hash Functions},
journal = {CoRR},
volume = {abs/2504.20001},
year = {2025},
doi = {10.48550/ARXIV.2504.20001}
}
Owner
- Name: Stefan Hermann
- Login: stefanfred
- Kind: user
- Repositories: 1
- Profile: https://github.com/stefanfred
Citation (CITATION.cff)
cff-version: 1.2.0
message: "If you use this software in an academic context or publication, please cite it as below."
authors:
- family-names: "Hermann"
given-names: "Stefan"
orcid: "https://orcid.org/0000-0001-9183-2926"
- family-names: "Kirmayer"
given-names: "Sebastian"
- family-names: "Lehmann"
given-names: "Hans-Peter"
orcid: "https://orcid.org/0000-0002-0474-1805"
- family-names: "Sanders"
given-names: "Peter"
orcid: "https://orcid.org/0000-0003-3330-9349"
- family-names: "Walzer"
given-names: "Stefan"
orcid: "https://orcid.org/0000-0002-6477-0106"
title: "Engineering Minimal k-Perfect Hash Functions"
preferred-citation:
title: "Engineering Minimal k-Perfect Hash Functions"
authors:
- family-names: "Hermann"
given-names: "Stefan"
orcid: "https://orcid.org/0000-0001-9183-2926"
- family-names: "Kirmayer"
given-names: "Sebastian"
- family-names: "Lehmann"
given-names: "Hans-Peter"
orcid: "https://orcid.org/0000-0002-0474-1805"
- family-names: "Sanders"
given-names: "Peter"
orcid: "https://orcid.org/0000-0003-3330-9349"
- family-names: "Walzer"
given-names: "Stefan"
orcid: "https://orcid.org/0000-0002-6477-0106"
doi: "10.48550/ARXIV.2504.20001"
year: 2025
GitHub Events
Total
- Member event: 2
- Push event: 2
- Create event: 2
Last Year
- Member event: 2
- Push event: 2
- Create event: 2