1. Hash Table 이란?
해시 테이블은 Key와 Value로 구성된 하나의 테이블을 말한다.
해시 함수를 사용하여 색인(index)을 bucket이나 slot의 배열로 계산한다.
해시테이블은 데이터를 담을 테이블을 미리 크게 확보해 놓은 후
입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는다.
데이터를 찾는 과정은 다음과 같다.
1. Input Data는 Hash Function을 거쳐서 테이블내의 인덱스로 변환된다.
2 그 후, 구한 인덱스를 이용해 테이블 내의 요소에 접근하게 된다.
이러한 이유로 해시테이블은 탐색, 삽입, 삭제 3가지 연산들의 시간복잡도에 대해
적절한 가정하에 평균적으로 O(1)의 상수시간에 가까워 지고 충돌이 많이 발생할수록 O(n)에 가까워진다.
다만, 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.
통계적으로 해시 테이블의 공간 사용률이 70 ~ 80%에 이르면 성능 저하가 나타나기 시작한다.
2. Hashing 이란?
해싱이란 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다.
해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
JDK내에서 해싱에서 사용하는 자료구조는 다음과 같이 배열(Array)과 연결리스트(LinkedList)의 조합으로 되어 있으며 이 방법은 Separate Chaining방식이라고 부른다.
Separate Chaining 방식이 나온 이유는 해시테이블의 고질적인 문제인 해시 충돌을 방지 하기위해 고안되었다.
※ 해시 충돌(Hash Collision): 해싱된 키(Hash Key)가 중복되어 해당 버킷에 이미 레코드가 존재하는 현상을 말한다.
(JDK 1.8부터는 하위 데이터가 8개 이하일때 LinkedList를 이상일때는 TreeMap을 사용한다.)
저장할 데이터의 키를 Hash function에 넣으면 배열의 한 요소를 얻게 되고, 그 곳에 연결되어 있는
LinkedList에 데이터를 저장하게 된다.
하나의 예를 들어보겠다.
어떤 동네의 동사무소 직원이 해당 지역 주민들의 데이터를 주민등록번호의 맨 앞자리의 생년을 기준으로 00년대생 부터 90년대생까지 분류 하게 되면 다음과 같이 데이터가 분류된다.
한가지 유의할 점은, LinkedList는 검색에 불리한 자료구조이기 때문에 LinkedList의 크기가 커질수록 검색속도가 떨어지게 된다.
이는, 실생활에서 하나의 책상서랍에 물건들이 많으면 많을수록 찾는데 오래걸리는 이유와 동일하다.
반면에, Array는 크기가 커져도, 원하는 요소가 몇 번째에 있는 지만 알면 아래의 공식에 의해서 빠르게 원하는 값을 찾을 수 있다.
배열의 n번째 요소의 주소 = 배열의 시작주소 + type의 size * n
그리하여, 해시테이블은 Array의 특징으로 인해 크기가 크면 클수록, LinkedList에 최소한의 데이터가 저장되기때문에 성능이 좋아진다는 결론이 나오게 된다.
3. Separate Chaining 방식의 구현
|
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
package Hash;
import java.util.LinkedList;
/**
*
* Separate Chaining기법
* Hash Collision 을 방지하기 위한 기법 중 하나로
* Array와 LinkedList를 이용하여 해시테이블을 구현한다.
*
*
* @author USER
*
*/
public class SeparateChainingHashTable {
LinkedList<Node>[] data;
//default 생성자 - LinkedList 생성
@SuppressWarnings("unchecked")
public SeparateChainingHashTable(int size) {
this.data = new LinkedList[size];
}
int getHashCode(String Key) {
int hashCode = 0;
for(char c : Key.toCharArray()) {
hashCode += c;
}
return hashCode;
}
int hashToIndex(int hashCode) {
return hashCode % data.length;
}
Node selectKey(LinkedList<Node> list, String key) {
if(list == null) {
return null;
}
for(Node node : list) {
if(key.equals(node.Key)) {
return node;
}
}
return null;
}
void put(String key, String value) {
// 1. 해시코드를 구한다.
int hashCode = getHashCode(key);
System.out.println(hashCode);
// 2. 해시코드를 인덱스 주소로 변환한다.
int index = hashToIndex(hashCode);
System.out.println(index);
// 3. 반환된 주소의 연결리스트를 list에 담는다.
LinkedList<Node> list = data[index];
System.out.println(list);
// 4. 해당 주소에 연결리스트가 없으면 새로 생성
if(list == null) {
list = new LinkedList<Node>();
data[index] = list;
}
Node node = selectKey(list, key);
// 5. 해당 연결리스트에 데이터가 있으면 마지막에 새로운 노드를 추가하여 데이터를 insert
if(node == null) {
list.addLast(new Node(key, value));
} else {
node.setValue(value);
}
}
public String get(String key) {
int hashCode = getHashCode(key);
int index = convertToIndex(hashCode);
LinkedList<Node> list = data[index];
Node node = selectKey(list, key);
return node == null ? "Not Found" : node.getValue();
}
class Node{
String Key;
String Value;
public Node(String Key, String Value) {
this.Key = Key;
this.Value = Value;
}
public String getValue() {
return this.Value;
}
public void setValue(String Value) {
this.Value = Value;
}
}
}
class Test {
public static void main(String[] args) {
SeparateChainingHashTable hashTable = new SeparateChainingHashTable(10);
hashTable.put("Alpha" , "A");
hashTable.put("Bravo" , "B");
hashTable.put("Charlie" , "C");
hashTable.put("Delta" , "D");
hashTable.put("Foxtrot" , "F");
hashTable.put("Echo" , "E");
System.out.println(hashTable.get("Alpha"));
System.out.println(hashTable.get("Bravo"));
System.out.println(hashTable.get("Charlie"));
System.out.println(hashTable.get("Delta"));
System.out.println(hashTable.get("Foxtrot"));
System.out.println(hashTable.get("Echo"));
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|