hopscotch map
v2.3.1
hopscotch-map 라이브러리는 충돌을 해결하기 위해 개방형 주소 지정 및 hopscotch 해싱을 사용하는 빠른 해시 맵 및 해시 세트의 C++ 구현입니다. 대부분의 경우 std::unordered_map 보다 더 나은 성능을 제공하는 캐시 친화적인 데이터 구조이며 더 적은 메모리를 사용하고 더 많은 기능을 제공하는 동시에 google::dense_hash_map 과 매우 유사합니다.
라이브러리는 tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map 및 tsl::hopscotch_pg_set 과 같은 기본 클래스를 제공합니다. 처음 두 개는 더 빠르며 두 가지 성장 정책의 거듭제곱을 사용하고, 마지막 두 개는 대신 프라임 성장 정책을 사용하며 열악한 해시 함수에 더 잘 대처할 수 있습니다. 해시의 하위 비트에서 패턴이 반복될 가능성이 있는 경우 프라임 버전을 사용하십시오(예: ID 해시 함수로 포인터를 저장하는 경우). 자세한 내용은 성장정책을 참조하세요.
이러한 클래스 외에도 라이브러리는 tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map 및 tsl::bhopscotch_pg_set 제공합니다. 이러한 클래스에는 키에 대한 추가 요구 사항이 있습니다. 이는 LessThanComparable 이어야 하지만 더 나은 점근 상한을 제공합니다. 자세한 내용은 예제를 참조하세요. 그럼에도 불구하고 특정 요구 사항(해시 DoS 공격 위험)이 없는 경우 tsl::hopscotch_map 및 tsl::hopscotch_set 대부분의 경우 충분하며 일반적으로 성능이 더 좋으므로 기본 선택이 되어야 합니다.
홉스카치 해싱의 개요와 일부 구현 세부 정보는 여기에서 확인할 수 있습니다.
다른 해시 맵에 대한 tsl::hopscotch_map 의 벤치마크는 여기에서 찾을 수 있습니다. 이 페이지는 또한 사용 사례에 맞게 시도해야 하는 해시 테이블 구조에 대한 몇 가지 조언을 제공합니다( tsl 네임스페이스의 여러 해시 테이블 구현으로 인해 약간의 어려움을 겪는 경우 유용함).
tsl::hopscotch_map 대상을 사용할 수도 있습니다.Key 와 다른 유형의 find 사용을 허용하는 이종 조회 지원(예: std::unique_ptr<foo> 키로 사용하는 맵이 있는 경우 foo* 또는 std::uintptr_t 키 매개변수로 사용할 수 있음) std::unique_ptr<foo> 구성하지 않고 find (예제 참조).precalculated_hash 매개변수 참조).tsl::bhopscotch_map 및 tsl::bhopscotch_set 조회 및 삭제 시 최악의 경우 O(log n)를 제공하여 이러한 클래스가 해시 테이블 DoS(서비스 거부) 공격에 저항하도록 합니다(예제의 세부 정보 참조).-fno-exceptions 옵션을 통해, MSVC의 /EH 옵션 없이 또는 단순히 TSL_NO_EXCEPTIONS 정의를 통해). std::terminate 예외가 비활성화된 경우 throw 명령어를 대체하는 데 사용됩니다.std::unordered_map 및 std::unordered_set 와 매우 유사한 API입니다.std::unordered_map 과의 차이점 tsl::hopscotch_map std::unordered_map 과 유사한 인터페이스를 가지려고 시도하지만 몇 가지 차이점이 있습니다.
erase 제외하고 해시 테이블을 수정하는 모든 작업은 모든 반복자를 무효화합니다(자세한 내용은 API 참조).operator*() 및 operator->() std::pair< std::pair<const Key, T> const std::pair<Key, T> std::pair<Key, T>에 대한 참조와 포인터를 반환하므로 T 값을 수정할 수 없게 됩니다. 값을 수정하려면 반복자의 value() 메서드를 호출하여 변경 가능한 참조를 가져와야 합니다. 예: tsl::hopscotch_map< int , int > map = {{ 1 , 1 }, { 2 , 1 }, { 3 , 1 }};
for ( auto it = map.begin(); it != map.end(); ++it) {
// it->second = 2; // Illegal
it. value () = 2 ; // Ok
}bucket_size , bucket , ...)는 지원되지 않습니다. 이러한 차이점은 std::unordered_set 과 tsl::hopscotch_set 사이에도 적용됩니다.
스레드 안전성 및 예외 보장은 std::unordered_map/set 와 동일합니다(즉, 작성기 없이 여러 판독기를 가질 수 있음).
라이브러리는 GrowthPolicy 템플릿 매개변수를 통해 여러 성장 정책을 지원합니다. 라이브러리에서는 세 가지 정책을 제공하지만 필요한 경우 자체 정책을 쉽게 구현할 수 있습니다.
tsl::(b)hopscotch_map/set 에서 사용하는 기본 정책입니다. 이 정책은 해시 테이블의 버킷 배열 크기를 2의 거듭제곱으로 유지합니다. 이 제약 조건을 통해 정책은 해시를 버킷에 매핑하기 위해 느린 모듈로 작업을 사용하지 않고 hash % 2 n 대신 hash & (2 n - 1) 사용합니다(빠른 모듈로 참조). 빠르지만 2의 거듭제곱을 갖는 모듈로는 결국 가장 중요한 비트만 마스크하므로 잘못된 해시 함수로 인해 많은 충돌이 발생할 수 있습니다.tsl::(b)hopscotch_pg_map/set 에서 사용하는 기본 정책입니다. 정책은 해시 테이블의 버킷 배열 크기를 소수로 유지합니다. 해시를 버킷에 매핑할 때 소수를 모듈로로 사용하면 해시 함수가 좋지 않더라도 버킷 전체에 해시가 더 잘 분산됩니다. 컴파일러가 모듈로 연산을 최적화할 수 있도록 정책은 상수 소수 모듈로가 있는 조회 테이블을 사용합니다(자세한 내용은 API 참조). tsl::hh::power_of_two_growth_policy 보다 느리지만 더 안전합니다. 성능이 좋지 않은 경우 overflow_size() 확인하세요. 0이 아니면 해시 충돌이 많이 발생할 수 있습니다. 더 균일한 것으로 해시 함수를 변경하거나 다른 성장 정책(주로 tsl::hh::prime_growth_policy )을 시도하십시오. 불행하게도 때로는 충돌로부터 자신을 보호하는 것이 어렵습니다(예: 해시 맵에 대한 DoS 공격). 필요한 경우 O(n) 대신 조회 시 O(log n)의 최악의 시나리오를 제공하는 tsl::bhopscotch_map/set 도 확인하세요. 자세한 내용은 예를 참조하세요.
자체 정책을 구현하려면 다음 인터페이스를 구현해야 합니다.
struct custom_policy {
// Called on hash table construction and rehash, min_bucket_count_in_out is the minimum buckets
// that the hash table needs. The policy can change it to a higher number of buckets if needed
// and the hash table will use this value as bucket count. If 0 bucket is asked, then the value
// must stay at 0.
explicit custom_policy (std:: size_t & min_bucket_count_in_out);
// Return the bucket [0, bucket_count()) to which the hash belongs.
// If bucket_count() is 0, it must always return 0.
std:: size_t bucket_for_hash (std:: size_t hash) const noexcept ;
// Return the number of buckets that should be used on next growth
std:: size_t next_bucket_count () const ;
// Maximum number of buckets supported by the policy
std:: size_t max_bucket_count () const ;
// Reset the growth policy as if the policy was created with a bucket count of 0.
// After a clear, the policy must always return 0 when bucket_for_hash() is called.
void clear () noexcept ;
}hopscotch-map을 사용하려면 포함 경로에 포함 디렉터리를 추가하기만 하면 됩니다. 헤더 전용 라이브러리입니다.
CMake를 사용하는 경우 target_link_libraries 와 함께 CMakeLists.txt에서 내보낸 tsl::hopscotch_map 대상을 사용할 수도 있습니다.
# Example where the hopscotch-map project is stored in a third-party directory
add_subdirectory (third-party/hopscotch-map)
target_link_libraries (your_target PRIVATE tsl::hopscotch_map) make install 통해 프로젝트가 설치된 경우 add_subdirectory 대신 find_package(tsl-hopscotch-map REQUIRED) 사용할 수도 있습니다.
코드는 모든 C++17 표준 호환 컴파일러에서 작동해야 합니다.
테스트를 실행하려면 Boost Test 라이브러리와 CMake가 필요합니다.
git clone https://github.com/Tessil/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests API는 여기에서 찾을 수 있습니다.
모든 메소드는 아직 문서화되어 있지 않지만 달리 지정하는 경우를 제외하고 std::unordered_map 및 std::unordered_set 의 동작을 복제합니다.
# include < cstdint >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
# include < tsl/hopscotch_set.h >
int main () {
tsl::hopscotch_map<std::string, int > map = {{ " a " , 1 }, { " b " , 2 }};
map[ " c " ] = 3 ;
map[ " d " ] = 4 ;
map. insert ({ " e " , 5 });
map. erase ( " b " );
for ( auto it = map. begin (); it != map. end (); ++it) {
// it->second += 2; // Not valid.
it. value () += 2 ;
}
// {d, 6} {a, 3} {e, 7} {c, 5}
for ( const auto & key_value : map) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
if (map. find ( " a " ) != map. end ()) {
std::cout << " Found " a " . " << std::endl;
}
const std:: size_t precalculated_hash = std::hash<std::string>()( " a " );
// If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
if (map. find ( " a " , precalculated_hash) != map. end ()) {
std::cout << " Found " a " with hash " << precalculated_hash << " . " << std::endl;
}
/*
* Calculating the hash and comparing two std::string may be slow.
* We can store the hash of each std::string in the hash map to make
* the inserts and lookups faster by setting StoreHash to true.
*/
tsl::hopscotch_map<std::string, int , std::hash<std::string>,
std::equal_to<std::string>,
std::allocator<std::pair<std::string, int >>,
30 , true > map2;
map2[ " a " ] = 1 ;
map2[ " b " ] = 2 ;
// {a, 1} {b, 2}
for ( const auto & key_value : map2) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
tsl::hopscotch_set< int > set;
set. insert ({ 1 , 9 , 0 });
set. insert ({ 2 , - 1 , 9 });
// {0} {1} {2} {9} {-1}
for ( const auto & key : set) {
std::cout << " { " << key << " } " << std::endl;
}
} 이기종 오버로드를 사용하면 사용된 유형이 해시 가능하고 Key 와 비교할 수 있는 한 조회 및 삭제 작업에 Key 이외의 다른 유형을 사용할 수 있습니다.
tsl::hopscotch_map/set 에서 이기종 오버로드를 활성화하려면 정규 ID KeyEqual::is_transparent 유효해야 합니다. std::map::find 와 동일한 방식으로 작동합니다. std::equal_to<> 사용하거나 자신만의 함수 객체를 정의할 수 있습니다.
KeyEqual 과 Hash 모두 서로 다른 유형을 처리할 수 있어야 합니다.
# include < functional >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
struct employee {
employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
}
// Either we include the comparators in the class and we use `std::equal_to<>`...
friend bool operator ==( const employee& empl, int empl_id) {
return empl. m_id == empl_id;
}
friend bool operator ==( int empl_id, const employee& empl) {
return empl_id == empl. m_id ;
}
friend bool operator ==( const employee& empl1, const employee& empl2) {
return empl1. m_id == empl2. m_id ;
}
int m_id;
std::string m_name;
};
// ... or we implement a separate class to compare employees.
struct equal_employee {
using is_transparent = void ;
bool operator ()( const employee& empl, int empl_id) const {
return empl. m_id == empl_id;
}
bool operator ()( int empl_id, const employee& empl) const {
return empl_id == empl. m_id ;
}
bool operator ()( const employee& empl1, const employee& empl2) const {
return empl1. m_id == empl2. m_id ;
}
};
struct hash_employee {
std:: size_t operator ()( const employee& empl) const {
return std::hash< int >()(empl. m_id );
}
std:: size_t operator ()( int id) const {
return std::hash< int >()(id);
}
};
int main () {
// Use std::equal_to<> which will automatically deduce and forward the parameters
tsl::hopscotch_map<employee, int , hash_employee, std::equal_to<>> map;
map. insert ({ employee ( 1 , " John Doe " ), 2001 });
map. insert ({ employee ( 2 , " Jane Doe " ), 2002 });
map. insert ({ employee ( 3 , " John Smith " ), 2003 });
// John Smith 2003
auto it = map. find ( 3 );
if (it != map. end ()) {
std::cout << it-> first . m_name << " " << it-> second << std::endl;
}
map. erase ( 1 );
// Use a custom KeyEqual which has an is_transparent member type
tsl::hopscotch_map<employee, int , hash_employee, equal_employee> map2;
map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });
// 2004
std::cout << map2. at ( 4 ) << std::endl;
} tsl::hopscotch_map 및 tsl::hopscotch_set 외에도 라이브러리는 두 가지 "보안" 옵션인 tsl::bhopscotch_map 및 tsl::bhopscotch_set (모두 해당 pg 대응 항목 포함)를 제공합니다.
이 두 가지 추가에는 조회 및 삭제에 대한 최악의 점근적 복잡성 O(log n)과 삽입에 대한 상각된 최악의 경우 O(log n)가 있습니다(O(n)에 있을 재해시 가능성으로 인해 상각됨) . 해시 함수가 모든 요소를 동일한 버킷에 매핑하더라도 O(log n)은 여전히 유지됩니다.
이는 해시 테이블 DoS(서비스 거부) 공격에 대한 보안을 제공합니다.
이를 달성하기 위해 보안 버전은 오버플로된 요소에 대해 이진 검색 트리를 사용하므로(구현 세부 정보 참조) 요소가 LessThanComparable 이어야 합니다. 추가 Compare 템플릿 매개변수가 필요합니다.
# include < chrono >
# include < cstdint >
# include < iostream >
# include < tsl/hopscotch_map.h >
# include < tsl/bhopscotch_map.h >
/*
* Poor hash function which always returns 1 to simulate
* a Deny of Service attack.
*/
struct dos_attack_simulation_hash {
std:: size_t operator ()( int id) const {
return 1 ;
}
};
int main () {
/*
* Slow due to the hash function, insertions are done in O(n).
*/
tsl::hopscotch_map< int , int , dos_attack_simulation_hash> map;
auto start = std::chrono::high_resolution_clock::now ();
for ( int i= 0 ; i < 10000 ; i++) {
map. insert ({i, 0 });
}
auto end = std::chrono::high_resolution_clock::now ();
// 110 ms
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
std::cout << duration. count () << " ms " << std::endl;
/*
* Faster. Even with the poor hash function, insertions end-up to
* be O(log n) in average (and O(n) when a rehash occurs).
*/
tsl::bhopscotch_map< int , int , dos_attack_simulation_hash> map_secure;
start = std::chrono::high_resolution_clock::now ();
for ( int i= 0 ; i < 10000 ; i++) {
map_secure. insert ({i, 0 });
}
end = std::chrono::high_resolution_clock::now ();
// 2 ms
duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
std::cout << duration. count () << " ms " << std::endl;
} 코드는 MIT 라이선스에 따라 라이선스가 부여됩니다. 자세한 내용은 LICENSE 파일을 참조하세요.
