[코드트리] Hash Set

SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다.

 

* 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용.

 

xxilliant 제작

unordered_set STL

C++에서는 unordered_set이라는 STL을 이용할 수 있습니다.

unordered_set은 HashSet 자료구조로 되어있으며, 이 HashSet이 바로 해싱을 기반으로 데이터들을 관리해주는 자료구조 입니다.

모든 함수의 시간복잡도는 O(1)입니다.

 

unordered_set은 set보다 속도가 빠르지만, 값의 존재 여부에만 관심이 있지 그 순서에는 전혀 관심이 없는 자료구조입니다.

 

#include <unordered_set> 헤더와, unordered_set<T> name; 형태의 선언이 필요합니다.

T는 type으로, unordered_set 안에 들어갈 원소의 타입을 적어줘야 합니다.

또, unordered_set은 원래 std::unordered_set으로 사용됩니다.

 

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<int> s;
    return 0;
}

 

unordered_set을 이용할 때 자주 사용되는 것은 다음 3가지 입니다. unordered_set<int> s;로 선언되어 사용될 때를 예로 설명해보겠습니다.

1. s.insert(E)

hashset에 데이터 E를 추가합니다.

 

1. s.erase(E)

현재 hashset에 들어있는 데이터 중 숫자 E를 찾아 제거합니다.

 

1. s.find(E)

현재 hashset에 숫자 E가 들어 있는지를 찾습니다. 있다면 해당 iterator를 반환하며, 없다면 s.end()값을 반환합니다. 따라서 값이 있다면 s.find(E) != s.end(), 없다면 s.find(E) == s.end()를 만족할 것입니다.

 

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<int> s;      // 정수를 관리할 hashset을 선언합니다. => 빈 set
    s.insert(3); 
    s.insert(9);
    s.insert(5);
    
    if(s.find(3) != s.end()) { // 숫자 3이 set에 있다면
        cout << "exists!" << endl;
    }

    s.erase(9);                   // 숫자 9를 제거합니다.
    if(s.find(9) == s.end()) { // 숫자 9가 hashset에 없다면
        cout << "not exists!" << endl;
    }

    return 0;
}

 

출처 코드트리