HashSet C++ 설명

Question

나는이 주제에 대해 배우지 않고 있습니다. 우리 수업에서는 우리 자신의 해시 세트 클래스를 구현하고 있습니다. 따라서 벡터 또는 배열과 같은 기본 데이터 구조가 있으며 해시 함수를 사용하여 요소가 집합에 있는지 여부를 빠르게 결정할 수 있습니다. 그것이 제가 따르지 않는 부분입니다. 이 결정에 해시 함수를 어떻게 사용합니까?

Answer 1

는 크기 100의 기본 배열을 상상하고는이 같은 0

99 일의 값을 삽입 할 수 있습니다 : 지금

class UselessHashMap 
{ 
public: 
    void insert(int value){ 
    _arr[hash(i)] = i; 
    } 
private: 
    int hash(int i) { return i }; 
    std::array<int,100> _arr; 
} 

, 당신은 100 개 이상을 저장할 상상 요소를 가지며 무한 (std :: numeric_limits :: max()) 크기를 갖는 배열을 가질 수 없습니다. 이 경우 해시 함수는 0-99 사이의 값을 반환해야하며, 물론 UselessHashMap 클래스도 충돌을 처리해야합니다. 왜냐하면이 함수는 다른 입력에 대해 동일한 값을 반환 할 수 있기 때문입니다.