[C++/코테] 해시 - 개념, 백준 예제

정의와 성질

해시: 키에 대응되는 값을 저장하는 자료구조

insert, erase, find, update의 연산을 $O(N)$에 활용할 수 있다.

 

해시함수: 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수

마치 카드 번호 16자리에서 뒷 4자리만 배열의 인덱스로 쓴 것과 같다.

충돌: 서로 다른 키가 같은 해시 값을 가지게 될 경우 발생하는 문제

ex) 5135에 Kim이 저장되어 있을 때, Kim이 0000 0000 0000 5135에 대응되는 Kim인지 9999 9999 9999 5135에 대응되는 Kim인지 알 수 없다.

해시 함수의 정의 상, 충돌 발생을 막을 수는 없지만 회피 방안이 있다. Chaning과 Open Addressing이 방안이다.

충돌회피1 - Chaning

각 인덱스마다 연결 리스트 (또는 C++ vector등의 동적 배열) 를 둬서 충돌 회피를 하는 방법.

최악의 경우 $O(N)$ 소요되므로 각 키의 해시 값이 최대한 균등하게 퍼져야 성능이 좋아진다.

 

충돌회피2 - Open addressing

각 인덱스에 바로 (키, 값) 쌍을 쓴다.

특정 값을 삽입하고자 할 때, 채워져 있으면 다음 칸으로 넘어간다.

erase 의 경우, 값을 지우는 것이 아니라 쓰레기 값 등으로 채워 원래 값이 있었지만 제거된 상태임을 명시해야 한다.

 

1) Linear Probing

충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식.

장점: Cache hit rate가 높다. 계속 인접한 영역의 배열 칸을 확인하기 때문.

단점: Clustering이 생겨 성능이 영향을 줄 수 있다.

2) Quadratic Probing

충돌이 발생하면 오른쪽으로 1, 3, 5, ... 칸 이동하는 방법

장점: Cache hit rate가 나쁘지 않고, Clustering을 어느 정도 회피할 수 있다.

단점: 해시 값이 같을 경우 여전히 Clustering이 발생한다.

3) Double hashing

충돌이 발생 시 이동할 칸의 수를 새로운 해시 함수의 값으로 계산하는 방식.

장점: Clustering을 효과적으로 회피할 수 있다.

단점: Cache hit rate가 낮다.

STL

#include <bits/stdc++.h>
using namespace std;

void unordered_set_example(){
  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'; // {-10, 15}, 1
  cout << s.erase(20) << '\n'; // {-10, 15}, 0
  
  if(s.find(15) != s.end()) cout << "15 in s\n";
  else cout << "15 not in s\n";
  
  cout << s.size() << '\n'; // 2
  cout << s.count(50) << '\n'; // 0
  
  for(auto e : s) cout << e << ' ';	// 해시 특성 상 순서는 뒤죽박죽임
  cout << '\n';
}

• 데이터를 unordered_set에 추가하고, 확인하고, 지운다.
• 선언 시 자료형도 함께 지정한다. 위 예제는 int 자료형에 대한 unordered_set이다.
• 삽입 시 중복을 허용하지 않는다.

void unordered_multiset_example(){
  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'; // {-10, -10, 100}, 2
  ms.erase(ms.find(-10)); // {-10, 100}
  
  ms.insert(100); // {-10, 100, 100}
  cout << ms.count(100) << '\n'; // 2
}

• erase를 주의해야 한다. 특정 값 erase시, 그 값 전부 지워지기 때문.
  하나만 지우고 싶을 때는 mr.erase(ms.find(-10)) 과 같이 인덱스를 전달해서 지워야 한다.

void unordered_map_example(){
  unordered_map<string, int> m;
  m["hi"] = 123;
  m["bkd"] = 1000;
  m["gogo"] = 165; // ("hi", 123), ("bkd", 1000), ("gogo", 165)
  cout << m.size() << '\n'; // 3
  
  m["hi"] = -7;  // ("hi", -7), ("bkd", 1000), ("gogo", 165)
  
  if(m.find("hi") != m.end()) cout << "hi in m\n";
  else cout << "hi not in m\n";
  
  m.erase("bkd"); // ("hi", 123), ("gogo", 165)
  
  for(auto e : m)
    cout << e.first << ' ' << e.second << '\n';
}

• unordered_map은 마치 배열인데, 인덱스가 숫자 뿐 아니라 string, 큰 정수나 음수도 담을 수 있는 느낌으로 사용된다.
• unordered_map은 키 중복이 허용되지 않지만, unordered_multimap 은 중복 키를 허용한다. (딱히 유용하진 않음)

연습 문제

백준 7785번: 회사에 있는 사람 https://www.acmicpc.net/problem/7785

✔️ 정렬과 이분 탐색, 또는 투 포인터로 접근할 수도 있다.

✔️ STL 해시를 사용해서 'enter'가 입력되면 insert, 'leave'가 입력되면 erase를 해준다.

7785번: 회사에 있는 사람

백준 1620번: 나는야 포켓몬 마스터 이다솜 https://www.acmicpc.net/problem/1620

✔️ STL의 unordered_map을 사용한다.

✔️ 이름이 입력되었을 때 번호를 답하는 것은 이분탐색으로도 해결이 가능하다.

1620번: 나는야 포켓몬 마스터 이다솜

 

 

구현

tbc..

 

---

출처: https://blog.encrypted.gg/1009

[실전 알고리즘] 0x15강 - 해시