해시란?
해시 자료구조는 키에 대응되는 값을 저장하는 자료구조이다.
우리가 주민등록번호나 전화번호에 맞는 숫자와 이름의 쌍을 생성한다고, 예제를 두었을때, 특정 번호가 누구의 것인지를 알아내는 일을 할 때 쓰인다.
다음과 같이 전화번호가 존재한다고 예를 들었을 때, 모든 데이터를 배열에 삽입하여 관리할 수도 있다. 이렇게 하게 될때, 삽입 연산은 0(1) , 데이터를 찾는 과정을 수행할 시엔 0(N), 특정 데이터를 제거할 시엔 다시 O(N)의 시간이 소요된다.
그렇지만 해시 자료구조에선느 insert, erase, find, update 등의 연산이 모두 O(1)이다.
이와 같은 이유는 해시 함수는 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수의 역할을 수행하기 때문이다.
예를 들어, 32자리의 카드 번호가 존재한다고 가정했을때, 카드 32번의 자리를 모두 외우는것이 아닌 끝자리 4자리를 외워 각 카드번호가 누구의 것으로 존재하는지 판별하는것과 과정이 비슷하다고 생각하면 된다.
즉, 해시 자료구조는 키에 대응하는 값을 저장하는 자료구졸서, 키를 배열의 인덱스로 보내는 해시 함수를 두어 테이블로 관리하는것이 해시 자료구조이다.
윗 그림과 같은 테이블을 해시 테이블로 정의한다.
뒷 4자리를 저장하여, 키의 배열에 맞는 인덱스를 지정하여 해당되는 value 값을 찾기 때문에, insert, erase, find 같은 연산과정이 O(1)의 실행속도를 가지는지 알 수 있다.
하지만, 해시 함수의 충돌이라는 큰 단점이 존재한다. 인덱스 값이 중복이 된다면, 예를 들어 0000 0000 0000 1921과 1111 1111 1111 1921 인덱스에서 같은 Lee의 데이터가 존재하면, 어떤 데이터에 대응되는 Lee인지 알 방법이 없다.
즉, 서로 다른 키가 같은 해시값을 갖게 되면 충돌이 발생한다. 이를 해결하기 위해, Open Addressing, Chaining 기법이 생겼다.
두 방식 중 먼저, Chaining을 얘기를 해보자.
Chaining에서는 각 인덱스마다 연결 리스트 혹은 Vector와 같은 동적 할당을 한다. 그래서 해당 연결 리스트의 첫번째 원소를 확인하고, 만약 지우고 싶은 카드번호랑 다르게 된다면 그 다음 인덱스를 순회한다. 이러한 방식으로, 해당 원소를 찾거나 삭제 및 업데이트를 진행할 수 있다. 실제로 STL에 있는 해시 자료구조는 Chaining을 사용하고 있다고 한다. 이상적인 상황에서 O(1) 이지만 빈번하게 충돌이 일어날수록 O(N)의 값이 되어질 수도 있다.
두번째, 방식은 Open Addressing이다.
Open Adddressing은 각 인덱스에 바로 (키, 값) 쌍을 대입한다.
예를 들어, (0000 0000 1111)을 인덱스 100번째에 삽입을 하였다고 가정하자. 이때, 만약 (0000 1111 1111)이 삽입을 하려고 했지만 해당 100번째 인덱스는 이미 채워져 있는 상태이다. 이때, 101번째인 다음 칸으로 들어가서, 삽입하게 된다. Find, erase 방식 모두 해당 설명과 동일하다고 생각하면된다. 하지만, OpenAddressing에서 삭제가 이루어질때, 해당 인덱스 값에 데이터가 지워지게 되고, 지워진 해시값 대신에 dummy 값을 두던가 아니면 다른 배열을 두어서 원래 값이 있었지만 현재 값은 삭제되었다는것을 명시해야한다.
OpenAddressing에서 알아갈 내용 또한 두가지이다.
1. Linear Probing
Linear Probing은 충돌 발생 시 오른쪽에서 1칸씩 이동하는 방식이다.
장점 : 인접해 있는 인덱스를 순차적 접근을 하기 때문에 Cache hit ratting이 높다.
단점 : Clustering이 생겨 성능에 영향을 줄 수 있다.
2. Quadratic Probing
Quadratic Probing은 충돌 발생 시 오른쪽으로 1, 3, 5 .. 칸씩 이동하는 방식이다.
장점 : Cache hit ratting이 나쁘지 않고, Clustering을 어느정도 회피할 수 있음
단점 : 해시 값이 같을 경우 여전히 clustering이 발생한다.
백준 문제로 예제 코드를 작성해보도록 하자.
BOJ 7785.
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
unordered_set<string> s;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while (n--)
{
string name, log;
cin >> name >> log;
if (log == "enter") s.insert(name);
else s.erase(name);
}
vector<string> ans(s.begin(), s.end());
sort(ans.begin(), ans.end(), greater<string>());
for (auto x : ans) cout << x << '\n';
}
