https://github.com/bytehamster/fips
A very simple and fast implementation of perfect hashing through fingerprinting.
Science Score: 39.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
✓DOI references
Found 2 DOI reference(s) in README -
○Academic publication links
-
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (9.3%) to scientific vocabulary
Repository
A very simple and fast implementation of perfect hashing through fingerprinting.
Basic Info
Statistics
- Stars: 1
- Watchers: 2
- Forks: 1
- Open Issues: 0
- Releases: 0
Metadata Files
README.md
FiPS
A minimal perfect hash function (MPHF) maps a set S of n keys to the first n integers without collisions. Perfect hash functions have applications in databases, bioinformatics, and as a building block of various space-efficient data structures.
FiPS (Finperprint Perfect Hashing through Sorting) is a very simple and fast implementation of perfect hashing through fingerprinting.
The idea of perfect hashing through fingerprinting is to hash each input key to a fingerprint. An array stores a bit for each possible fingerprint indicating whether keys collided. Colliding keys are handled in another layer of the same data structure. There are many implementations of the approach, for example FMPH (Rust).
The construction of perfect hashing through fingerprinting is usually implemented as a linear scan, producing a fault for every key. Instead, FiPS is based on sorting the keys, which is more cache friendly and faster. Also, it interleaves its select data structure with the payload data, which enables very fast queries. Lastly, the FiPS implementation is very simple, with just about 200 lines of code.
Library usage
Clone this repository (with submodules) and add the following to your CMakeLists.txt.
add_subdirectory(path/to/FiPS)
target_link_libraries(YourTarget PRIVATE FiPS::fips)
You can construct a FiPS perfect hash function as follows.
cpp
std::vector<std::string> keys = {"abc", "def", "123", "456"};
fips::FiPS<> hashFunc(keys, /* gamma = */ 2.0f);
std::cout << hashFunc("abc") << std::endl;
Licensing
This code is licensed under the GPLv3.
Owner
- Login: ByteHamster
- Kind: user
- Location: Germany
- Company: Karlsruhe Institute of Technology
- Website: https://www.bytehamster.com
- Repositories: 50
- Profile: https://github.com/ByteHamster
I'm a PhD student at Karlsruhe Institute of Technology. In my freetime, I maintain AntennaPod and contribute to other projects like K-9 Mail and Baikal Server.
GitHub Events
Total
- Watch event: 3
- Delete event: 1
- Push event: 16
- Public event: 1
- Fork event: 1
- Create event: 1
Last Year
- Watch event: 3
- Delete event: 1
- Push event: 16
- Public event: 1
- Fork event: 1
- Create event: 1
Committers
Last synced: about 1 year ago
Top Committers
| Name | Commits | |
|---|---|---|
| ByteHamster | i****o@b****m | 27 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: about 1 year ago
All Time
- Total issues: 0
- Total pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Total issue authors: 0
- Total pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0