데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력 받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 방법으로, 궁극의 탐색 알고리즘이다.
해시 테이블의 성능은 공간을 팔아 얻어낸 것이라고 생각하면 된다.
보통 테이블의 엔트리는 <Key, value> 로 나타내며 이 때 value 는 key 로 인한 hash function 의 아웃 풋이다.
해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.
허나 해시를 이용하면 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형 시간이 걸리기도 했던 것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.
→ Hash Table 은 bucket 들과 그 bucket 을 이루고 있는 slot 들로 구성되어있다.
※ 해쉬 함수의 요구조건
- 계산하기 쉬워야 한다.
- 충돌의 횟수를 최소화 해야 한다.
- 편향되지 않아야 한다.
◇1. Direct Addressing Table
Direct Addressing Table 은 key-value쌍의 데이터를 배열에 저장할, key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다.
예를 들면 키 값이 400인 데이터가 있다면, 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.
똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에는, 각 키마다 자신의 공간이 존재하므로 그 위치에다가 저장을 하면 되고, 삭제 시에는 해당 키의 위치에 NULL 값을 넣어주면 된다. 탐색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.
찾고자 하는 데이터의 key 만 알고 있으면 즉시 위치를 찾는 것이 가능하므로 탐색 저장, 삭제, 갱신은 모두 선형시간 인 O(1) 로 매우 빠른 속도로 처리가 가능하다.
다만 key값이 최대 크기만큼 배열이 할당되기 때문에, 크기는 매우 큰데, 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.
◇2. Hash Table
Hash Table 은 key-value 쌍에서 key 값을 테이블에 저장할 때, Direct Addressing Table과 달리 Key 값을 함수를 이용해 계산을 수행한 후,
그 결과 값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key 값을 계산하는 함수는 해쉬 함수(Hash Function) 이라고 부르며, 해쉬 함수는 입력으로 key를 받아, 0부터 배열의 크기 -1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기 만큼으로 변환시킨 것이다.
이 경우 k값이 h(k) 로 해쉬 되었다고 하며, h(k)는 k의 해쉬 값이라고 한다
2.1 충돌(Collusion)
하지만 해쉬 테이블은 '충돌'이 일어날 수 있다는 큰 문제점이 있다. 충돌이란, 다른 k값이 동일한 h(k)값을 가져 동일한 slot 에 저장되는 경우를 말한다.
예를 들자면 k1과 k12 을 해쉬하였더니 h(k1) = h(k12) 인 경우를 들 수 있다. Direcet Addressing Table 에서는 이를 방지하기 위해 모든 key 값이 다르다고 전제하였지만 해쉬 테이블에서는 key값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다.
하지만 해쉬 함수를 아무리 잘 짜더라도 충돌을 '완전히' 방지한다는 것을 보장하기는 힘드므로, 충돌을 방지하기 위한 방법으로 충돌을 어느 정도 허용하되 이를 최소화 하는 방법도 사용하기도 한다.
Chaining 방법 - 충돌을 허용하되 최소화 하는 방법
충돌을 허용하지만 이를 최소화 하기 위한 방법 중 하나인 체이닝 방식이다. 체이닝이란 이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, 해쉬 테이블에선 동일한 해쉬 값이 출력 되어 충돌이 일어나면, 그 위치에 있던 데이터에 key 값을 포인터로 뒤이어 연결한다. (마치 Linked List 처럼)
따라서 최초로 h(k) 위치에 저장된 데이터를 시작으로 그 이후의 h(k) 값이 출력되는 데이터는 모두
연결 리스트의 형태를 취한다.
그렇기 때문에 최초의 위치를 탐색하는 해쉬 과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다.
Chaining 방법에서의 수행시간은 삽입 시에는 해쉬 값을 이용해 바로 slot 에 저장하면 되므로 상수 시간에 일어나고, 삭제는 연결리스트의 삭제와 동일하게 상수시간에, 탐색 시에는 견결 리스트를 따라가기 때문에 연결리스트의 길이 만큼 발생하지만, 최악의 경우, 즉 모든 데이터의 해쉬값이 일치하여 한 인덱스에 젖아됬을 경우엔 연결리스트의 탐색시간과 동일한 선형시간을 가지게 된다.
적재률
하지만 이 최악의 경우는 극단적인 예로써, 평균적인 경우엔 O(a+1)의 시간이 걸린다. a는 적재율을 뜻하며 적재율이란 현재 저장된 key값 갯수(K), 전체 테이블의 갯수(N)을 서로 나눈 값(K/N)이다. 즉 현재 저장된 데이터가 많으면 많아질수록 충돌 확률이 높아져 연결 리스트 탐색 확률도 증가하며, 적을수록 리스트 탐색 확률이 적어진다는 것이다.
Simple uniform hash
충돌을 최소화 하는 방법 중에 충돌이 적은 좋은 해쉬 함수를 만드는 방법도 있다. 좋은 해쉬 함수의 조건은 Simple uniform hash 함수를 만드는 것으로, 이 조건은 다음과 같다.
1. 계산된 해쉬 값들은 0부터 배열의 크기-1 사이의 범위를 '동일한 확률'로 골고루 나타날 것.
2. 각각의 해쉬 값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것.
첫 번째 조건을 충족하면 충돌이 일어날 확률이 적어질 것이며, 두 번째 조건은 해쉬값들이 서로 연관이 있을 경우 연관성이 있으면 해당 해쉬 값이 등장하는 패턴이나 순서가 존재 할 수 있고, 이는 반복적인 충돌을 일으킬 확률이 있기 때문이다.
division method
해쉬 함수는 정말 다양하지만 대표적인 해쉬 함수로는 divison method가 있는데, modular 연산 방법을 이용하는 방법이다. 특정 key를 어떤 수로 나눈 나머지를 해쉬값으로 사용한다.
예를 들어 m=100이면 k mod m은 0부터 99까지의 범위를 가진다. 이 범위의 m은 해쉬 테이블의 성능을 크게 좌우하는데, m의 크기는 보통 키의 수의 3배가 적당하다고 한다. (적재율이 30%쯤까지 충돌이 거의 일어나지 않는다고 한다.)
그리고 m으로 2^p값을 사용하는 것엔 큰 주의를 요한다. 왜냐하면 m이 2^3이면, 2진수로 00001000이고, 4번째 이하의 숫자만 해쉬값에 영향을 끼치기 때문이다.
예를 들어 k1과 k2가 각각 10110100,10120100이면 둘 다 같은 해쉬값을 출력한다. 이를 방지하기 위해서 m은 보통 2^p에 근접한 소수를 선택한다고 한다.
◇ 정리
해시 알고리즘의 기초
- 인덱스를 사용하는 검색 알고리즘이다.
- 대용량의 데이터를 검색할 떄 주로 사용한다.
- 이진 검색 알고리즘과 병행해서 사용하면 빠른 검색 속도를 얻을 수 있다.
- 검색 성능 : O(1)
- 장점 : 데이터의 양에 관계 없이 빠른 성능을 기대할 수 있다.
해시 알고리즘에서 사용하는 몇 가지 용어
- 버킷 : 해시 주소 하나에 1개 이상의 데이터가 저장되는 전체 메모리 공간
- 슬롯 : 버킷에서 하나의 데이터가 저장되는 메모리 공간
- 충돌 : 서로 다른 데이터인데 같은 해시 주소를 갖게 되면 충돌이 발생한다.
- 오버플로 : 보통 충돌을 방지하기 위해 해시 주소 하나에 여러 슬록을 만들지만, 충돌이 계속해서 발생하여 데이터를 저장할 슬롯이 없어지는 상황
"오버플로" 해결방법
- 선형 조사 방법 : 해시 주소에 데잍어가 채워져 잇을 경우 옆자리를 확인하는 방법→ 데이터가 집중되는 현상 발생 (클러스터링)
- 링크드 리스트 사용 : 같은 해시 주소를 갖는 데이터를 배열이 아니라 링크드 리스트로 구성→ 클러스터링이 발생하면 링크드 리스트 내부에서 검색 작업이 발생해 순차 검색 해야 한다.
- 리해싱 : 다른 해시 함수를 사용해서 새로운 해시 주소를 생성하는 것→ 함수의 성능에 따라 알고리즘의 성능이 달라질 수 있다.
c++ 에서 해시 테이블을 구현하는 방법 중 대표적으로
unordered_map 이 있다.
코테보기 전에 이거 외우고 가자.
unordered_map 사용하기
- map보다 더 빠른 탐색을 하기 위한 자료구조이다.
- unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.
- map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)이다.
- unordered_map을 사용하기 위해서는 #include< unordered_map > 을 선언해야 한다.
- unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보인다.
- 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다.
함수
empty( )
- 맵이 비어있는지 확인하는 함수
- if unordered_map is empty, then return 1 else 0
size( )
- 맵의 크기를 확인하는 함수
- return size_type ( unsigned int )
operator [ ]
- 맵에서 key를 통해 value를 지정하는 operator
- map_name[key] = value
find( key )
- 맵에서 key에 해당하는 원소를 찾는 함수
- if key is contained, then iterator else map_name.end()
count( key )
- 맵에서 key에 해당하는 원소의 갯수를 반환하는 함수
- if key is contained, return 1 else 0
insert( )
- 맵에 pair<key,value> 를 추가하는 함수
- if key is contained, then not insert
erase( key )
- 맵에서 key에 해당하는 원소를 제거하는 함수
- erase 하는 방법 : 특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제
clear( )
- 맵을 초기화하는 함수
operator =
- 대입연산자 가능
※ 주의할 점
unordered_map 을 통해 for 문을 돌 때, vector 와 약간 다르다는 것을 알고 있어야 한다.
for (auto i = MapPlayer.begin(); i != MapPlayer.end(); ++i) {
if (i->second) {
iAnswer = i->first;
break;
}
}위의 코드와 같은 방식으로 for 문을 돈다. 주의 할 점은 ++i 라는 것이다.
(또한 i→first , i→second 방식으로 원소를 뽑아낼 수 있다는 점을 알아둬야 할 듯.)
프로그래머스 문제
- 해쉬 1번
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
string answer = "";
string iAnswer = ""; // 리턴값을 저장하는 변수.
unordered_map<string,int> MapPlayer; // string(key값)은 선수의 이름, int(value값)은 선수의 수.
for(int i=0 ; i<participant.size() ; i++) {
if(!MapPlayer.count(participant[i])){
MapPlayer[participant[i]] = 1;
}else {
MapPlayer[participant[i]] += 1;
}
}
for(int i=0 ; i<completion.size() ; i++ ) {
auto it = MapPlayer.find(completion[i]);
--it->second;
}
for(auto it = MapPlayer.begin() ; it != MapPlayer.end() ; ++it) {
if(it->second) {
answer = it->first;
break;
}
}
return answer;
}참고링크
'책장 > 알고리즘' 카테고리의 다른 글
| [프로그래머스]타겟넘버 (0) | 2021.04.30 |
|---|---|
| 완전탐색 (0) | 2021.04.24 |
| 깊이/너비우선탐색(DFS,BFS) (0) | 2021.04.23 |
| 힙 (0) | 2021.04.23 |