1. 탐색이란?
■ 탐색은 레코드들의 집합인 테이블(table)에서 원하는 탐색키(search key)를 가진 레코드를 찾는 작업이다. 탐색키는 레코드가 갖는 키(key)로서, 이 키를 통해 레코드들을 서로 구별한다.
■ 간단한 탐색 알고리즘으로 순차 탐색, 이진 탐색, 보간 탐색이 있으며, 빠른 탐색을 위한 자료구조로 맵과 해쉬(hash) 테이블이 있다.
2. 순차 탐색(Sequential Search)
■ 순차 탐색은 정렬되지 않은 테이블에서도 적용 가능한 방법이다.
■ 탐색을 위한 레코드들이 배열에 저장되어 있으면, 순차 탐색은 정렬되지 않은 배열을 처음부터 마지막까지 하니씩 순서대로 검사하여 원하는 레코드를 탐색하는 방법이다.
■ 예를 들어 [5, 3, 8, 4, 9, 1]에서 '8'을 찾는다고 할 때,
이렇게 탐색에 성공하면 해당 항목의 위치를 알려주는 인덱스 '2'를 반환한다.
- 반면, 배열에 없는 '2'를 찾는다고 할 때, 다음과 같이 더 이상 탐색할 항목이 없어서 탐색에 실패한다.
■ 이처럼 처음부터 하나씩 검사하기 때문에, 최선의 경우는 찾고자 하는 항목이 첫 번째 위치에 있는 경우이고, 최악의 경우는 찾고자 하는 항목이 마지막 위치에 있거나, 배열에 아예 없는 경우이다.
■ 최악의 경우 \( n \)번 비교를 해야 한다. 따라서 항목이 탐색될 확률이 동일하다면 평균 비교 횟수는 \( (1 + 2 + 3 + \ldots + n) / n = (n + 1) / 2 \) 번이다. 결국, 순차 탐색의 시간 복잡도는 \( O(n) \)이 된다.
2.1 순차 탐색 구현
■ 순차 탐색은 탐색 대상인 리스트와 탐색키, 그리고 리스트에서의 탐색 범위를 매개변수로 전달받아, 탐색 범위에서 탐색을 성공하면 그 항목의 인덱스를 반환하고, 탐색을 실패하면 None을 반환하게 만들면 된다.
def SequentialSearch(lst, key, low, high):
for i in range(low, high+1):
if lst[i] == key:
return i
return Nonelst = [5, 3, 8, 4, 9, 1]
SequentialSearch(lst, 8, 0, len(lst)-1)
```#결과#```
2
````````````
print(SequentialSearch(lst, 2, 0, len(lst)-1))
```#결과#```
None
````````````
3. 이진 탐색(Binary Search)
■ 이진 탐색은 정렬된 배열의 탐색에 적합한 방법이다.
■ 이진 탐색은 배열 중앙에 있는 값을 조사해서 찾고자 하는 항목이 왼쪽에 있는지 오른쪽에 있는지 판단해서, 왼쪽 부분 배열에 있으면 오른쪽을 탐색하지 않고, 오른쪽 부분 배열에 있다면 왼쪽을 탐색하지 않는 식으로 매 단계마다 탐색 범위를 반으로 줄여가며 탐색을 진행한다.
■ 예를 들어 사전에서 10억 개의 단어 중 특정 단어를 탐색한다면, 순차 탐색은 평균 \( \dfrac{\text{10억+1}}{2} \) ≒ 5억 번의 비교가 필요하지만, 이진 탐색은 \(\log_2 \text{10억} \) ≒ 29.897.... 약 30번의 비교만 하면 된다.
- 찾고자 하는 단어가 현재 페이지 앞에 있는지 뒤에 있는지 확인하고 단어가 있는 부분만 다시 탐색하기 때문이다.
■ 예를 들어 정렬된 배열 [2, 5, 6, 9, 10, 12, 14, 17, 20, 22]에서 이진 탐색으로 '14'를 탐색한다면, 먼저 탐색 범위 low에서 high 사이의 중앙 값 middle을 찾아야 한다.
■ middle의 인덱스는 \( \dfrac{\text{low index + high index}}{2} = \dfrac{0 + 9}{2} = 4.5 \) \( \rightarrow 4 \)가 된다.
■ middle의 값 10은 탐색키의 값 '14'보다 작다. 즉, 정렬된 배열이므로 low와 middle 사이에는 '14'가 없는 것이다.
■ 그리고 다음 탐색을 위해, 다음 탐색 범위는 middle의 다음 위치부터 low가 된다.
- 새로운 low의 인덱스는 middle의 인덱스 + 1 = 5가 되므로 새로운 middle의 인덱스는 \( \dfrac{\text{5 + 9}}{2} = 7 \)이 된다.
■ 새로운 middle의 값이 '14'보다 크므로 middle과 high 사이에는 찾고자 하는 '14'가 없는 것이다. 따라서 탐색 범위를 줄이기 위해 middle의 이전의 위치를 high로 설정한다. 그러면 새로운 미들의 인덱스는 \(
\dfrac{5 + 6}{2} = 5.5 \rightarrow 5
\)가 된다.
■ middle의 값이 '14'보다 작으므로 새로운 low의 인덱스는 middle의 인덱스 + 1이므로 6이 된다.
■ middle의 인덱스는 6이 되고 low와 high의 인덱스도 6이 되며, middle의 값이 '14'로 찾고자 하는 값이므로 탐색 성공이다.
■ 즉, low와 high의 인덱스가 같은 항목을 가리키며 비교하고자 하는 항목이 1개가 남는 경우, 남은 항목 1개가 찾고자 한 값이라는 것을 알 수 있다.
■ 만약, 배열에 없는 값 '13'을 탐색하려 한다면 위의 상황에서 다시 high의 인덱스가 middle의 인덱스 - 1이 되며, low와 high가 역전된다.
■ 즉, 찾고자 하는 값이 배열에 없다면 low와 high가 역전된다는 것을 알 수 있다.
3.1 이진 탐색 구현
■ 이진 탐색을 구현할 때, 주의해야 할 점은 바로 middle의 인덱스를 계산하는 부분이다.
■ 위의 middle 예시를 파이썬에서 \( '(low + high) / 2' \) 이렇게 '/' 연산자를 이용할 경우, middle의 인덱스는 4.5가 된다.
■ 실수는 인덱스로 사용할 수 없으므로 계산 결과가 정수가 될 수 있도록 '//' 연산자를 이용해야 한다.
■ 파이썬에서 '//' 연산자를 이용해 이진 탐색을 구현하면 다음과 같다.
def BinarySearch(lst, key, low, high):
while low <= high: # 종료 조건 low와 high 역전
middle = (low + high) // 2 # 인덱스는 4.5같이 실수가 될 수 없고 4처럼 정수 형태가 되야 하므로 // 연산자 사용
# print(f'low, middle, high index{low}, {middle}, {high}\n')
if key == lst[middle]: # 찾는 값이 middle이 가리키고 있다면
return middle # 탐색 성공
elif key > lst[middle]: # 찾는 값이 middle이 가리키고 있는 값보다 크다면
low = middle + 1
# print(f'change low index: {low}')
else: # 찾는 값이 middle이 가리키고 있는 값보다 작다면
high = middle - 1
# print(f'change high index: {high}')
return None # 탐색 실패lst = [2, 5, 6, 9, 10, 12, 14, 17, 20, 22]
print(BinarySearch(lst, 14, 0, len(lst)-1))
```#결과#```
low, middle, high index0, 4, 9
change low index: 5
low, middle, high index5, 7, 9
change high index: 6
low, middle, high index5, 5, 6
change low index: 6
low, middle, high index6, 6, 6
6
`````````````
print(BinarySearch(lst, 13, 0, len(lst)-1))
```#결과#```
low, middle, high index0, 4, 9
change low index: 5
low, middle, high index5, 7, 9
change high index: 6
low, middle, high index5, 5, 6
change low index: 6
low, middle, high index6, 6, 6
change high index: 5
None
`````````````■ 이진 탐색은 재귀적인 구조를 가지므로, 위의 반복 구조 외에도 다음과 같이 순환 호출을 이용해서 구현할 수 있다.
def BinarySearch2(lst, key, low, high):
if low <= high: # 종료 조건
middle = (low + high) // 2
# print(f'low, middle, high index{low}, {middle}, {high}\n')
if key == lst[middle]:
return middle # 탐색 성공
elif key > lst[middle]:
low = middle + 1
return BinarySearch2(lst, key, low, high)
else:
high = middle - 1
return BinarySearch2(lst, key, low, high)
return None # 탐색 실패print(BinarySearch2(lst, 14, 0, len(lst)-1))
```#결과#```
low, middle, high index0, 4, 9
low, middle, high index5, 7, 9
low, middle, high index5, 5, 6
low, middle, high index6, 6, 6
6
`````````````
print(BinarySearch2(lst, 13, 0, len(lst)-1))
```#결과#```
low, middle, high index0, 4, 9
low, middle, high index5, 7, 9
low, middle, high index5, 5, 6
low, middle, high index6, 6, 6
None
`````````````■ 이처럼 이진 탐색은 매 단계에서 탐색 범위가 반으로 줄어든다.
■ 따라서 시간 복잡도는 \( O(\log_2 n \)으로 효율적인 방법이다.
■ 단, 이진 탐색을 적용하기 전에 반드시 배열이 정렬되어 있어야 하므로, 배열의 정렬이 깨지게 되는 항목의 삽입, 삭제가 빈번한 경우에는 적합하지 않다.
4. 보간 탐색(Interpolation Search)
■ 보간 탐색은 이진 탐색의 일종으로 배열이 정렬된 상태일 때 값을 탐색하는데, 탐색키가 존재할 위치를 예측하여 탐색하는 방법이다.
■ 예를 들어 사전에서 'a'로 시작하는 단어나 'y'로 시작하는 단어를 탐색할 때, 이진 탐색은 무조건 middle, 중앙 값부터 확인한다.
■ 반면, 보간 탐색은 'a'로 시작하는 단어는 사전의 앞부분에서, 'y'로 시작하는 단어는 뒷부분에서 찾는데, 이는 찾고자 하는 값이 어디 있는지 예측이 가능하기 때문이다.
ㅊ 보간 탐색은 이진 탐색과 달리 배열을 불균등하게 분할하여 탐색한다. 이는 탐색 값과 위치는 비례한다는 가정을 기반으로, 탐색 위치 middle을 결정할 때 찾고자 하는 키 값의 위치에 더 가깝게 접근하기 위해 가중치를 부여하기 때문이다.
■ 예를 들어 [1, 2, 3, 4, 5, ..., 100, 1000, 10000]에서 찾고자 하는 값이 'k'라 할 때, 탐색 값과 위치가 다음과 같이 비례한다고 가정한다.
■ 찾고자 하는 킷값이 \( k \)라 할 때, 보간 탐색의 탐색 위치 middle은 \( low + (high - low) \cdot \dfrac{k - A[low]}{A[high] - A[low]} \)이다.
- \( \dfrac{k - A[low]}{A[high] - A[low]} \)으로 key가 전체 구간 내 어디에 위치하는지 비율을 구하고
- 이 비율에 \( (high - low) \)를 곱해 위치를 계산하고
- 마지막으로 \( low \)를 더해 전체 배열에서의 예상 위치를 계산한다.
4.1 보간 탐색 구현
■ 보간 탐색은 이진 탐색의 middle 계산 코드를 위의 보간 탐색 middle 계산으로 변경해 주면 된다.
middle = int(low+(high-low)*(key-lst[low])/(lst[high]-lst[low]))def InterpolationSearch(lst, key, low, high):
while low <= high:
middle = int(low+(high-low)*(key-lst[low])/(lst[high]-lst[low]))
print(f'low, middle, high index{low}, {middle}, {high}\n')
if key == lst[middle]:
return middle
elif key > lst[middle]:
low = middle + 1
print(f'change low index: {low}')
else:
high = middle - 1
print(f'change high index: {high}')
return Nonelst = [2, 5, 6, 9, 10, 12, 14, 17, 20, 22]
print(InterpolationSearch(lst, 14, 0, len(lst)-1))
```#결과#```
low, middle, high index0, 5, 9
change low index: 6
low, middle, high index6, 6, 9
6
`````````````
lst = list(range(1, 25)) # range 이용해 간격 일정한 균등 리스트
print(InterpolationSearch(lst, 14, 0, len(lst)-1)) # 이렇게 데이터가 균등하게 분포되어 있으면 효율적
```#결과#```
low, middle, high index0, 13, 23
13
````````````■ 보간 탐색의 시간 복잡도는 이진 탐색과 같은 \( O(\log_2 n) \)이며, 많은 데이터가 균등하게 분포되어 있을 때 훨씬 효율적인 방법이다.
5. 맵(map)
■ 맵 또는 딕셔너리는 찾고자 하는 key가 있을 때 가능한 한 번에, 즉 \( O(1) \)로 찾고자 하는 key에 대응되는 value를 찾고자 하는 자료구조이다.
■ 맵은 엔트리(entry)라 불리는 키를 가진 레코드(keyed record)의 집합이다.
- 엔트리는 '키(key)'와 '값(value)'이라는 두 개의 필드를 가진다.
- '키'는 영어 단어와 같은 레코드를 구분할 수 있는 탐색키이고
- '값'은 영어 단어의 의미와 같이 탐색키와 관련된 값이다.
■ 즉, 맵은 키-값 쌍으로 구성된 엔트리의 집합이다.
■ 예를 들어 word = {'red':'빨강', 'black':'검정', 'blue':'파랑'}과 같이 key가 'red', 'black', 'blue' 일때, 각 key의 value는 '빨강', '검정', '파랑'이다.
■ 딕셔너리는 맵을 구현한 하나의 예이다. 위의 예시와 같이 파이썬의 딕셔너리는 키-값 쌍으로 이루어진 엔트리의 집합이기 때문이다.
5.1 맵 구현 방법
■ 맵을 구현하는 방법은 ① 리스트를 이용하는 방법과 ② 해싱(hashing) 구조를 이용하는 방법이 있다.
■ key가 숫자로 표현된 경우, key 값을 index로 하는 배열(리스트)을 이용하는 것이 가장 간단한 방법이다.
■ 리스트를 이용하는 방법은 예를 들어 다음과 같은 테이블이 있을 때, 길이 30의 리스트로 만들어서, 숫자 key인 ID를 리스트의 인덱스로 사용해 각 인덱스의 값을 저장한다.
■ 이렇게 리스트를 이용하면, 만약 key 값이 '10'인 레코드를 찾고 싶다면 index 10에 바로 접근 \( (O(1)) \)해서 그 값을 불러올 수 있다.
■ 숫자 key가 아닌 일반적인 경우 맵을 구현하는 가장 좋은 방법은 해싱 구조를 이용하는 것이다.
5.2 맵 구현 - 엔트리
■ 맵은 키-값으로 구성된 엔트리의 집합이다. 따라서 먼저 엔트리부터 클래스로 구현한다면 다음과 같다.
class Entry:
def __init__(self, key, value):
self.key = key
self.value = value
def __str__(self):
return f'({self.key}, {self.value})'
5.3 순차 탐색 맵 구현
■ 맵은 엔트리의 집합이다. 따라서 엔트리를 저장할 테이블이 필요하다.
■ 테이블을 리스트로 만든다면, 테이블에 있는 레코드의 개수와 테이블에 있는 모든 엔트리를 확인하는 메서드는 다음과 같이 간단하게 구현할 수 있다.
class SequentialMap:
def __init__(self):
self.table = []
def size(self):
return len(self.table)
def display_map(self):
for entry in self.table:
print(entry, end = ' ')■ 탐색 연산은 위에서 정의한 시간 복잡도가 \( O(n) \)인 순차 탐색 함수를 호출하기만 하면 된다.
def SequentialSearch(lst, key, low, high):
for i in range(low, high+1):
if lst[i].key == key: # 순차 탐색 맵 클래스에서 사용하기 위해 수정
return i
return None■ 순차 탐색은 정렬되지 않은 배열에서도 사용할 수 있는 방법이다. 따라서 삽입 시, 리스트의 아무 곳에나 엔트리를 넣어도 된다.
■ 리스트를 사용하므로 append( )를 사용하면 삽입 연산의 시간 복잡도가 \( O(1) \)이 된다.
def insert(self, key, value):
self.table.append(Entry(key, value))■ 삭제 연산은 삭제할 위치를 찾아야 하므로 리스트의 인덱스와 pop( )을 이용하면 된다.
■ pop( ) 또는 pop(-1)은 리스트의 맨 마지막 항목을 제거해 삭제 시, 다른 항목들이 이동할 필요가 없어 시간 복잡도는 \( O(1) \)이지만
■ pop(\( i \)) (\( i \)는 임의의 인덱스)는 \( i \)번 째 항목을 제거하면, \( i \) 이후의 모든 항목들이 이동해야 한다. 따라서 삭제 연산의 시간 복잡도는 \( O(n) \)이다.
- 예를 들어 첫 번째 항목을 제거하면 그 뒤의 모든 항목들은 한 칸씩 앞으로 이동해야 한다.
def delete(self, key):
for i in range(self.size()):
if self.table[i].key == key:
return self.table.pop(i)
return None- 이를 종합하면 순차 탐색 맵 구현은 다음과 같다.
class SequentialMap:
def __init__(self):
self.table = []
def size(self):
return len(self.table)
def display_map(self):
for entry in self.table:
print(entry, end = ' ')
def search(self, key):
index = SequentialSearch(self.table, key, 0, self.size() - 1)
if index is None:
return None
else:
return self.table[index]
def insert(self, key, value):
self.table.append(Entry(key, value))
def delete(self, key):
for i in range(self.size()):
if self.table[i].key == key:
return self.table.pop(i)
return NoneMap = SequentialMap()
Map.insert('apple', 1000)
Map.insert('orange', 1500)
Map.insert('apple mango', 2000)
Map.insert('mango', 1700)
Map.table[0].key, Map.table[0].value
```#결과#```
('apple', 1000)
````````````
Map.display_map()
```#결과#```
(apple, 1000) (orange, 1500) (apple mango, 2000) (mango, 1700)
````````````
print(Map.search('apple mango'))
```#결과#```
(apple mango, 2000)
````````````
Map.size()
```#결과#```
4
````````````
print(Map.delete('apple mango'))
```#결과#```
(apple mango, 2000)
````````````
print(Map.delete('banana'))
```#결과#```
None
````````````
Map.display_map()
```#결과#```
(apple, 1000) (orange, 1500) (mango, 1700)
````````````
5.4 이진 탐색 맵 구현
■ 이진 탐색은 정렬된 배열의 탐색에 적합한 방법이다. 따라서 이진 탐색의 삽입 연산은 엔트리의 킷값 크기를 보고 올바른 위치를 찾아 삽입해야 하므로 삽입 연산의 시간 복잡도는 \( O(n) \)이 된다.
■ 삭제 연산은 순차 탐색 맵의 삭제 연산과 동일하며, 탐색 연산은 위에서 정의한 이진 탐색 함수를 사용한다면 탐색 연산의 시간 복잡도는 \( O(\log_2 n) \)이 된다.
def BinarySearch(lst, key, low, high):
while low <= high:
middle = (low + high) // 2
# print(f'low, middle, high index{low}, {middle}, {high}\n')
if key == lst[middle].key: # 이진 탐색 맵 클래스에서 사용하기 위해 수정
return middle
elif key > lst[middle].key: # 이진 탐색 맵 클래스에서 사용하기 위해 수정
low = middle + 1
# print(f'change low index: {low}')
else:
high = middle - 1
# print(f'change high index: {high}')
return None
class BinarySearchMap(SequentialMap):
def __init__(self):
super().__init__()
def search(self, key, low=None, high=None):
if low is None:
low = 0
if high is None:
high = self.size() - 1
index = BinarySearch(self.table, key, low, high)
if index is None:
return None
else:
return self.table[index]
def insert(self, key, value, low=None, high=None):
if low is None:
low = 0
if high is None:
high = self.size() - 1
insert_pos = 0 # 삽입 위치를 저장할 변수
while low <= high:
middle = (low + high) // 2
if key < self.table[middle].key:
high = middle - 1
else:
low = middle + 1
insert_pos = low # 반복문이 끝나면 low는 삽입 위치가 된다.
self.table.insert(insert_pos, Entry(key, value)) # 리스트의 insert 함수를 사용해서 올바른 위치에 삽입Map_2 = BinarySearchMap()
Map_2.insert('apple', 1000)
Map_2.insert('orange', 1500)
Map_2.insert('apple mango', 2000)
Map_2.insert('mango', 1700)
Map_2.table[0].key, Map_2.table[0].value
```#결과#```
('apple', 1000)
````````````
Map_2.display_map()
```#결과#```
(apple, 1000) (apple mango, 2000) (mango, 1700) (orange, 1500)
````````````
Map_2.insert('banana', 1200)
Map_2.display_map()
```#결과#```
(apple, 1000) (apple mango, 2000) (banana, 1200) (mango, 1700) (orange, 1500)
````````````
print(Map_2.delete('apple mango'))
```#결과#```
(apple mango, 2000)
````````````
Map_2.display_map()
```#결과#```
(apple, 1000) (banana, 1200) (mango, 1700) (orange, 1500)
````````````
print(Map.search('mango'))
```#결과#```
(mango, 1700)
````````````
6. 고급 탐색 구조 - 해싱
■ 해싱은 위의 다른 방법들처럼 레코드의 key 값을 비교하지 않고 key 값에 산술적인 연산으로 레코드가 저장될 위치를 직접 계산하는 방법이다.
■ key 값으로부터 레코드가 저장될 위치를 계산하는 함수를 해시 함수(hash function)라고 하며, 이 해시 함수에 의해 계산된 위치, 주소에 레코드를 저장한 테이블을 해시 테이블(hash table)이라고 한다.
■ 즉, 해시 테이블은 key 값의 연산에 의해 직접 접근이 가능한 구조이다.
6.1 해싱의 구조
■ 해싱의 구조는 크게 해시 함수, 해시 테이블이며, 해시 테이블은 버킷(bucket)과 슬롯(slot)으로 구성되어 있다.
■ 일반적으로 해시 테이블에서는 하나의 버킷에 여러 개의 슬롯이 있으며, 하나의 슬롯에는 하나의 레코드를 저장할 수 있다.
■ 그리고 각각의 버킷에 해당하는 해시 주소를 가지고 있는데, 해시 함수 \( h(key) \) 값이 해시 주소가 되며, 이 해시 주소인 \( h(key) \) 값을 index로 사용해서 테이블에 접근한다.
■ 이렇게 해시 함수로 탐색키 값에 대한 연산을 통해 해시 주소를 계산해서 해시 테이블에 바로 접근하기 때문에 접근하는 연산의 시간은 \( O(1) \)이다.
■ 위의 그림처럼 해시 함수로 계산된 해시 주소를 통해 해시 테이블에 접근하기 때문에 탐색과 삽입, 삭제 연산은 파이썬 딕셔너리의 탐색, 삽입, 삭제 연산이 모두 key 값을 이용해 연산하는 것과 같이 모두 해시 주소를 이용하는 구조이다.
■ 해시 함수는 탐색키를 작은 정수로 대응시켜 주는 역할을 수행한다. 탐색키를 문자열, 실수, 너무 큰 정수 값을 사용했을 때, 메모리가 부족해지는 상황을 방지하기 위해서이다.
6.2 충돌(Collision)과 오버플로(Overflow)
■ key 값이 해시 함수의 입력으로 들어오면, 해시 함수는 \( h(key) \)를 출력하며, \( h(key) \)는 해시 주소가 되고 해시 주소를 인덱스로 사용하여 항목에 접근하는데
■ 이때, 버킷이 충분하지 않으면 서로 다른 key가 해시 함수에 의해 같은 주소로 계산되는 상황이 발생할 수 있다. 이 상황을 '충돌'이라고 한다.
■ 그리고 충돌이 슬롯 수보다 더 많이 발생할 수 있는데, 이 상황을 오버플로라고 한다.
■ 충돌이 슬롯 수보다 더 많이 발생하게 된다는 것은 해당 버킷에 충돌된 레코드를 저장할 곳이 없다는 것이다. 따라서 해싱에서는 오버플로 문제를 반드시 해결해야 한다.
■ 예를 들어 key 값이 'apple', 'banana', 'apple mango', 'mango'일 때, 해시 함수의 계산 결과가 \(
h(\text{apple}) = 5, \, h(\text{banana}) = 2, \, h(\text{apple mango}) = 3, \, h(\text{mango}) = 3
\)이라 하면
- 만약, 해시 주소가 3인 버킷에 슬롯이 한 개만 있다면 이렇게 key 'apple mango'와 'mango'의 해시 주소가 동일하게 계산된 경우 충돌이 발생한다.
- 그리고 'key = apple mango'의 레코드가 슬롯에 들어가 있어 'key = mango'는 해당 버킷의 다른 빈 슬롯이 있는지 검사하지만, 슬롯이 한 개뿐이라 다시 'key = apple mango'의 슬롯에 돌아가게 되어 충돌을 발생시킨다. 이런 상황을 오버플로라고 한다.
- 슬롯의 수가 2개 였다면, 'mango'의 레코드를 남는 하나의 슬롯에 저장할 수 있으므로 이런 충돌 문제가 발생하지 않았을 것이다.
■ 충돌이 절대 발생하지 않는 이상적인 해싱이라면 시간 복잡도는 \( O(1) \)이 가능하지만, 충돌과 오버플로가 빈번하게 발생하면 이상적인 경우의 \( O(1) \)보다는 성능이 떨어지게 된다.
■ 이런 오버플로를 피하기 위해 해시 테이블의 크기를 충분히 크게 만들면, 그만큼의 메모리가 필요하다는 단점이 있다. 따라서 해싱 함수를 개선해 충돌과 오버플로를 방지하는 것이 더 적합하며, 이런 방법에는 선형 조사법을 이용해 오버플로를 처리하는 방법이 있다.
6.3 선형 조사법(Linear Probing)에 의한 오버플로 처리
■ 선형 조사법은 충돌이 발생할 경우 해시 테이블의 다음 위치에 저장하는 방법이다. 즉, 해싱 함수로 계산된 해시 주소가 가리키는 버킷에 빈 슬롯이 없다면, 그 다음 버킷에 빈 슬롯이 있는지 찾는 방법이다.
■ 만약 해시 테이블의 k 번째 위치인 ht[k]에서 충돌이 발생했다면, 다음 위치인 ht[k+1]부터 순서대로 빈 슬롯이 있는지 조사하고 빈 슬롯이 있다면 그곳에 저장하는 방법으로, 빈 공간을 찾을 때까지 계속되며 테이블 끝에 도달하면 다시 테이블의 처음으로 이동한다.
■ 만약, 처음 충돌이 발생한 곳으로 다시 돌아온다면, 이는 해시 테이블이 모두 찬 상태임을 의미한다.
6.3.1 선형 조사 : 삽입 연산
■ 예를 들어 해시 테이블의 크기 M = 11이라 할 때 key 값이 12, 74, 54, 9, 49, 51, 71, 24, 17인 레코드를 선형 조사법으로 저장해 보자.
■ key 값을 작은 정수로 대응시키기 위해 key 값을 M(해시 테이블의 크기)으로 나머지 연산한 계산 결과를 해시 주소로 사용한다. 즉, 해시 함수는 \( h(key) = key \text{ % } M \)이므로 각 키의 해시 주소는 다음과 같이 계산된다.
- 각 버킷에 슬롯이 한 개라는 가정 하에 12, 74, 54, 9, 49, 51 까지의 삽입에서는 동일한 해시 주소가 없으므로 충돌이 발생하지 않는다.
- '71' 삽입 시, 이미 'h(key) = 5' 자리에 '49'가 저장되어 있어 충돌이 발생한다. 선형 조사법에서는 충돌이 발생한 위치 h(key) = 5' 다음 버킷에 빈 공간이 있으면 그 버킷에 '71'을 삽입한다. 따라서 '6' 위치에 '71'을 저장한다.
- 그리고 '24'를 삽입한 뒤, '17'을 삽입할 때 위치 '6'에서 다시 충돌이 발생한다. 뒤 쪽 남는 버킷이 없으므로 해시 테이블 처음으로 돌아가서 다시 빈 공간이 있는지 조사한다. 빈 공간을 찾으면 해당 버킷에 '17'을 삽입한다.
■ 위의 예시에서 '17'을 삽입할 때 위치 '6'에 자리가 없어 다음 버킷을 조사했는데, 위치'7'에서도 '51'이 이미 저장되어 있어 충돌이 발생했다. 위치 '8', '9', '10', 마지막 버킷까지 빈 곳이 없어 충돌이 반복해서 발생했다.
■ 충돌이 발생한 위치에 이렇게 항목들이 집중돼서 저장되는 현상을 볼 수 있다. 이를 군집화(clustering) 현상이라 하는데, 이렇게 항목들이 군집화되어 있는 경우 충돌이 반복해서 발생해, 끝에 도달할 때까지 다음 버킷을 순서대로 방문하기 때문에 비효율적으로 탐색이 이루어진다.
6.3.2 선형 조사 : 탐색 연산
■ 탐색 연산도 삽입 연산과 비슷한 과정을 거친다. 탐색한 위치에 찾는 값과 다른 값이 있으면 다음 버킷으로 이동한다. 이 과정은 원하는 값을 찾거나 빈 버킷을 만나거나 모든 버킷을 검사할 때까지 진행된다.
■ 탐색한 위치에 찾는 값 대신 다른 값이 있다면, 이는 삽입 연산 과정에서 충돌이 발생해 다른 위치에 찾고자 하는 값이 저장되었기 때문이다.
■ 예를 들어 '71'을 탐색하려면 h(71) = 71 % M(11) = 5. 위치 '5'를 보면 된다. 그러나 위치 '5'에는 다른 값이 저장되어 있으므로 다음 버킷으로 이동한다.
이동한 버킷에 위의 그림같이 찾고자 하는 값이 있다면 탐색 성공이다.
■ 반면, '33'을 탐색할 경우 h(33) = 33 % 11 = 0, 위치 '0'에 다른 값이 있으므로 이동한다. 다음 버킷들로 이동해도 '33'은 없고 위와 같이 빈 버킷을 만나게 된다. 만약, 위치 5에서 탐색을 시작했더라도 '33'이 없으므로 해시 테이블의 처음으로 돌아와서 결국에는 빈 버킷을 만나게 된다.
이렇게 탐색 연산 과정에서 다음 버킷으로 이동하다가 빈 버킷을 만나게 되는 이유는 찾는 값이 해시 테이블에 존재하지 않기 때문이다. 따라서 빈 버킷을 만나면 탐색 실패이다.
6.3.3 선형 조사 : 삭제 연산
■ 선형 조사법에서 항목이 삭제되면 빈 버킷이 되므로 탐색이 실패할 수 있다.
■ 예를 들어 위의 예에서 '49'가 삭제된 상태에서 '71'을 탐색하려고 하면,
빈 버킷을 만나게 되므로 탐색이 실패하여 탐색이 종료된다. 따라서 탐색 연산의 예시처럼 위치 '6'의 버킷으로 이동할 수 없다.
■ 이런 오류를 방지하기 위해 빈 버킷을 두 가지 유형으로 분류해야 한다.
- 첫 번째 유형은 처음부터 한 번도 사용하지 않은 버킷
- 두 번째 유형은 사용되었다가 값이 삭제되어 비어있는 버킷이다.
■ 예를 들어 두 번째 유형의 버킷을 △로 표기하여, △ 버킷을 만난 경우에는 다음 버킷으로 이동할 수 있게 하고 첫 번째 유형의 버킷을 만날 때 탐색이 중단되는 방식으로 구현하면, 중간에 항목이 삭제되어 빈 버킷이 생기는 경우에도 탐색의 오류가 발생하지 않고 원하는 위치까지 탐색을 수행할 수 있다.
class LinearProbingHashTable:
def __init__(self, M):
self.size = M
self.table = ['EMPTY'] * self.size # 모든 버킷을 'EMPTY'로 초기화
def hash_function(self, key): # 해시 함수
return key % self.size
def insert(self, key):
index = self.hash_function(key) # 해시 주소 계산, 현재 키를 삽입하려는 위치
original_index = index # 시작 위치를 지정해 전체를 순회했는지 확인하기 위해 사용
first_deleted = -1 # 초기화, DELETED 버킷의 첫 번째 위치를 저장. 아직 DELETED 버킷을 찾지 못했음을 의미
while True:
if self.table[index] == 'EMPTY': # 현재 버킷이 빈 버킷일 때
if first_deleted != -1: # DELETED != 1, 즉 DELETED 버킷을 발견하면
self.table[first_deleted] = key # 키를 DELETED 버킷에 삽입
else: # DELETED 버킷이 아니라면, 즉 그냥 EMPTY 버킷이어도
self.table[index] = key # 키를 현재 index에 삽입
return True # 삽입 후 True를 반환해 삽입 성공을 알림
elif self.table[index] == 'DELETED': # 현재 빈 버킷이 두 번째 유형의 빈 버킷 DELETE인데
if first_deleted == -1: # 아직 DELETED 버킷을 발견하지 못했다면
first_deleted = index # 현재 인덱스를 DELETED 버킷 인덱스에 저장
elif self.table[index] == key: # 현재 버킷에 이미 동일한 키가 존재하면
return False # 이미 키가 존재하므로 중복 삽입을 방지하기 위해 False를 반환
index = (index + 1) % self.size # 다음으로 이동
if index == original_index: # 하다가 삽입을 시작하려 한 index를 다시 만난다면
return False # 테이블이 가득 찬 것을 의미
def search(self, key):
index = self.hash_function(key)
original_index = index
while True:
if self.table[index] == 'EMPTY': # 한 번도 사용되지 않은 빈 버킷 첫 번째 유형을 만나면
return None # 탐색 종료
elif self.table[index] == key: # 그렇지 않으면
return index # 찾고자 하는 항목의 인덱스 반환, 즉 # 'DELETED'인 경우에도 계속 탐색
index = (index + 1) % self.size
if index == original_index: # 다시 탐색 시작 위치를 만나면
return None # 찾고자 하는 항목은 테이블에 없는 것
def delete(self, key):
index = self.search(key)
if index != -1:
self.table[index] = 'DELETED' # 'DELETED' 문자열을 넣어 삭제
else:
return False
def display(self):
for i, key in enumerate(self.table):
print(f'Bucket {i}: {key}')ht = LinearProbingHashTable(11)
for i in [12, 74, 54, 9, 49, 51, 71, 24, 17]:
ht.insert(i)
ht.display()
```#결과#```
Bucket 0: 17
Bucket 1: 12
Bucket 2: 24
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 49
Bucket 6: 71
Bucket 7: 51
Bucket 8: 74
Bucket 9: 9
Bucket 10: 54
```````````
print(ht.search(71)); print(ht.search(33))
```#결과#```
6
None
```````````
ht.delete(49)
ht.display()
```#결과#```
Bucket 0: 17
Bucket 1: 12
Bucket 2: 24
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: DELETED
Bucket 6: 71
Bucket 7: 51
Bucket 8: 74
Bucket 9: 9
Bucket 10: 54
```````````
ht.search(71)
```#결과#```
6
````````````
ht.insert(49)
ht.display()
```#결과#```
Bucket 0: 17
Bucket 1: 12
Bucket 2: 24
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 49
Bucket 6: 71
Bucket 7: 51
Bucket 8: 74
Bucket 9: 9
Bucket 10: 54
`````````````6.4 선형 조사 군집화 완화 방법
■ 충돌이 발생했을 때 군집화를 완화하는 방법으로 이차 조사법(quadratic probing)과 이중 해싱법(double hashing)이 있다.
■ 이차 조사법은 충돌이 발생하면 \( h(k), h(k)+1, h(k)+2, \ldots \) 처럼 충돌 위치 바로 다음 버킷으로 이동하는 것이 아닌, 더 멀리 있는 버킷으로 이동하기 위해 \(
(h(k) + i\text{*}i) \text{ % } M \quad (i = 0, 1, 2, \ldots, M - 1)
\)으로 위치를 조사한다.
■ 이 식을 사용하면, 조사되는 위치는 \(
h(k), \ h(k) + 1, \ h(k) + 4, \ h(k) + 9, \ \ldots
\)가 되기 때문에 바로 다음 버킷으로 이동하는 방식에 비해 군집화 현상을 완화시킬 수 있다.
■ 단, 1차 군집화를 완화시킬 수는 있지만, 결국 같은 순서로 빈 버킷을 조사하기 때문에 2차 군집화 현상이 발생할 수 있다. 이 문제는 이중 해싱법으로 해결할 수 있다.
■ 이중 해싱법은 재해싱(rehashing)이라고도 하는데, 충돌이 발생해서 충돌한 항목을 저장할 다음 위치를 결정할 때, 기존 해시 함수와 다른 해시 함수를 사용해 저장할 다음 위치를 계산하는 방법으로, 해시 함수 값(= 해시 주소)이 같아도 탐색키가 다르다면 서로 다른 조사 순서를 갖도록 하여 2차 군집화를 완화할 수 있는 방법이다.
■ 예를 들어 \( h(key) \)라는 해시 함수를 이용해 해시 주소를 계산했는데, 충돌이 발생할 경우 2 번째 해시 함수 \( h_2(key) \)를 이용해서 다른 해시 주소를 찾아 삽입, 탐색 등이 가능한지 확인한다.
■ 이렇게 두 번째에 아예 다른 별개의 해시 함수를 적용해서 충돌이 발생한 2개 항목의 두 키 값이 다른 해시 주소를 가질 수 있도록 만들어 줄 수 있다.
6.4.1 이차 조사법 구현
class QuadraticProbingHashTable(LinearProbingHashTable):
def __init__(self, M):
super().__init__(M)
def insert(self, key):
index = self.hash_function(key)
i = 0
first_deleted = -1
while i < self.size: # i는 0부터 M-1까지
new_index = (index + i*i) % self.size # 이차 조사법
if self.table[new_index] == 'EMPTY':
if first_deleted != -1:
self.table[first_deleted] = key
else:
self.table[new_index] = key
return True
elif self.table[new_index] == 'DELETED':
if first_deleted == -1:
first_deleted = new_index
elif self.table[new_index] == key:
return False
self.display()
print('---'*10)
i += 1
return False # 해시 테이블이 가득 참
def search(self, key):
index = self.hash_function(key)
i = 0
while i < self.size:
new_index = (index + i * i) % self.size
if self.table[new_index] == 'EMPTY': # 탐색 도중 EMPTY 버킷을 만남
return None
elif self.table[new_index] == key:
return new_index # 키를 찾았음
i += 1
return None # 전체를 순회했지만 찾고자 하는 키를 찾지 못함- 위의 예시에서 해시 테이블의 크기가 10이고 나머지 연산 결과가 모두 1인 항목들을 삽입시켜 계속 충돌을 발생시켰을 때, 이차 조사법 적용 전과 후를 비교해 군집화 현상이 완화되는지 확인해 보자.
# 이차 조사법 적용 전
ht = LinearProbingHashTable(10)
for i in [11, 21, 31, 41, 51, 61, 71]:
ht.insert(i)
ht.display()
```#결과#```
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: EMPTY
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: 61
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: 61
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: 61
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: 61
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: 61
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: 61
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: 31
Bucket 4: 41
Bucket 5: 51
Bucket 6: 61
Bucket 7: 71
Bucket 8: EMPTY
Bucket 9: EMPTY
``````````
# 이차 조사법 적용 후
ht_2 = QuadraticProbingHashTable(10)
for i in [11, 21, 31, 41, 51, 61, 71]:
ht_2.insert(i)
ht_2.display()
```#결과#```
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: EMPTY
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: EMPTY
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: EMPTY
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: EMPTY
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: EMPTY
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
------------------------------
Bucket 0: 41
Bucket 1: 11
Bucket 2: 21
Bucket 3: EMPTY
Bucket 4: EMPTY
Bucket 5: 31
Bucket 6: 61
Bucket 7: 51
Bucket 8: EMPTY
Bucket 9: EMPTY
``````````- 최종 결과만 비교했을 때 이차 조사법을 적용하기 전은 [EMPTY, 11, 21, 31, 41, 51, 61, 71, EMPTY, EMPTY]로 군집화 현상이 발생한 것을 볼 수 있다.
- 반면, 적용용 후는 [41, 11, 21, EMPTY, EMPTY, 31, 61, 51, EMPTY, EMPTY]로 적용 전보다 군집화, 즉 항목의 집중화가 완화된 것을 볼 수 있다.
6.4.2 이중 해싱법 구현
■ 두 번째 해싱 함수를 self.size - (key % self.size)로 정의하여 이중 해싱법을 다음과 같이 적용하였다.
class DoubleHashingHashTable:
def __init__(self, M):
super().__init__(M)
def hash_function2(self, key):
return self.size - (key % self.size)
def insert(self, key):
index = self.hash_function(key)
second_index = self.second_hash(key)
i = 0
first_deleted = -1
while i < self.size:
new_index = (index + i * second_index) % self.size # 이중 해싱 공식 적용
if self.table[new_index] == 'EMPTY':
if first_deleted != -1:
self.table[first_deleted] = key
else:
self.table[new_index] = key
return True
elif self.table[new_index] == 'DELETED':
if first_deleted == -1:
first_deleted = new_index
elif self.table[new_index] == key:
return False # 중복 키가 존재하므로 삽입 실패
self.display()
print('---'*10)
i += 1
return False # 해시 테이블이 가득 찼음
def search(self, key):
index = self.hash_function(key)
second_index = self.second_hash(key)
i = 0
while i < self.size:
new_index = (index + i * second_index) % self.size
if self.table[new_index] == 'EMPTY':
return None # 키를 찾을 수 없음
elif self.table[new_index] == key:
return new_index # 키를 찾았음
i += 1
return None # 전체를 순회했지만 키를 찾지 못함
6.5 오버플로 처리 - 체이닝(chaining)
■ 체이닝은 각각의 버킷을 링크드 리스트로 구현해서 슬롯의 개수에 제한을 두지 않고, 하나의 버킷에 원하는 만큼 계속해서 여러 개의 레코드를 저장하는 방법이다.
■ 이 방법을 사용하면 충돌 시, 이미 저장되어 있는 레코드에 이어서 연결하면 된다.
■ 예를 들어 체이닝을 이용해 크기가 5인 해시 테이블에 1, 51, 12, 4, 34를 삽입한다면, 체이닝을 이용하지 않았을 경우 '1' 삽입 후 '51' 삽입 시 & '4' 삽입 후 '34' 삽입 시 충돌이 발생한다. 반면, 체이닝을 이용한다면 다음과 같이 이미 저장된 레코드 노드에 연결해 새로운 레코드 노드로 '51', '34'를 저장하면 된다.
■ 이렇게 체이닝 방법을 이용하면 해싱 테이블이 링크드 리스트로 구성되므로 필요한 만큼의 메모리만 사용하게 되고, 오버플로가 발생해도 오버플로가 발생한 버킷만 처리하게 되므로 공간과 시간면에서 모두 효율적이다.
6.5.1 체이닝을 이용한 해시 맵 구현
■ 체이닝은 링크드 리스트를 이용하므로 노드가 필요하다. 이느 단순연결리스트의 Node 클래스를 사용하면 된다.
■ 그리고 해싱에서는 테이블의 크기 \( M \)이 미리 결정되어 있어야 한다.
■ 엔트리의 키가 문자열이면 정수에 대응시키기 위해 문자열의 각 문자에 대한 아스키 코드 값을 더하고, 모두 더한 값을 테이블 크기로 나머지 연산하는 해시 함수를 사용한다.
class Node:
def __init__(self, data, link = None):
self.data = data # 데이터 필드
self.link = link # 링크 필드
self.next_node = link # 노드가 하나 있는 상태이므로 더 이상 다음 노드가 없어 None을 가리켜야 함
def set_next(self, node): # 다음 노드를 설정하는 연산
self.next_node = node
def get_next(self):
return self.next_node # 다음 node를 반환하는 연산
def get_data(self):
return self.dataclass HashChainingMap:
def __init__(self, M):
self.table = [None]*M
self.M = M
def HashString(self, key): # 해시 함수
if isinstance(key, str):
result = 0
for i in key:
result += ord(i)
return result % self.M
else:
return key % self.M■ 삽입 연산은 먼저 해시 주소를 계산해야 한다.
■ 그리고 전단 삽입을 이용해 기존의 노드들이 새로 삽입된 노드 뒤로 연결되게 하면 삽입 시 \( O(1) \) 시간 복잡도로 새 노드를 추가할 수 있다.
def insert(self, key, value):
i = self.HashString(key)
self.table[i] = Node(Entry(key, value), self.table[i])
- 먼저 i = self.HashString(key) 해시 함수로 주어진 키의 해시 주소, 즉 버킷의 인덱스를 계산한다.
- 그 다음, Node(Entry(key, value), self.table[i])로 새로운 노드가 이미 버킷에 저장된 헤드 노드를 가리키게 한 다음, self.table[i] = Node(Entry(key, value), self.table[i])로 새로운 노드를 업데이트 하여 새로운 노드가 새로운 헤드 노드가 되게 한다.
■ 탐색 연산은 해시 주소를 계산하고, 계산된 주소의 모든 노드에 대해 찾고자 하는 키를 가진 노드가 있는지 확인한다.
■ 따라서 탐색 연산의 시간 복잡도는 연결된 레코드 수에 비례한다. 만약, 계산된 해시 주소에 속한 레코드가 항상 \( k \) 개 이하로 유지된다면 시간 복잡도는 \( O(k) \)이다. 즉, 탐색 연산은 상수 시간 \( k \) 만큼 소요되므로, \( O(k) \)의 시간 복잡도는 \( O(1) \) 시간 복잡도를 의미한다.
def search(self, key):
i = self.HashString(key)
node = self.table[i]
while node is not None:
if node.data.key == key:
return node.data.value
node = node.next_node
return None■ 삭제 연산은 해시 주소를 계산한 다음, 계산된 주소에 삭제하고자 하는 레코드가 존재하면 삭제하면 된다.
■ 이때, 링크드 리스트를 사용하기 때문에 삭제할 노드의 선행 노드를 찾아야 한다. 삭제하려는 노드를 리스트에서 제거하려면, 그 노드를 가리키던 선행 노드의 다음 노드를 삭제하려는 노드의 다음 노드로 변경해야 하기 때문이다.
- 예를 들어 A \( \rightarrow \) B \( \rightarrow \) C 에서 노드 'B'를 삭제하려면 A의 다음 노드로 C가 되어야 A \( \rightarrow \) C가 되어 B가 제거 된다.
■ 선행 노드를 모른다면 예시와 같이 'B'를 직접적으로 삭제할 방법이 없기 때문에 선행 노드를 알아야 한다.
def delete(self, key):
i = self.HashString(key)
node = self.table[i]
prev = None
while node is not None:
if node.get_data().key == key:
if prev == None:
self.table[i] = node.get_next()
else:
prev.set_next(node.get_next())
return
prev = node
node = node.get_next()class HashChainingMap:
def __init__(self, M):
self.table = [None]*M
self.M = M
def HashString(self, key): # 해시 함수
if isinstance(key, str):
result = 0
for i in key:
result += ord(i)
return result % self.M
else:
return key % self.M
def search(self, key):
i = self.HashString(key)
node = self.table[i]
while node is not None:
if node.data.key == key:
return node.data.value
node = node.next_node
return None
def insert(self, key, value):
i = self.HashString(key)
self.table[i] = Node(Entry(key, value), self.table[i])
def delete(self, key):
i = self.HashString(key)
node = self.table[i]
prev = None
while node is not None:
if node.get_data().key == key:
if prev == None:
self.table[i] = node.get_next()
else:
prev.set_next(node.get_next())
return
prev = node
node = node.get_next()
def display_map(self):
for i in range(len(self.table)):
node = self.table[i]
if node is None:
print('None')
continue
while node:
entry = node.get_data()
print(f'({entry.key}: {entry.value})', end=' -> ')
node = node.get_next()
print("None")Map_3 = HashChainingMap(8)
Map_3.insert('apple', 1000)
Map_3.insert('orange', 1500)
Map_3.insert('apple mango', 2000)
Map_3.insert('mango', 1700)
Map_3.insert('banana', 1200)
Map_3.insert(5, 1100)
Map_3.display_map()
```#결과#```
None
(banana: 1200) -> None
(mango: 1700) -> (apple: 1000) -> None
None
(apple mango: 2000) -> (orange: 1500) -> None
(5: 1100) -> None
None
None
````````````
Map_3.delete('apple mango')
Map_3.display_map()
```#결과#```
None
(banana: 1200) -> None
(mango: 1700) -> (apple: 1000) -> None
None
(orange: 1500) -> None
(5: 1100) -> None
None
None
````````````
print(Map_3.table[2].get_data()); print(Map_3.table[2].get_next().get_data())
```#결과#```
(mango, 1700)
(apple, 1000)
````````````
print(Map_3.search('mango'));print(Map_3.search(5))
```#결과#```
1700
1100
````````````
6.6 해시 함수
■ 좋은 해시 함수의 조건은
- 충돌이 적어야 하고
- 함수 값(=해시 주소)이 해시 테이블 주소 영역에서 고르게 분포되어야 한다.
- 그리고 계산이 빠르면 좋다.
6.6.1 해시 함수 - (1) 제산 함수
■ 제산 함수는 가장 일반적인 해시 함수로 나머지 연산을 이용하는 함수이다.
■ 탐색키가 정수 \(k \), 해시 테이블의 크기가 \( M \)이면, 제산 함수의 식은 \( h(k) = k \text{ % } M \)이다.
■ 만약, 해시 테이블의 크기가 소수라면, 소수는 1과 자기 자신만을 약수로 가지기 때문에 \( k \text{ % } M \)이 0부터 \( M - 1 \)까지 골고루 사용하는 값(여기서 값은 위치)을 만들 수 있다.
6.6.2 해시 함수 - (2) 폴딩(folding) 함수
■ 폴딩 함수는 탐색키가 해시 테이블의 크기보다 더 큰 경우, 탐색키를 몇 개의 부분으로 나누고 나눈 것들끼리 연산 후, 이를 종합하여 해시 주소로 이용하는 방법이다.
■ 폴딩 함수에서 탐색키를 나누고 더하는 방법으로 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)이 있다.
- 이동 폴딩은 탐색키를 여러 부분으로 나누고, 나눈 값들을 모두 더한 값을 해시 주소로 사용하고
- 경계 폴딩은 탐색키를 여러 부분으로 나누는데, 이때 이웃한 부분을 거꾸로 만든 다음, 나눈 값들을 모두 더한 값을 해시 주소로 사용하는 방법이다.
■ 예를 들어 탐색키가 다음과 같을 때 5개로 나눈다면
이동 폴딩과 계산 폴딩은 다음과 같이 계산된다.
6.6.3 해시 함수 - (3) 중간 제곱 함수
■ 탐색키를 제곱해서 중간의 몇 비트를 선택해 해시 주소로 생성하는 방법이다.
■ 예를 들어 탐색키가 128이면 128 × 128 = 16384에서 중간의 63, 38, 638 등을 선택해서 해시 주소로 생성할 수 있다.
■ 또한, 두 킷값에서 몇 개의 자리가 같아도 서로 다른 해싱 주소를 가질 수 있다.
■ 예를 들어 \( key_1 = 1234 \), \( key_2 = 1244 \)라면, \( key_1 \)의 제곱 1522756, \( key_2 \)의 제곱 1547536이다. 중간 3자리를 사용하면 \( key_1 \)의 해시 주소는 227, \( key_2 \)의 해시 주소는 475가 된다.
■ 이렇게 key 값을 제곱하면 크기가 작은 key는 작은 제곱 값, 큰 key는 큰 제곱 값을 가지므로 key의 크기에 따라 다양한 자리의 숫자가 생성된다. 따라서 제곱 결과의 중간 비트는 다양한 해시 주소가 생성되므로 해시 테이블에 데이터들이 고르게 분산될 수 있다.
6.6.4 해시 함수 - (4) 비트 추출 함수
■ 해시 테이블 크기가 \( M = 2^k \)일 때, 탐색키를 이진수로 간주하여 임의의 위치에 \( k \)개의 비트를 해시 주소로 사용하는 방법이다.
■ 이진수, 즉 해시 주소가 0과 1로 구성되기 때문에 동일한 해시 주소가 많이 생성되어 군집화 현상이 발생할 가능성이 높다.
cf) 탐색키가 문자열인 경우
■ 탐색키가 문자열인 경우, 각 문자의 아스키 코드나 유니코드 값을 이용해 문자를 정수로 대응시켜 정수로 변환하면 된다.
■ 예를 들어 문자열 탐색키를 받아 아스키 코드를 이용해 각 문자를 정수로 대응시켜, 모든 정수를 더하고 모두 더한 값을 제산 함수처럼 해시 테이블의 크기 \( M \)으로 나머지 연산을 적용해서 해시 주소를 계산하는 해시 함수를 만들 수 있다.
def HashString(key, M):
result = 0
for i in key:
result += ord(i)
return result % Mkey1, key2 = 'string','String'
print(HashString(key1, 11));print(HashString(key2, 11))
```#결과#```
3
4
````````````
7. 해싱의 적재 밀도(적재 비율)
■ 해싱의 시간 복잡도는 이상적인 경우 모든 연산이 \( O(1) \)로 수행된다. 단, 충돌이 발생하면 할수록 연산이 \( O(1) \)보다 더 느려질 수 있다.
■ 해싱의 성능을 분석하기 위해 해싱의 적재 밀도(loading density) 또는 적재 비율(loading factor)을 계산하며, 이는 저장되는 항목의 개수 \( n \)과 해시 테이블의 크기 \( M \)의 비율이다. \[
\alpha \text{(적재 밀도, 적재 비율)} = \dfrac{\text{저장된 항목의 개수}}{\text{해시 테이블의 크기 = 해시 테이블의 버킷 개수}} = \dfrac{n}{M}
\]
■ \( \alpha = 0 \)이면 '저장된 항목의 개수 = 0'이므로 해시 테이블에는 아무것도 없는 상태이다.
■ \( \alpha \) 값은 충돌 해결 방법에 따라 달라진다. 선형 조사법은 해시 테이블이 모두 차면 모든 버킷에 하나의 항목이 저장된 것이므로 \( n = M \)이다. 따라서 \( \alpha = 1 \)이 된다.
■ 반면, 체이닝은 저장할 항목의 수가 제한을 받지 않아 \( n \)이 \( M \)보다 더 커질 수 있어 \( \alpha \)는 최댓값을 가지지 않는다.
8. 탐색 방법별 성능 비교
| 탐색 방법 | 탐색 연산 | 삽입 연산 | 삭제 연산 |
| 순차 탐색 | \( O(n) \) | \( O(1) \) | \( O(n) \) |
| 이진탐색, 보간 탐색 | \( O(\log_2 n) \) | \( O(n) \) | \( O(n) \) |
| 이진 탐색 트리 - 균형 트리(최선의 경우) | \( O(\log_2 n) \) | \( O(\log_2 n) \) | \( O(\log_2 n) \) |
| 이진 탐색 트리 - 경사 트리(최악의 경우) | \( O(n) \) | \( O(n) \) | \( O(n) \) |
| 해싱 - 최선의 경우 | \( O(1) \) | \( O(1) \) | \( O(1) \) |
| 해싱 - 최악의 경우 | \( O(n) \) | \( O(n) \) | \( O(n) \) |
■ 최선의 경우의 해싱은 탐색, 삽입, 삭제 연산이 모두 \( O(1) \)로 가장 효율적이지만, 해싱은 순서가 없기 때문에 다른 방법들처럼 어떤 항목의 이전 항목, 다음 항목을 쉽게 찾을 수 없다.
■ 또한, 최악의 경우의 해싱은 모든 키가 하나의 버킷에 집중되어 항목이 \( n \)개이면 그만큼의 충돌이 발생하여 시간 복잡도가 \( O(n) \)이 된다는 단점이 있다.
