Robin Hood Hashing

Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
Alternatives To Robin Hood Hashing
Project NameStarsDownloadsRepos Using ThisPackages Using ThisMost Recent CommitTotal ReleasesLatest ReleaseOpen IssuesLicenseLanguage
Phc Winner Argon24,31339 days ago1February 27, 201878otherC
The password hash Argon2, winner of PHC
Blake33,96314519 hours ago25January 25, 202299otherAssembly
the official Rust and C implementations of the BLAKE3 cryptographic hash function
Jssha2,1571,6573805 months ago20December 07, 20202bsd-3-clauseTypeScript
A JavaScript/TypeScript implementation of the complete Secure Hash Standard (SHA) family (SHA-1, SHA-224/256/384/512, SHA3-224/256/384/512, SHAKE128/256, cSHAKE128/256, and KMAC128/256) with HMAC.
2 days ago61gpl-3.0C++
📝 File hashing and checking shell extension
Imagehash1,8783023 months ago14November 29, 202132mitPHP
🌄 Perceptual image hashing for PHP
Deepdiff1,6754082243 days ago63April 10, 202264otherPython
DeepDiff: Deep Difference and search of any Python object/data. DeepHash: Hash of any object based on its contents. Delta: Use deltas to reconstruct objects by adding deltas together.
4 years ago1February 27, 20183otherC++
Advanced library for randomization, hashing and statistical analysis (devoted to chaos machines). :microscope:
Cryptopasta1,509123684 years agoOctober 03, 202111otherGo
copy & paste-friendly golang crypto
Robin Hood Hashing1,352
a month ago21mitC++
Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
Object Hash1,257179,5491,4683 months ago47February 18, 202235mitJavaScript
Generate hashes from javascript objects in node and the browser.
Alternatives To Robin Hood Hashing
Select To Compare

Alternative Project Comparisons

➵ robin_hood unordered map & set Release GitHub license

NOTE: Unfortunately I do not have time to continue development for this hashmap. I have a worthy successor though, please head over to: ankerl::unordered_dense::{map, set}

I have spent a lot of time developing and improving it robin_hood, and it works quite well for most use cases. I won't make any updates to this code any more, unless they are PRs for critical bug fixes.

Travis CI Build Status Appveyor Build Status Codacy Badge Total alerts Language grade: C/C++ Coverage Status

robin_hood::unordered_map and robin_hood::unordered_set is a platform independent replacement for std::unordered_map / std::unordered_set which is both faster and more memory efficient for real-world use cases.

Installation & Usage

Direct Inclusion

  1. Add robin_hood.h to your C++ project.
  2. Use robin_hood::unordered_map instead of std::unordered_map
  3. Use robin_hood::unordered_set instead of std::unordered_set

Conan, the C/C++ Package Manager

  1. Setup your CMakeLists.txt (see Conan documentation on how to use MSBuild, Meson and others) like this:
    project(myproject CXX)
    add_executable(${PROJECT_NAME} main.cpp)
    include(${CMAKE_BINARY_DIR}/conanbuildinfo.cmake) # Include Conan-generated file
    conan_basic_setup(TARGETS) # Introduce Conan-generated targets
    target_link_libraries(${PROJECT_NAME} CONAN_PKG::robin-hood-hashing)
  2. Create conanfile.txt in your source dir (don't forget to update the version)
  3. Install and run Conan, then build your project as always:
    pip install conan
    mkdir build
    cd build
    conan install ../ --build=missing
    cmake ../
    cmake --build .
    The robin-hood-hashing package in Conan is kept up to date by Conan contributors. If the version is out of date, please create an issue or pull request on the conan-center-index repository.


Please see extensive benchmarks at Hashmaps Benchmarks. In short: robin_hood is always among the fastest maps and uses far less memory than std::unordered_map.

Design Choices

  • Two memory layouts. Data is either stored in a flat array, or with node indirection. Access for unordered_flat_map is extremely fast due to no indirection, but references to elements are not stable. It also causes allocation spikes when the map resizes, and will need plenty of memory for large objects. Node based map has stable references & pointers (NOT iterators! Similar to std::unordered_map) and uses const Key in the pair. It is a bit slower due to indirection. The choice is yours; you can either use robin_hood::unordered_flat_map or robin_hood::unordered_node_map directly. If you use robin_hood::unordered_map It tries to choose the layout that seems appropriate for your data.

  • Custom allocator. Node based representation has a custom bulk allocator that tries to make few memory allocations. All allocated memory is reused, so there won't be any allocation spikes. It's very fast as well.

  • Optimized hash. robin_hood::hash has custom implementations for integer types and for std::string that are very fast and falls back to std::hash for everything else.

  • Depends on good Hashing. For a really bad hash the performance will not only degrade like in std::unordered_map, the map will simply fail with an std::overflow_error. In practice, when using the standard robin_hood::hash, I have never seen this happening.


Licensed under the MIT License. See the LICENSE file for details.

by martinus

Popular Hashing Projects
Popular Hash Projects
Popular Computer Science Categories
Related Searches

Get A Weekly Email With Trending Projects For These Categories
No Spam. Unsubscribe easily at any time.
C Plus Plus
Header Only
Single File