std :: unordered_set에 대해 std :: hash 함수로 대소 문자를 구분하지 않는 이유는 무엇입니까?

Question

내가 가진 질문은 대소 문자를 구분하지 않는 std :: unordered_set을 사용하는 것이 아니라 오히려 어떻게 작동 하는가?

#include "stdafx.h" 
#include <string> 
#include <iostream> 
#include <unordered_set> 
#include "boost/algorithm/string.hpp" 


struct case_insensitive_comparer 
{ 
    bool operator() (const std::string& x, const std::string& y) const 
    { 
     return boost::iequals(x, y); 
    } 
}; 

using case_insensitive_set = std::unordered_set<std::string, std::hash<std::string>, case_insensitive_comparer>; 

std::vector<std::string> permute_case(const std::string& s) 
{ 
    std::vector<std::string> strs; 

    // Iterate through all bitmasks, 1 for uppercase, 0 for lowercase 
    int msb = 1 << (s.length() - 1); 
    int upper = 1 << s.length(); 
    std::locale loc; 
    for (int i = 0; i < upper; i++) 
    { 
     int bit = msb; 
     std::string current = ""; 
     for (size_t j = 0; j < s.length(); j++, bit >>= 1) 
      current += (bit & i) ? std::toupper(s[j], loc) : std::tolower(s[j], loc); 

     strs.push_back(current); 
    } 

    return strs; 
} 

int main() 
{ 
    std::vector<std::string> strs = permute_case("awesome"); 

    case_insensitive_set set(strs.begin(), strs.end()); 

    // Check the hash 
    for (auto& s : strs) 
     std::cout << s << " :" << std::hash<std::string>()(s) << "\n"; 

    // Check the element 
    for (auto& s : set) 
     std::cout << s << "\n"; 

    return 0; 
} 

그래서 나는 std::unordered_set에 대한 문자열 대소 문자를 구별 비교 자 및 해시 함수로 std::hash<std::string>를 사용합니다. 해시 세트에 대한 기본적인 이해 (나는 unordered_set이 해시 세트와 같다고 가정합니다)는 키의 해시를 계산하여 아직 존재하지 않는다면 세트에 넣습니다. 그리고 비교자인 Pred는 집합이 키를 삽입하려고 할 때 해시 충돌이있을 때 키가 같거나 다른지를 결정해야합니다.

코드를 기반으로하면 관계없이 작동하므로 내 가정 일부가 올바르지 않습니다. 누군가 내 가정이 잘못되었다고 말하면 도움이 될 것입니다.

감사합니다.

편집 :이 경우 대소 문자를 구분하지 않아도된다고 생각합니다. unordered_set은 1 개의 키만 삽입하면됩니다. 관찰 한 경우입니다. 즉, AWESOME 만 표시됩니다. 그래서 제 경우에는 작동하는 것으로 생각했지만 kennym의 대답으로 모든 키가 같은 버켓에있게되어 운이 좋았습니다. 실제로 MSVC를 사용하여 코드를 컴파일합니다.

Answer 1

hash table이 어떻게 작동하는지 생각해 봅시다. 용량 N와

1. 해시 테이블 버킷 배열이다. 버킷은 일반적으로 연결된 목록 또는 이진 검색 트리입니다. 개념적으로는

   template <typename T> 
   class HashTable { 
       std::vector<std::forward_list<T>> _buckets; 
   
   public: 
       HashTable(size_t capacity = 16) : _buckets(capacity) {} 
       size_t bucket_count() const { return _buckets.size(); } 
   

2. 모든 키 K ∈ T는 해시 테이블의 버킷에 삽입 할 수있는 해시 테이블을 생각할 수 있습니다. 선택되는 버킷 키 K와 용량 입력으로 N을 취하는 함수 bucket_index 의해 결정 키가 속해야 버킷 배열 인덱스 0 ≤ I < N를 생성한다 .

   void insert(T&& key) { 
        // locate the bucket. 
        size_t i = bucket_index(key, bucket_count()); 
        auto& bucket = _buckets[i]; 
        // ensure the key does not already exist in the bucket 
        if (std::find(bucket.cbegin(), bucket.cend(), key) == bucket.cend()) { 
         // now insert the key into the bucket. 
         bucket.push_front(std::move(key)); 
        } 
       } 
   

3. bucket_index 기능은 일반적으로 해시 함수의 관점에서 구현하고 용량 계수 가지고있다 : 두 개의 키 : 그것은 std::hash<T>()(key)를 직접 사용하지 않는

   private: 
       static size_t bucket_index(const T& key, size_t cap) { 
        return std::hash<T>()(key) % cap; 
       } 
   }; 
   

   주 hash % cap이 같을 때 동일한 버킷을 참조합니다.영업 이익의 코드가 MSVC에서 작동하는 것처럼 보일 이유

---

는 그리고이입니다. MSVC의 unordered_set 구현에서 초기 용량은 8입니다. 그리고, 당신 print the hash as hexadecimal 경우, 마지막 자리는 항상 c입니다 알 수 있습니다 :

AWESOME :7552acc94fd16a5c 
AWESOMe :75528cc94fd133fc 
AWESOmE :75bf6cc9502dcf7c 
AWESOme :75bf8cc9502e05dc 
AWESoME :60234cc8b2d194fc 
... 
awesOme :976734d757ba79dc 
awesoME :81caf4d6ba5e08fc 
awesoMe :81cb14d6ba5e3f5c 
awesomE :815e34d6ba01a3dc 
awesome :815e14d6ba016d7c 

따라서, hash % 8 항상 4 될 것, 즉 팔 중 같은 버킷은 모두 128 키에 의해 선택됩니다. 우리가 양동이를 선택한 후에 무슨 일이 일어 났는지 기억해? 우리는 링크 된 목록에 키가 이미 존재하는지 확인합니다. 이것은 항상 참이므로 첫 번째 키만 "굉장합니다"만 표시됩니다. 정말로 일어나는 것은 단지 MSVC의 해시 함수는 매우 낮은 품질을 가지고있는 동안

AWESOME 

이

, 그냥 == 작품을 교체 환상을 제공합니다.

---

OP 코드가 "작동하지 않음"을 보여주기 위해 다른 표준 라이브러리로 전환 해 봅시다. libC++에 clang을 사용하면 다음 결과를 얻을 수 있습니다.

AWESOME :1a285ecfc4bab378 
AWESOMe :acb9b7f4f69b16e2 
AWESOmE :fd66d9186a434601 
AWESOme :254b008bd66d1e29 
AWESoME :27cac8154bb934d0 
... 
awesOme :a4e8c2140834341e 
awesoME :cfd12a83da4a4b0f 
awesoMe :b4c4eb4c60968581 
awesomE :bdca27cd606f4f42 
awesome :14ddc089ab5badb5 

libC++의 해시는 상당히 균등하게 배포됩니다. libc의 ++의 unordered_set의 초기 용량은 2, 두 양동이 가득, 그래서 세트는 두 가지 요소가 있습니다

AWESOmE 
AWESOME 

및 영업 이익의 코드는 일반적으로 작동하지 않습니다.

---

주

: 여기에 내가 해시 충돌이 별도의 체인에 의해 처리되고 == 항상 true를 반환하기 때문에이 두 그림을 입력하지 않습니다하지만 더 동적 크기 조정이 없다 생각했습니다.

Answer 2

문제는 대소 문자를 구분하는 대소 문자와 대소 문자를 구분하지 않는 비교자를 사용한다는 것입니다. 만약 당신이 대소 문자를 구분하지 않는다면 당신은 하나의 엔트리를 얻을 것이다. 예를 들어

: 출력은 단지 굉장이 포함됩니다

#include <boost/algorithm/string/case_conv.hpp> 

struct case_insensitive_hasher 
{ 
    size_t operator()(const std::string& key) const 
    { 
     std::string keyCopy(key); 
     boost::to_lower(keyCopy); 
     return std::hash<std::string>()(keyCopy); 
    } 
}; 

using case_insensitive_set = std::unordered_set<std::string, case_insensitive_hasher, case_insensitive_comparer>; 

, 첫 번째 항목이 삽입.