The O1 (as in O(1)) project focuses on implementing hashing schemes for perfect and general-purpose hash tables.

• Basic universal hashing function families.
  • The Dietzfelbinger multiply-shift family.
  • The polynomial family.
  • Optimizations by introducing SIMD instructions.
  • Other optimizations.
• An alternative fast hashing algorithm.
  • XXH3 hashing algorithm.
• The FKS perfect hashing scheme.
  • Compile-time construction.
  • Run-time construction.
  • Hybrid construction (with multi-stage build).
• Benchmarking setup.
  • Against the HashMap from the standard library.
  • Against the HashMap with an alternative hasher.
  • Against phf.
  • Benchmarking of the hash functions.
• Implement the brute-force perfect hashing scheme that guarantees minimal lookup and construction times at the expense of increased memory usage.
• no_std support.
• derive-macro for auto-generation of library's hashers.

• xxh3 - enables the XXH3 hashing algorithm.

The following standards are followed to maintain the project:

• https://www.conventionalcommits.org/en/v1.0.0/
  • "dev" commit type to designate internal, non-user-facing features.
• https://semver.org/
• https://keepachangelog.com/en/1.1.0/
• https://adr.github.io/madr/

• PHF - compile-time static maps based on perfect hashing for Rust: https://github.com/rust-phf/rust-phf
• Perfect hashing:
  • The original paper describing the FKS scheme: https://dl.acm.org/doi/10.1145/828.1884
  • PtrHash - a new scheme focused on lookup speed: https://curiouscoding.nl/posts/ptrhash-paper/
• Benchmarks:
  • Benchmark of minimal perfect hashing schemes: https://github.com/roberto-trani/mphf_benchmark
  • A very detailed benchmark that includes linear-probing, robin-hood and Cuckoo schemes: https://dl.acm.org/doi/10.14778/2850583.2850585
  • Another interesting comparison that includes Cuckoo, Hopscotch and linear probing schemes: http://jakubiuk.net/stuff/hash_tables_cache_performance.pdf