해시

해시

정의와 성질

• 해시에서는 insert, erase, find, update 모두 O(1)
• 해시 함수: 임의의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수

  충돌

• 서로 다른 키가 같은 해시 값을 가질 경우 충돌이 일어남
• 충돌이 발생했을 때 회피 방안은 Chaining과 Open Addressing

  Chaining

• 각 인덱스마다 연결 리스트를 둬서 충돌 회피를 하는 방법
• STL에 있는 해시 자료구조는 Chaining을 사용
• 이상적인 상황에서는 O(1)이지만 충돌이 빈번할수록 성능이 저하되고 모든 키의 해시 값이 같으면 O(N)이 됨
• 각 키의 해시 값이 최대한 균등하게 퍼져야 성능이 좋아지기 때문에 좋은 해시 함수를 정해야 함

  Open Addressing

• 각 인덱스에 바로 (키,값)쌍을 씀
• 해당 칸에 값이 있는 경우 그 다음 칸에 저장
• 삭제를 할 때 그냥 값을 날려서 빈 칸을 만들지 않고 해당 칸에 쓰레기 값을 두던가 별도의 배열 두어서 해당 칸이 빈 칸이 아니라 원래 값이 있었지만 제거된 상태임을 명시함

  Linear Probing

• 충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식
• 장점: Cache hit rate가 높음
• 단점: Clustering이 생겨 성능에 영향을 줄 수 있음

  Quadratic Probing

• 충돌 발생 시 오른쪽으로 1,3,5,…칸씩 이동하는 방식
• 처음 위치 기준으로 1,4,9…칸씩 이동하기 때문에(제곱방식)
• 장점: Cache hit rate가 나쁘지 않고 Clustering을 어느 정도 회피할 수 있음
• 단점: 해시 값이 같을 경우 여전히 Clustering이 발생함

  Double Hashing

• 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식
• 장점: Clustering을 효과적으로 회피할 수 있음
• 단점: Cache hit rate가 낮음

  STL

• unordered_set

  #include<iostream>
  #include<unordered_set>
  using namespace std;
  int main(void){
    unordered_set<int> s;
    s.insert(-10);
    s.insert(100);
    s.insert(15);
    //{-10,100,15}
    s.insert(-10); // 중복을 허용하지 않기 때문에 변화 없음
    //{-10,100,15}
    cout<<s.erase(100)<<'\n';//출력:1 {-10,15}
    cout<<s.erase(20)<<'\n';//출력:0 {-10,15}
    if(s.find(15)!=s.end()){
        cout<<"yes\n";
    }
    cout<<s.size()<<'\n'; // 2
    cout<<s.count(50)<<'\n'; //0
    for(auto e:s){//해시의 특성상 원소들이 크기 순서 혹은 삽입한 순서로 위치해 있지 않음
        cout<<e<<' ';
    }
    cout<<'\n';
    return 0;
  }
  

• unordered_multiset

  #include<iostream>
  #include<unordered_set>
  using namespace std;
  int main(void){
    unordered_multiset<int> ms;
    ms.insert(-10);
    ms.insert(100);
    ms.insert(15);// {-10,100,15}
    ms.insert(-10);
    ms.insert(15);// {-10,-10,100,15,15}
    cout<<ms.size()<<'\n';// 5
    for(auto e : ms){
        cout<<e<<' ';
    }
    cout<<'\n';
    cout<<ms.erase(15)<<'\n'; //출력: 2 {-10,-10,100} 하나만 지워지지 않고 모든 15가 지워짐
    ms.erase(ms.find(-10)); //{-10,100}
    ms.insert(100); //{-10,100,100}
    cout<<ms.count(100)<<'\n';// 2
    return 0;
  }
  

• unordered_map

  #include<iostream>
  #include<unordered_map>
  using namespace std;
  int main(void){
    unordered_map<string,int> m;
    m["hi"]=123;
    m["bird"]=1000;
    m["gogo"]=165; // {"hi",123},{"bird",1000},{"gogo",165}
    cout<<m.size()<<'\n'; //3
    m["hi"]=-7; // {"hi",-7},{"bird",1000},{"gogo",165} 중복키를 허용하지 않음
    if(m.find("hi")!=m.end()){
        cout<<"yes\n";
    }
    else{
        cout<<"no\n";
    }
    m.erase("bird"); //{"hi",-7},{"gogo",165}
    for(auto e:m){ //{"hi",-7},{"gogo",165}
        cout<<e.first<<' '<<e.second<<'\n';
    }
    return 0;
  }