@ 해시(위키피디아)
해시는 해시 함수를 이용하여 키 값을 위치로 변환하고 이를 이용해 저장된 자료를 바로 찾아가는 계산 검색 방식이다.
저장과 검색은 아래와 같은 과정을 거친다
키 값 –> 해싱 함수 –> 해시 주소(버킷 주소) –> 해시 테이블
해싱 함수는 계산이 쉬워야 하고 충돌이 적어야 하며 해시 테이블에 고루 분포할 수 있도록 해야 한다.
자주 쓰는 것은 제산 함수(나누기) 와 승산 함수(곱하기) 이다.
서로 다른 키 값에 대해 해싱 함수가 같은 버킷 주소를 지정할 수 있다. 이런 경우를 ‘충돌’ 이라고 하며, 비어 있는 슬롯에 저장하면 되지만, 빈 슬롯이 없는 경우 오버플로우가 발생한다.
오버플로우 처리 방법은 두 가지가 있다.
1) 선형 개방 주소법(선형 조사법)
충돌이 일어난 키값을 다른 비어있는 버킷을 찾아 저장한다. 이 때 비어있는 버킷은 순차적으로 찾는다.
찾을 때도 마찬가지로 해싱 함수로 버킷을 찾아 키가 있는지 확인하고, 없으면 순차적으로 버킷을 뒤진다.
2) 체이닝
해시 테이블을 변형하여 각 버킷이 무한대의 슬롯을 갖게 한다. 오버플로우가 일어나지 않게 하는 방법이다.
소스 >>
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
|
# 해쉬 구현
# 2009-03-18, Jung-taek Lim(Heart)
class Hash
def initialize(burket_size, use_chaining)
@burket_size = burket_size
@use_chaining = use_chaining
@burket = []
end
# 제산 함수 이용
def hashing_function(key)
return key % @burket_size
end
def put(key, value)
return @use_chaining ? put_using_chaining(key, value) :
put_using_open_addressing(key, value)
end
def get(key)
return @use_chaining ? get_using_chaining(key) :
get_using_open_addressing(key)
end
private
# 선형 개방 주소법 사용
def put_using_open_addressing(key, value)
burket_idx = hashing_function(key)
(burket_idx..@burket_size - 1).each do |idx|
if nil == @burket[idx]
@burket[idx] = [key, value]
return true
end
return true if @burket[idx][0] == key
end
return false
end
def get_using_open_addressing(key)
burket_idx = hashing_function(key)
(burket_idx..@burket_size - 1).each do |idx|
return @burket[idx][1] if key == @burket[idx][0]
end
return nil
end
# 체이닝 사용
def put_using_chaining(key, value)
burket_idx = hashing_function(key)
if nil == @burket[burket_idx]
@burket[burket_idx] = [[key, value]]
else
@burket[burket_idx].push [key,value]
end
return true
end
def get_using_chaining(key)
burket_idx = hashing_function(key)
return nil if nil == @burket[burket_idx]
@burket[burket_idx].each do |set|
return set[1] if key == set[0]
end
return nil
end
end
hash = Hash.new(5, false)
hash.put(45, 1)
hash.put(9, 2)
hash.put(10, 3)
hash.put(96, 4)
hash.put(25, 5)
puts hash.get(96)
puts hash.get(25)
puts hash.get(15)
puts "---------------------------------"
hash = Hash.new(5, true)
hash.put(45, 1)
hash.put(9, 2)
hash.put(10, 3)
hash.put(96, 4)
hash.put(25, 5)
puts hash.get(96)
puts hash.get(25)
puts hash.get(15)
|
결과 >>
4
5
nil
---------------------------------
4
5
nil
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| Divide & Conquer : n 번째 피보나치 수열의 수를 구하기 (0) | 2009/05/06 |
|---|---|
| Divide & Conquer : 거듭제곱 알고리즘 (0) | 2009/05/06 |
| 해시 검색 - in Ruby (0) | 2009/03/18 |
| 이진 검색 - in Ruby (0) | 2009/03/18 |
| 트리 정렬 - in Ruby (0) | 2009/03/18 |
| 힙 정렬 - in Ruby (0) | 2009/03/18 |
