해시
개념
키에 대응대는 값을 저장하는 자료구조이다.
다른 자료구조들을 보면 특정 연산은 빠른 반면 특정 연산은 느린 상황이 나오게 마련인데 해시는 모든게 O(1)이다.
해시자료구조에서는 해시함수라는 것이 쓰인다. 해시함수는 마치 카드번호 16자리에서 뒷 4자리만 배열의 인덱스로 쓴 것과 같이 임의 길이 데이터를 고정된 길이의 데이터로 대응시키는 함수이다.
충돌
서로 다른 키가 같은 해시값을 가지게 될 경우 동작이 이상하게 되어버린다 → 충돌
해시함수를 적절하게 잡아서 충돌을 해결할 수 있지 않냐는 의문을 가질 수 있지만 해시함수의 목적 자체가 함수의 입력으로 주어지는 정의역의 공간이 너무 커서 이걸 배열의 인덱스로 활용할 수 없으니 범위를 줄이고자 하는데 있다. 그래서 정의역 공간을 늘리는 것은 해시함수가 추구하는 방향과는 어긋난다.
이 충돌을 회피하기 위해서 회피 방안에 대해 많은 연구를 거듭한 결과 chaning, open address라는 방법을 찾아냈다.
충돌 회피 - Chaining
각 인덱스 마다 연결리스트를 주고 삽입이 발생하면 해당하는 연결리스트에 삽입해주고 삭제,수정 등은 해당 키값을 조회하고 연결리스트를 순회하면서 일치하는 값이 발견되면 삭제, 수정등이 발생한다.
만약 많은 데이터를 저장했는데 데이터들의 해시값이 모두 같다고하면 연결리스트 1개에 대해서 insert erase find update를 다 하는 상황이 발생한다. 따라서 insert는 O(1)이 되겠지만 나머지 연산들은 모든 원소를 순회해야 하기 때문에 O(N)이 된다.
이처럼 해시자료구조는 이상적인 상황에서는 O(1)이지만 충돌이 빈번할수록 성능이 저하되고 모든 키의 해시값이 같은 최악의 상황에서는 O(N)이 되기 때문에 각 키의 해시값이 최대한 균등하게 퍼져야 성능이 좋아지고 그러기 위해서는 주어진 데이터에 대한 좋은 해시함수를 정해야 한다.
충돌 회피 - Open Addressing
해당 키값이 비어있다면 밸류를 넣어주고 만약 값이 이미 존재한다면 바로 옆 칸에 저장을 해준다. 그 옆 칸에도 이미 값이 있다면 비어있는 키값이 나올 때까지 옆으로 이동해 값을 넣어준다.
find는 해당 키값을 조회하고 없다면 옆으로 이동해 찾아 명령을 수행하는 방식이다. 옆으로 계속 이동해 찾다가 비어있는 값을 만나면 해당 값이 없다는 의미이다.
erase는 해당 값을 찾고 그대로 지워서 빈 칸으로 남겨놓지 않는다. 이유는 find에서 값이 비어있다면 없다는 의미로 받아들이기 때문에 지워진 빈칸 이후의 값들 전체를 조회가 불가능하게 만드는 문제가 발생한다. 그래서 지우고 난 다음 dummy값을 두거나 별도의 배열을 두는 방법으로 원래 값이 있었으나 제거된 상태임을 명시해준다.
- Linear Probing 충돌 발생시 오른쪽으로 1칸씩 이동하는 방식 장점- Cache hit rate가 높다. 단점- Clustering이 생겨 성능에 영향을 줄 수 있다.(데이터가 모여있게 됨 바로 다음칸을 찾기 때문에)
- Quadratic Probing 충돌 발생시 오른쪽으로 1, 3, 5 칸씩 이동하는 방식 장점 - Cache hit rate가 나쁘지 않다. Clustering을 어느정도 회피할 수 있다. (데이터가 모여있지 않음) 단점 - 해시값이 같을 경우 여전히 Clustering이 발생한다.
- Double Hashing 충돌 발생시 이동할 칸의 수를 새로운 해시함수로 계산하는 방식 장점 - Clustering을 효과적으로 회피할 수 있다. 단점 - Cache hit rate가 낮다.
연습문제
boj-7785
import sys
input= sys.stdin.readline
N = int(input().rstrip())
enter_leave_map = {}
for _ in range(N):
name, enter_or_leave = input().rstrip().split()
if enter_or_leave == "leave":
enter_leave_map.pop(name)
else: enter_leave_map[name] = 1
for name in sorted(enter_leave_map.keys(), reverse=True):
print(name)boj-1620
N, M = map(int, input().split())
name_number_map = {}
pocket_monters = []
for i in range(1, N+1):
name = input()
pocket_monters.append(name)
name_number_map[name] = i
for _ in range(M):
question = input()
if question.isdigit():
print(pocket_monters[int(question) - 1])
else:
print(name_number_map[question])집합과 같은 식으로 원소를 추가하고 빼는 일이 빈번하거나 문자열을 수에 대응시키는 것처럼 키를 가지고 값을 알아내야하는 일이 필요하다면 해시를 활용해서 풀 수 있다.
이것만 써서 풀어야 하는 문제는 너무 쉬워서 잘 안나오겠지만 중간에 해시를 활용해서 풀어야 하는 경우는 출제자 입장에서 간단하게 난이도를 높일 수 있어서 자주 있을 것이다. 그러므로 잘 익혀놓을 필요가 있다.
구현
Load factor = 원소의 개수 / 테이블의 크기
이 로드 팩터를 작게 유지하면 충돌이 덜 생겨 각 연산이 거의 O(1)에 동작하겠지만 반대로 cache hit rate가 줄어들고 메모리도 많이 차지한다는 단점이 있다.
반대로 로드팩터를 크게 유지하면 메모리는 적게 차지하지만 충돌이 많이 생겨서 성능에 악영향을 줄 수 있다.
Chaning은 연결리스트로 연결하기 때문에 각 키 값에 여러 원소를 둘 수 있다. 그래서 충돌을 어느정도 감수하더라도 공간효율성을 고려해서 로드팩터를 1이하게 되게 한다.
Open Addressing 방식은 각 인덱스에 반드시 하나의 원소가 들어가야 하기 때문에 만약 로드 팩터를 1이하로 뒀다가는 해시테이블이 거의 다 채워질 쯤 되어서는 빈 곳을 찾느라 삽입이 아주 느리게 이루어질 것이다. 그렇기 때문에 로드팩터를 보통 0.75 이하 정도로 둔다.
정리하면 chaining에서는 테이블의 크기를 최대 삽입 횟수로 open addressing에서는 최대삽입횟수 * 1.33 정도로 두면 되지만 알고리즘 문제를 푸는 경우에는 메모리가 널널한 경우가 많기 때문에 넉넉하게 2배정도로 잡는것을 권장함
테이블의 크기가 소수이면 좋다. 이건 해시함수와 관련이 있다.(무조건 소수일 필요는 없다.)
충돌이 빈번하게 일어나는 해시 함수
- 해시함수의 값이 한정적임
- 해시함수의 키인 문자가 최대 100자라고 했을 때 아스키 코드가 128보다 작기 때문에 12800보다 작을 수밖에 없다.
- 즉 0 ~ 1000002 사이에서 나오는게 아니라 0 ~ 12800 사이에서만 해시함수의 값이 발생하기 때문에 충돌이 많이 발생할 수밖에 없다.
const int M = 1000003;
int hash(string& s) {
int h = 0;
for(auto x : s) h += x;
return h % M;
}롤링 해시를 활용한 사례
- “abc”를 이 해시 함수에 넣는다고 하면 a 1000 **2 + b 1000 1 + c * 1000 0 의 값이 키값이 된다.
- 다른 a나 M을 사용해도 되지만 a * M이 int 최대값을 넘는다면 int overflow가 발생할 수 있다.
const int M = 1000003;
const int a = 1000;
int hash(string& s) {
int h = 0;
for(auto x : s)
h = (h * a + x) % M;
return h;
} 자세한 구현은 주말에 파이썬 클래스로 만들어 구현을 해보아야겠다.
