insert, erase, find, update 모두 O(1)
해시 함수는 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수
해시에서 가장 중요한 사항은 충돌이고 이 충돌을 잘 처리하는게 해시의 성능에 가장 큰 영향을 준다.
서로 다른 키가 같은 해시값을 가지면 충돌 발생
해시의 의의에는 함수의 입력으로 주어지는 정의역이 너무커서 인덱스로 사용할 수 없으니
그 크기를 줄이는 것. 충돌은 어쩔 수 없다.
허나 회피하는 방법이 연구되었다.
첫 번째가 Chaining
Chaining에서는 각 인덱스마다 연결 리스트를 하나씩 둠
STL 해시 자료구조는 Chaining 사용
최악 경우 find , update O(N)
균등하게 퍼지도록 좋은 해시함수를 찾는 것이 중요
두 번째 Openaddressing
해당 칸이 이미 있는 경우 옆 칸에 저장한다.
찾을 시 해당 장소에 워나는 값이 없다면 옆 칸을 다 찾는다.
찾는 값이 없을 시 빈칸에 가게되고 없음을 파악
삭제 시 그냥 지워버리면 find 시 존재하는 값을 찾지 못하게 될 수 있음
그러니 쓰레기값을 대신 넣어버렷. 쓰레기값에 insert 가능
Linear Probing 탐사병
충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식
장점 - Cache hit rate가 높다
단점 Clustering이 생겨 성능에 영향을 줄 수 있다.
Quadratic Probing 제곱하며 탐사
충돌 발생 시 오른쪽으로 1, 3, 5, ... 이동하는 방식
장점 Cache hit rate가나쁘지 않다, Clustering을 어느정도 회피할 수 있다.
단점 해시 값이 같을 경우 여전히 Clustering이 발생
Double Hashing = 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식
장점 Clustering을 효과적으로 회피할 수 있다.
STL
unordered_set<int> s;
s.insert(-10);
s.erase(100); 지웠으면 1 실패 0
if (s.find(15) != s.end())
s.size()
s.count(50)
for (auto e : s)
반복자 존재
unordered_multiset 중복허용 erase 조심해야해 전부 다 지워짐
unordered_multiset<int> ms
ms.insert(-1);
ms.size();
for (auto e : ms)
ms.erase(15);
ms.erase(ms.find(-10)); find 반복자 반환 하나만 지움
ms.count(100);
unordered_map<string, int> m;
m["hi"] = 123;
m]"bkd"] 1000;
m["gogo"] = 165;
m.size()
if (m.find("hi") != mend())
m.erase("bkd");
for (auto e : m)
구현
해시 테이블 크기, 해시 함수
Load factor = 원소의 개수 / 테이블의 크기
LF 클 시 충돌 자주 발생하지만 cache hit rate 높고
낮을 시 충돌 덜 발생, chr 낮음
보통 LF를 1이하로 맞춤 이 경우 Open addressing에서는
빈칸을 찾는데에 시간을 소비해 load factor를 0.75 정도로 준다.
정수에 대한 해시 함수
const int M = 1000003;
int my_hash(int x) {
return (M + x % M) % M;
}
문자열에 대한 해시 함수
const int M = 1000003;
int hash(string* s) {
int h = 0;
for (auto x : s) h += x;
return h % M;
}
// 결과가 집중되는 성향 있어 충돌 빈번
문자열을 진법처럼 처리 하면 그나마 낫다
(롤링 해시)
const int M = 1000003;
const int a = 1000;
int my_hash(string& s) }
int h = 0;
for (auto x : s)
h = (h * a + x) % M;
return h;
}const int M = 1000003;
const int a = 1000;
const int MX = 500005;
int head[M];
int pre[MX];
int nxt[MX];
string key[MX];
int val[MX];
int unused = 0;
int my_hash(string& s) {
int h = 0;
for (auto x : s)
h = (h * a + x) % M;
return h;
}
int find(string k) {
int h = my_hash(k);
int idx = head[h];
while (idx != -1) {
if (key[idx] == k) return idx;
idx = nxt[idx];
}
return -1;
}
void insert(string k, int v) {
int idx = find(k);
if (idx != -1) {
val[idx] = v;
return;
}
int h = my_hash(k);
key[unused] = k;
val[unused] = v;
if (head[h] != -1) {
nxt[unused] = head[h];
pre[head[h]] =unused;
}
head[h] = unused;
unused++ ;
}
void erase(string k) {
int idx = find(k);
if (idx == -1) return;
if (pre[idx] != -1) nxt[pre[idx]] = nxt[idx];
if (nxt[idx] != 01) pre[nxt[idx]] = pre[idx];
int h = my_hash(k);
if (head[j] == idx) head[h] = nxt[idx];
}
댓글