접근 속도는 빠르지만 기억 공간이 많이 요구됨.
다른 방식에 비해 검색속도 빠름.
삽입 삭제 작업 빈도가 많을 때 유리.
대부분 탐색방법들은 탐색키를 저장된 키 값과 반복적으로 비교하여 탐색하고자하는 항목에 접근하지만,
해싱은 키 값에 산술적 연산을 적용해 해당 항목이 저장되어있는 테이블의 주소를 계산하여 접근한다. : 자료를 꺼내기 위해 전체 배열을 탐색하지 않음.
*키 값의 연산에 의해 직접 접근이 가능한 구조 : 해시테이블
*해시테이블을 이용한 탐색 : 해싱
키들의 비교에 의한 탐색은 정렬이 안되어있으면 O(n), 정렬되어있으면 O(logn₂ N).
보통 사전과 같은 자료구조를 구현할 때 최상의 선택이 됨.
사전 구조(dictionary)는 맵이나 테이블로 불리기도 한다. 탐색 키/키와 관련된 값으로 2가지 필드를 가짐.
ex)영어 단어:키 / 해당 영단어의 정의 : 값
탐색키에 따라 정렬이 되어있기도, 그렇지 않기도 하다. 무조건 탐색키에 의해서 항목에 접근할 수 있으면 되는데, 정렬 여부는 추상 자료혀 사전구조를 구현할 때 결정해야될 문제.
해싱은 사전구조를 가장 효율적으로 구현할 수 있는 방법이다.
탐색키의 비교가 아닌, 탐색키에 수식을 적용시켜 탐색키가 저장된 위치를 얻는다.
사용 분야
- 보안 : 데이터의 위변조를 막기 위하여 전자서명, 부인방지(메시지 수신자가 수신한 메시지를 부인 또는 이의제기할 경우를 방지하는 서비스) 또는 보안 알고리즘에 사용
- 사전, 맞춤법 검사기, 방문했던 웹 페이지 기록 저장, 투표, 컴파일러의 심볼 테이블 등 구현에 사용.
구조
자료를 저장하는데는 배열을 사용 : 단점도 있지만 원하는 항목이 저장된 위치를 알고있을 경우 빠르게 자료를 삽입하고 꺼낼 수 있음.
어떤 항목의 탐색 키만 가지고 바로 항목이 저장되어있는 배열의 인덱스를 결정하는 기법 : 해싱
hash function이란 탐색 키를 입력받아 hash address를 생성하고,
이 hash aress가 배열로 구현된 hash table의 index가 됨. 이 배열 인덱스 위치에 자료를 저장할 수도, 꺼낼 수도 있다.
하나의 버켓은 s개의 슬롯(slot)을 가질 수도 있고, 한 슬롯에는 하나의 항목이 저장된다.
해시 테이블에 존재하는 버켓 수를 M이라고 했을 때 해시함수 h()는 모든 k에 대해 0≤h(k)≤M-1 범위 값을 제공해야한다.
서로 다른 탐색키 k1과 k2에 대해 h(k1)=h(k2)인 경우를 충돌(collision)이라고 한다. 그리고 이 k1와 k2키를 동의어(synonym)이라 한다.
| 충돌(collision) 1.키값은 무한한데 해시코드는 정수개만큼밖에 제공을 못함. 2.다른 해시코드를 만들어냈어도 방이 한정되어있어 같은 방을 배정받음. |
충돌이 발생하면 bucket내부에서 순차탐색하는 시간이 길어져 탐색 성능이 저하되어, 해시함수를 수정하거나 해시테이블의 크기를 적절히 조절해줘야한다. bucket의 크기가 크면 메모리 낭비, 작으면 충돌의 우려가 있음.
충돌이 계속되어 슬롯보다 많이 발생하게되면 overflow발생. 이를 해결하기 위한 방법이 반드시 필요하다.
좋은 해시 함수의 조건
1. collision이 적어야 함.
2. 해시 함수 값이 해시 테이블의 주소 영역 내에 고르게 분포되어야 함.
3. 계산이 빨라야 함.
1. 제산 함수
나머지 연산자(mod)를 사용해 탐색 키를 해시테이블의 크기로 나눈 나머지를 해시주소로 사용.
h(k)=k mod M, M은 해시테이블 크기, 해시 함수의 값의 범위는 0~(M-1)이 됨.
M은 주로 나누어 떨어지지 않는 소수로 선택하는데, M이 짝수면 해시함수 연산결과가 k가 짝수면 짝수, k가 홀수면 홀수가 된다.
메모리 주소로 해싱하면 k가 짝수일 가능성이 높음(메모리주소는 보통2의 배수). 따라서 M은 항상 홀수여야 한다.
나머지 연산을 수행했을 때 음수가 나올 수 있으므로 hash index = key % M의 index값이 음수이면 M을 더해 양수로 만들어준다.
2. 폴딩함수
탐색 키를 여러 부분으로 나눠 모두 더하거나 비트별로 XOR연산 결과를 해시 주소(버킷주소(index))로 사용.
이동 폴딩(shift folding)과 경계 폴딩(boundary folding)이 대표적.
shift folding : 탐색 키를 여러부분으로 나눈 값들을 더해 해시주소로 사용
boundary folding : 탐색 키의 이웃한 부분을 거꾸로 더해 해시주소 얻음
폴딩을 구현할 때는 키 값을 해시테이블 크기만큼의 수를 가지는 부분으로 분할 후, 분할된 부분을 합해 해시주소를 만든다.
ex) 키 값이 12320324111220이고, 해시주소가 10진수 3자리로 구성되어있는 경우
shift folding : 123 + 203 + 241 + 112 + 20 = 669
boundary folding : 123 + 302 + 241 + 211 + 20 = 897
3. 중간 제곱 함수(Mid-Square)
키 값을 제곱한 후, 결과 값의 중간의 몇 비트만 선택헤 해시주소(=버킷주소(=인덱스))생성
제곱한 값의 중간 bit드른 일반적으로 키의 모든 문자들과 관련이 있어 서로 다른 키의 몇 개의 문자가 같더라도 서로 다른 결과값을 갖게된다.
탐색 키 값을 제곱한 값의 중간비트들의 값은 비교적 고르게 분산됨.
4. 비트 추출 방법
해시테이블의 크기가 M=2^k일 때 탐색키를 이진수로 간주해 임의의 위치 k개의 비트를 해시주소로 사용함.
간단한 방법이지만 키의 일부 정보만을 사용하여 해시주소의 집중 현상이 일어날 가능성 높음.
5. 숫자 분석법(Digit-Analysis)
숫자로 구성된 키에서 각 위치에 있는 수의 특징을 미리 알고있을 때 유용.
키의 각 위치의 숫자 중가장 고르게 나타나있는 자릿 수를 해시테이블의 크기에 적합한 만큼 조합해 해시주소로 사용.
예를 들어(200812345)에서 입학년도를 의미하는 앞의 4자리 수는 편중되어 가급적 사용하지 않고, 나머지수를 조합하는 방법.
삽입/삭제가 빈번한 경우 비효율적, 파일 키값이 이미 알려진 static file인 경우 유용.
충돌 해결법
1. 충돌이 일어난 항목을 해시테이블의 다른 위치에 저장
- 해시테이블 안에서 현재 사용되지 않는 공간 찾음. : 선형조사법(linear probing)
2. 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조 변경
- 체이닝(chaining)
선형조사법 (linear probing)
특정 버켓에서 충돌 발생시 해시 테이블에서 비어있는 버켓을 찾는 방법.
비어있는 공간을 찾는 것을 조사(probing)라고하며, 여러 방법의 조사가 가능함.
ht[k]에서 충돌 발생시 ht[k+1]이 비어있는지 살핌. 비어있지 않다면 ht[k+2]살핌. 이런식으로 계속 살피다가 테이블 끝에 도달하게 될 경우 다시 테이블 처음으로 가고, 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬 것.
구현
해시테이블은 1차원 배열로 구현. 키와 값 필드 가짐. 버켓당 하나의 슬롯 가정
: 탐색 키들이 집중되어 저장되는 군집화(clustering) 현상 발생하게 됨.
최악의 경우 집중된 항목들이 결합(coaliasing)하는 현상까지 발생하게 되므로, 탐색시간이 길어지는 단점 가짐.
간단하다는 장점이 있지만 오버플로가 자주 발생하면 군집화와 결합에 의해 탐색 효율이 크게 저하됨.
충돌로 인해 3개의 버킷에 연달아 저장되었고 두번째 데이터가 빠졌다고 가정했을 경우 첫번째 데이터에서 세번째 데이터로 접근하지 못한다.
따라서 한 번도 사용이 안 된 버켓, 사용되었으나 현재는 비어있는 버켓, 현재 사용중인 버켓으로 분류해야하며
탐색 함수에서는 한 번도 사용이 안 된 버켓을 만나야만 탐색이 중단되도록 해야 한다.
->개선
이차 조사법(quadratic probing)
선형 조사법과 유사하지만 다음 조사할 위치를 (h(k)+inc*inc) mod M 으로 변경하여 결정한다.
모든 위치를 조사하려면 테이블 크게는 소수여야 한다.
선형 조사법의 집중과 결합 문제를 크게 완화시킬 수 있고, 2차 집중 문제를 일으킬 수 있지만 1차 집중처럼 심각한 것은 아니다.
2차 집중의 이유는 동일한 위치로 매핑되는 여러 탐색키들이 같은 순서에 의해 빈 버켓을 조사하기 때문인데, 이걸 이중 해시법으로 해결할 수 있음.
->개선
이중 해시법(double hashing) 또는 재해싱(rehashing)
오버플로가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법. 항목들을 해시테이블에 더욱 균일하게 분포시킬 수 있어 효과적인 방법임.
해시값이 같더라도 탐색키가 다르면 서로 다른 조사순서를 가져 2차 집중 문제 발생 피할 수 있음.
1차 집중 : primary clustering, 묶인 데이터의 긴 체인을 만드는 경우
2차 집중 : secondary clustering, 서로 다른 키가 동일한 값으로 동일한 순서를 갖게 됨
선형 조사법의 문제점은 한번도 사용되지 않은 위치가 있어야 탐색이 빨리 끝난다.
만약 거의 모든 위치가 사용되고 있거나 사용된 적 있는 위치라면 실패하는 탐색인 경우 테이블의 거의 모든 위치를 조사하게 되는데,
체이닝에서는 이런 문제점이 없음.
체이닝
선형조사법은 해시 주소가 다른 키와도 비교해야하기때문에 탐색시간이 많이 소요된다.
해시주소가 같은 키들을 하나의 리스트로 묶어두면 불필요한 비교는 하지 않아도 된다. : 리스트의 크기를 예측할 수 없어 연결리스트로 구현
연결리스트의 어디에 새로운 항목을 삽입하느냐를 결정할 때,
키들의 중복을 허용하는 경우 연결리스트의 처음에다, 허용되지 않는 경우(연결리스트를 처음부터 탐색하여야하므로 어차피 연결리스트의 뒤로 가야하므로) 뒤에 삽입하는 것이 능률적임.
Open Addressing은 연속된 공간에 데이터를 저장하여 Separate Chining에 비해 캐시 효율이 높아 데이터 갯수가 적다면 성능이 더 좋지만, 배열의 크기(M)가 커질 수록 장점이 사라짐. = 캐시 적중률이 낮기 때문.
구현
입력받은 문자열에 각 아스키값을 더해서 해시코드 만들기.
* 고정된 크기의 배열을 선언함.
* 해시코드 % size를 index로 사용하자.
참고 : https://youtu.be/6Iq5iMCVsXA
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
package com.company;
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
class HashTable{
class Node {
String key; //검색할 키
String value; //검색 결과로 보여줄 값
public Node(String key, String value){
this.key = key;
this.value = value;
}
String value(){ //get
return value;
}
void value(String value){ //set
this.value = value;
}
}
//data저장할 배열
LinkedList<Node>[] data;
//크기를 미리 정해서 배열방을 미리 만들어놓음
HashTable(int size){
this.data = new LinkedList[size];
}
//해시 알고리즘을 가진 해시함수.
//키를 받아서 해시코드 반환.
int getHashCode(String key){
int hashcode = 0;
//각 래터에 아스키값을 더해줌.
for(char c : key.toCharArray()){
hashcode += c;
}
return hashcode;
}
//해시코드 받아서 배열방의 index로 변환해주는 함수
int convertToIndex(int hashcode){
return hashcode % data.length;
}
//index로 배열방을 찾은 이후 배열방에 노드가 여러개 존재하는 경우
//검색 키를 가지고 해당 노드를 찾아오는 함수
//
Node searchKey(LinkedList<Node> list, String key){
//배열방이 null이면
if(list == null) return null;
//배열방 안의 linked list를 돌면서 node의 키와 검색하는 키가 같은지 확인
for(Node node : list){
//찾았으면
if(node.key.equals(key)){
return node;
}
}
//못찾았으면
return null;
}
//data 받아서 저장하는 함수
void put(String key, String value){ //저장할 키, 값
//key로 hashcode받아옴
int hashcode = getHashCode(key);
//받아온 hashcode로 저장할 배열방번호(=index)받아옴
int index = convertToIndex(hashcode);
System.out.println(key+", hashcode("+hashcode+"), index("+index+")");
//변수 index를 이용해 배열방에 있는 data가져옴
LinkedList<Node> list = data[index];
//배열방이 null이면 LinkedList 생성하고 해당list를 배열방에 넣어줌.
if(list == null){
list = new LinkedList<Node>();
data[index] = list;
}
//배열방에 혹시 기존 키로 배열방을 갖고있는지 node를 받아옴
Node node = searchKey(list, key);
//node가 null이면 data가 없다는 것이므로,
if(node == null){
//받아온 정보로 node객체를 생성해 list를 추가
list.addLast(new Node(key,value));
}else{
//node가 null이 아니면
//해당 노드를 대체해주는 것으로 중복키를 처리
node.value(value);
}
}
//key를 가지고 data를 가져오는 함수
String get(String key){
int hashcode = getHashCode(key);
int index = convertToIndex(hashcode);
//index에서 linkedlist를 가져옴
LinkedList<Node> list = data[index];
//linkedlist안에 해당 키를 가지는 노드를 검색해옴
Node node = searchKey(list,key);
//찾은 결과 반환
return node == null? "Not found" : node.value();
}
}
public class Main {
public static void main(String[] args) throws IOException {
HashTable h = new HashTable(3);
h.put("suk","She is pretty");
h.put("jin","She is a model");
h.put("park","She is an angel");
h.put("Tae","She is cute");
System.out.println(h.get("suk"));
System.out.println(h.get("jin"));
System.out.println(h.get("park"));
System.out.println(h.get("Tae"));
System.out.println(h.get("hee"));
}
}
|
cs |