std :: unordered_set의 KeyEqual은 무엇입니까?

Question

세 번째 매개 변수 KeyEqual의 목적은 std::unordered_set에 무엇입니까? 해시 고유성이 충분하지 않습니까?

template< 
    class Key, 
    class Hash = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator<Key> 
> class unordered_set; 

이 질문이 순진하게 들리면 죄송합니다. 파이썬/PHP에서 C++로 옮기기 :)

현재로서는 KeyEqual의 구현은 항상 Hash impl을 복제합니다. 그래서 제대로했는지 궁금합니다.

Answer 1

하지만 해시 충돌이 발생하면 어떻게 될까요?

사진은 동일한 해시 값을 갖는 상이한 두 요소가 발생하는 경우를 보여준다. 결과적으로, 해시 값은 이 아닌 일 수 있습니다. 해시는 고유해야합니다.

---

에 따옴표 refstd::unordered_set의 :

는 내부적으로 unordered_set의 요소는 빠르게 액세스 할 수 있도록 모든 특정 순서로 정렬하지만, 자신의 해시에 값을 따라 버킷으로 구성되지 않습니다 직접적으로 평균 시간 복잡도가 일정한 에 의해 개별 요소에 직접 전달됩니다.

그래서 버킷에는 하나 이상의 요소가있을 수 있습니다! 이 두 요소는 동일한 해시 값을 가지며 고유 한 것으로 보장되지 않습니다!

---

독특한이 보장되는 유일한 것은 키입니다!

Answer 2

간단히 말해 집합은 두 개의 키가 같은지 여부를 알아야합니다. KeyEqual은이를 수행하기위한 메커니즘입니다.

동일한 값을 비교하지 않는 두 개의 키는 같은 값으로 해시 할 수 있으며 그 값을 확인해야합니다.

Answer 3

다른 값이 반드시 다른 해시를 가질 필요는 없습니다. 예를 들어 std::string 개의 개체가 실제로 무한하지만 실제로는 2^N std::size_t 개의 개체 만 있으므로이라는 결과가 나오므로 해시 충돌은 피할 수없는 경우가 있습니다.

따라서 std::unordered_set 및 std::unordered_map은 해시 값이 동일해도 요소가 동일하거나 동일하지 않은지 테스트하는 방법이 필요합니다.

Answer 4

그냥 간단 모드 % 작업을 수행하는 해시 함수, 예를 들면 int의 세트를 보자

struct IntMod { 
    constexpr std::size_t operator()(int i) const { return i % 10; } 
}; 

std::unordered_set<int, IntMod> s; 

이 쉽게 해시 충돌이 발생할 수 있습니다, 그것은 당신이 할 필요가 발생했을 때 키가 이미 존재 하는지를 알기 위해 키를 비교할 수 있습니다.

s.insert(25); // hash == 5 
s.insert(35); // hash == 5 
assert(*s.find(25) == 25); // both 25 and 35 are present despite the same hash 
assert(*s.find(35) == 35); 

우리는 단지뿐만 아니라 해시 함수를 사용 (당신이 기본적으로 할 제안처럼)는 제 2 삽입에 나누기 KeyEqual를 추가하는 경우.

struct IntEq { 
    constexpr bool operator()(int a, int b) const { 
    return IntMod{}(a) == IntMod{}(b); 
    } 
}; 

std::unordered_set<int, IntMod, IntEq> s; 
s.insert(25); // hash == 5 
s.insert(35); // hash == 5 
assert(*s.find(25) == 25); 
assert(*s.find(35) == 35); // now this fails. s.find(35) returns iterator to 25