robin hood hashing下載robin hood hashing源代碼下載

robin hood hashing

C/C++

3.11.5

下載

➵ROBIN_HOOD無序地圖和設置

注意：不幸的是，我沒有時間繼續開發此哈希圖。我有一個值得的繼任者，請前往： ankerl::unordered_dense::{map, set}

我花了很多時間來開發和改進robin_hood ，並且在大多數用例中都可以很好地工作。除非它們是關鍵錯誤修復的PR，否則我將不再對此代碼進行任何更新。

robin_hood::unordered_map and robin_hood::unordered_set是一個平台獨立替換std::unordered_map / std::unordered_set ，它既快速又更有效地記憶，用於現實世界中使用情況。

安裝和用法

直接包容

將robin_hood.h添加到您的C ++項目中。
使用robin_hood::unordered_map而不是std::unordered_map
使用robin_hood::unordered_set代替std::unordered_set

柯南，C/C ++軟件包管理器

設置您的CMakeLists.txt （請參閱有關如何使用MSBUILD，MESON等）的文檔：

 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)

在您的源代碼中創建conanfile.txt （別忘了更新版本）
```
 [requires]
robin-hood-hashing/3.11.5

[generators]
cmake
```
安裝和運行柯南，然後一如既往地構建您的項目：
```
pip install conan
mkdir build
cd build
conan install ../ --build=missing
cmake ../
cmake --build .
```
柯南（Conan）的貢獻者將robin-hood-hashing包裝在柯南（Conan）中保持最新狀態。如果該版本已過時，請在conan-center-index存儲庫上創建問題或提取請求。

基準

請在Hashmaps基準測試中查看廣泛的基準測試。簡而言之： robin_hood始終是最快的地圖之一，並且使用的內存要比std::unordered_map少得多。

設計選擇

兩個內存佈局。數據要么存儲在平面陣列中，要么在節點間接方面。由於沒有間接， unordered_flat_map的訪問非常快，但是對元素的引用不穩定。它還會導致地圖大小時會導致分配尖峰，並且需要大量的大對象內存。基於節點的映射具有穩定的引用和指針（不是迭代器！類似於std :: unordered_map），並在配對中使用const Key 。由於間接，這要慢一些。選擇是你的；您可以直接使用robin_hood::unordered_flat_map或robin_hood::unordered_node_map 。如果您使用robin_hood::unordered_map則嘗試選擇適合您數據的佈局。
自定義分配器。基於節點的表示形式具有自定義的散裝分配器，該分配器試圖進行很少的內存分配。所有分配的內存都重複使用，因此不會有任何分配峰值。也很快。
優化的哈希。 robin_hood::hash具有針對整數類型和std::string的自定義實現，這些實現非常快，可以回到std::hash for其他所有內容。
取決於良好的哈希。對於非常糟糕的哈希，性能不僅會像std::unordered_map中的降級，而且地圖將僅使用std::overflow_error失敗。在實踐中，使用標準robin_hood::hash時，我從未見過這種情況。