rigtorp/HashMap được TopGit xếp vào nhóm dự án mã nguồn mở, với 224 sao trên GitHub, viết chủ yếu bằng C++. An open addressing linear probing hash table, tuned for delete heavy workloads
Tóm tắt dựng từ metadata GitHub của chính dự án — chưa có bài review TopGit. Trang sẽ tự động cập nhật khi bài review đầy đủ được xuất bản.
VÌ SAO CHƯA CÓ REVIEW
TopGit viết bài đầy đủ cho repo có nhiều sao nhất và được yêu cầu nhiều nhất. Trang này là snapshot trong thời gian chờ — xem README gốc ở tab READ ME.
A hash table mostly compatible with the C++11 std::unordered_map
interface, but with much higher performance for many workloads.
Implementation
This hash table uses open addressing with linear probing and
backshift deletion. Open addressing and linear probing minimizes
memory allocations and achieves high cache efficiency. Backshift deletion
keeps performance high for delete heavy workloads by not clobbering
the hash table with tombestones.
Usage
HashMap is mostly compatible with the C++11 container interface. The
main differences are:
A key value to represent the empty key is required.
Key and T needs to be default constructible.
Iterators are invalidated on all modifying operations.
It's invalid to perform any operations with the empty key.
The same target is available after add_subdirectory(path/to/HashMap).
Installation respects CMAKE_INSTALL_INCLUDEDIR and CMAKE_INSTALL_LIBDIR.
Benchmark
A benchmark src/HashMapBenchmark.cpp is included with the sources. The
benchmark simulates a delete heavy workload where items are repeatedly inserted
and deleted.
The benchmark uses std::chrono::steady_clock and requires no benchmark
framework or vendored dependencies. CMake enables comparisons against installed
Abseil and sparsehash when found. Set HASHMAP_BENCHMARK_WITH_ABSL=OFF or
HASHMAP_BENCHMARK_WITH_SPARSEHASH=OFF to disable either comparison. Abseil must
provide its CMake package; sparsehash must provide google/dense_hash_map.
No dependencies are downloaded during configuration.
The benchmark is built on Linux and macOS; Windows builds the example and tests.
All containers in a run use the same hash: hardware CRC32 on x86-64 and
MurmurHash3's fmix64 integer mixer on ARM and other architectures. Hash choices
differ across architectures, so compare containers within the same run.
I ran this benchmark on the following configuration:
AMD Ryzen 9 3900X
Linux 5.8.4-200.fc32.x86_64
gcc (GCC) 10.2.1 20200723 (Red Hat 10.2.1-1)
Isolated a core complex (CCX) using isolcpus for running the benchmark
When working set fits in L3 cache (HashMapBenchmark -c 100000 -i 100000000):
Implementation
mean ns/iter
max ns/iter
HashMap
24
1082
absl::flat_hash_map
24
2074
google::dense_hash_map
49
689846
std::unordered_map
67
10299
When working set is larger than L3 cache (HashMapBenchmark -c 10000000 -i 1000000000):
Trang TopGit này là một snapshot — tab "Readme" hiển thị nguyên văn README của repo (đã bỏ link, giữ ảnh). Repo GitHub ở github.com/rigtorp/HashMap là nguồn chính thức.
rigtorp/HashMap có phải mã nguồn mở không?
Có — rigtorp/HashMap phát hành theo license MIT, nghĩa là mã nguồn mở để đọc, fork và (tùy license) tái sử dụng. Mã: github.com/rigtorp/HashMap.
rigtorp/HashMap có website riêng không?
TopGit chưa ghi nhận URL trang chủ cho rigtorp/HashMap. Phần README ở tab phía trên thường có link demo, hoặc xem mô tả GitHub của repo.
rigtorp/HashMap dùng license gì?
rigtorp/HashMap phát hành theo license MIT. Nên mở file LICENSE trên GitHub để xác nhận — license metadata đôi khi lệch với thực tế dự án.
rigtorp/HashMap là gì?
rigtorp/HashMap (rigtorp/HashMap) là dự án C++ trên GitHub. Theo mô tả gốc: An open addressing linear probing hash table, tuned for delete heavy workloads
Đọc đầy đủ README ở tab phía trên.
Muốn nghe thêm một ý kiến về HashMap?
Hỏi một AI đọc được trang này — một cú bấm là có ngay nhận định về HashMap.