자료 구조 마지막 포스팅이 언제였더라...(뒤적뒤적)
세상에... 3년 전이 마지막 자료구조 포스팅이었다. 필자가 최근 밀린 포스팅들을 몰아서 작성하다보니, 놓치고 있던 카테고리들이 상당히 많은데, 최근에 자료 구조 서적을 다시 뒤적거릴 일이 생긴 참에 이 카테고리를 방문(?)하게 되었다.
하여간, 마지막 자료구조 포스팅의 내용은 Hash 충돌을 해결하는 방법 중 하나인 Chaining이었는데, 이번 포스팅에서는 Hash 충돌을 피하는 또 다른 방법인 개방 주소법(Open Address)에 대해 알아보려한다.
1. Open Address 개요
Hash값의 충돌로 Hash List의 동일 Bucket(index라고 생각하자)에 둘 이상의 자료가 저장되는 경우, Hash 충돌이 일어났다고 말한다. 아무래도 방대한 데이터를 한정된 카테고리로 나누어 넣어야하다 보니, 충돌이 일어나지 않기가 어려운 구조다. 따라서 이전 포스팅에서 설명한 Chaining 방법은 동일 Bucket에 들어가는 데이터가 둘 이상 존재하는 경우, 이들을 Linked List(연결 리스트 - 이거 진짜 추후에 포스팅 할 거다... 지난 포스팅에서도 이래놓고 3년 동안 안했지...)로 연결하여 Bucket에 저장한다.
이렇게 되면 Hash 값이 중복되는 데이터도 균일하게 Hash List에 저장할 수 있다는 장점이 있으나, 정말 재수없게도 저장해야 하는 값들의 Hash가 전부 동일하다던가, Hash List의 크기가 너무 작은 경우, 하나의 Bucket에 다량의 데이터가 Linked List로 저장된다는 단점이 생긴다. 검색을 빨리 하려고 Hash를 썼는데, Bucket 내에서는 다량의 데이터를 선형 구조로 검색을 해야하니 선형구조로 데이터를 저장하는 것과 별 반 차이가 없게 되는 것이다.
그럼, Hash 중복값이 일어나는 데이터를 Hash List 내의 빈 Bucket에 보관할 수는 없을까? 이 물음에서 출발한 것이 개방 주소법(Open Address)이다.
개방 주소법은 개념이 간단하다. Hash값에 맞는 Hash List의 Bucket이 비어있으면 값을 저장하고, 그렇지 않다면 바로 옆의 Bucket에 값을 저장한다는 개념이다. 만약 바로 옆의 Bucket도 값이 저장되어 있다면? 그 옆의 Bucket이 비어있는지 확인하고 값을 저장한다.
Chaining의 경우에는 연결 리스트의 Node에 데이터 값을 저장시킴과 동시에, 연결 리스트의 다음 Node 주소 정보까지도 저장하고 있어야하지만, 개방 주소법의 경우 연결되는 데이터가 없기 때문에 Node를 생성할 필요가 없다. 찾고자 하는 데이터가 Hash 값과 동일한 Bucket에 위치하지 않더라도 Bucket의 위치를 하나씩 옮겨가며(선형 검색으로) 검색하면 되기 때문이다.
2. 개방 주소법 구현 코드 - Python
Hash 충돌을 해결할 수 있는 개방 주소법을 한 번 구현해 보려한다.
(1) 클래스 뼈대 만들기
먼저 필요한 것을 정리해보자. 우선 데이터를 저장할 Hash List를 생성하고, 이를 다룰 수 있는 클래스가 하나 필요하다. 이 클래스에서는 저장할 데이터에 대한 Hash 값을 돌려주는 메서드, 데이터의 Bucket 저장, 조회, 삭제 기능을 추가하려한다.
기능을 감안해서 클래스를 작성했을 떄, 대략 아래와 같은 뼈대가 나타난다.
|
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
|
from hashlib import sha256
class HashList():
# 인스턴스 생성 시, capacity 크기의 List를 생성. List는 기본값으로 None이 입력
def __init__(self, capacity: int):
self.capacity: int = capacity
# List에 저장된 None 값은 추후 다른 클래스로 변경할 예정이다. 포스팅 참고
self.hash_list: list = [None] * self.capacity
def __hash_function(self, value: str):
pass
def store_data(self, data: str):
pass
def search_data(self):
pass
def remove_data(self):
pass
|
cs |
(2) Hash 반환 매서드 및 데이터 추가 매서드
이제 각 기능에 대해 구현을 진행해보자. 먼저 hash 값을 돌려주는 __hash_function과 데이터 추가를 담당하는 store_date() 매서드를 아래와 같이 작성한다.
|
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
|
from hashlib import sha256
class HashList():
# 인스턴스 생성 시, capacity 크기의 List를 생성. List는 기본값으로 None이 입력
def __init__(self, capacity: int):
self.capacity: int = capacity
# List에 저장된 None 값은 추후 다른 클래스로 변경할 예정이다. 포스팅 참고
self.hash_list: list = [None] * self.capacity
def __hash_function(self, value: str):
return int(sha256(value.encode()).hexdigest(), 16) % self.capacity
def store_data(self, data):
hash_value: int = self.__hash_function(value=data)
hash_move_count = 0
while hash_move_count < self.capacity:
if self.hash_list[hash_value] is None:
self.hash_list[hash_value] = data
print(f"[INFO] 데이터 '{data}(Hash - {self.__hash_function(value=data)})가 '{hash_value}'번 Bucket에 추가되었습니다.")
return
elif self.hash_list[hash_value] == data:
print(f"[WARNING] 데이터 '{data}'는 이미 저장된 값입니다.")
return
hash_value = (hash_value + 1) % self.capacity
hash_move_count += 1
print("[WARNING] Hash List 내 저장 공간이 없습니다.")
def search_data(self):
pass
def remove_data(self, data):
pass
|
cs |
데이터의 추가는 간단하다. Hash 추출값으로 반환받은 Bucket Index가 비어 있다면 값을 저장하고, 아니라면 다음 Bucket index에 값을 저장한다. 만약 다음 Index의 Bucket도 값이 저장되어 있다면 동일한 절차를 다음 Bucket에서 진행한다. 만약 모든 Bucket이 데이터로 저장되어 있다면 "저장 공간이 없다"는 문구를 화면에 출력한다. 만약 동일한 값이 입력된다면 "이미 저장된 데이터"라는 문구를 출력한다.
먼저 데이터 하나만 넣어보자. 필자는 "hello world!!!!"를 넣어보았다.
데이터가 잘 저장된 것이 확인된다. 이번에는 중복되는 값 및 Hash 값이 다른 데이터를 추가해보았다.
현재까지는 Hash 값과 동일한 Bucket Index에 값이 추가되는 것을 확인할 수 있다. 이번에는 "hello world!!!!"와 동일한 Hash 값을 가지는 데이터를 추가해보려한다.
필자가 방금 추가한 "Hashlist"는 이미 추가된 "hello world!!!!"와 동일한 Hash 값을 가진다. 따라서 이미 선점된 7번 Bucket에 데이터 저장이 어렵기 때문에 개방 주소법 코드에 따라 다음 Bucket인 8번에 데이터가 저장되었다.
마찬가지로 Hash 값 8을 가지는 "Guten Tag" 데이터를 추가하면 이 데이터는 이미 선점된 8번 Bucket이 아닌 9번 Bucket에 저장된다.
물론, Hash 값이 비어있는 Bucket의 Index와 동일하다면 Bucket 이동 없이 바로 값이 저장된다.
저장은 얼추 마무리 된 듯 하다. 이제 데이터의 삭제와 관련된 코드를 생각(작성이 아니다. 중요하니 밑줄을 그었겠지? - 이게 밑줄이냐..-)해보자.
데이터의 삭제는 삭제할 데이터의 Hash에 해당하는 Bucket Index에서, 저장된 값이 삭제할 값과 일치하는지 확인하고 삭제를 진행하면 될 것이다. 만약 저장된 값과 다르다면, 다음 Bucket에 저장된 값을 확인하고 삭제를 진행할지 말지 결정하면 되고, None 값이 저장되어 있다면 삭제할 데이터가 없음으로 중단하면 된다(응?)
맞다. 뭔가 이상하다. 아래의 예시를 보자.
동일한 Hash 값을 가지는 데이터가 연속된 Bucket에 저장되어 있다. 이 중 하늘색 h1 데이터를 검색한다고하면, 하늘색 h1의 해시값과 매칭되는 Bucket인 첫 번 째 버킷부터 순차적으로 데이터 일치 여부를 검색할 것이다. 그러다 4번째 버킷에서 하늘색 h1을 만나면 삭제를 진행할 것이고 말이다. 만약 보라색 h1을 삭제한다고 하면, 하늘색 h1 다음 Bucket까지 선형 검색을 진행할 것이나, 데이터가 None 값이 저장되어, "삭제할 값 없음"이라고 판단할 것이다.
이제 주황색 h1 데이터를 삭제해보자.
이 상태에서 하늘색 h1을 삭제하기 위해 Bucket을 스캔한다고 해보자. h1 해시값이 첫 번째 Bucket과 매칭되나, 첫 번째 Bucket은 이미 데이터가 사라져 None 값을 가지기 때문에 "삭제할 값 없음"이라는 어이가 아리마셍하는 결과가 나타난다. 실제로 하늘색 h1은 Hash List에 존재하고 있음에도 말이다.
그렇기 때문에 각 Bucket은 값이 삭제될 때, 자신과 연관된 Hash를 가지는 데이터가 삭제되어 빈 것인지, 아니면 기존에 비어있던 Bucket인지 기록해야 할 필요가 있다. 만약 주황색 h1이 삭제될 때, "나는 원래 데이터가 있던 Bucket인데 삭제되었어요"라는 자료가 남아있고, remove_data() 코드에서 이 조건을 사용할 수 있다면, Bucket이 None 값이더라도 뒤에 저장된 데이터를 확인할 수 있기 때문이다.
따라서, Hash List의 기본값은 단순한 None이 아니라 이들 정보를 포함할 수 있는 클래스로 저장해야 한다. 필자는 아래와 같이 Bucket 정보를 저장할 클래스를 생성했다.
|
1
2
3
4
5
6
7
8
9
10
|
class Bucket():
def __init__(self, value:str = None, status: int = 0):
# self.value: 데이터를 저장하는 변수
self.value = value
# Bucket의 상태 표시. 0 - Empty, 1 - Removed, 2 - Occupied
self.status = status
def __repr__(self):
return f"{self.value}({self.status})"
|
cs |
이에 맞춰 HashList의 __init__ 함수 부분의 self.hash_list의 생성부와 데이터 추가와 관련된 부분도 아래와 같이 변경을 진행했다.
|
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
|
from hashlib import sha256
class HashList():
# 인스턴스 생성 시, capacity 크기의 List를 생성. List는 기본값으로 None이 입력
def __init__(self, capacity: int):
self.capacity: int = capacity
# 변경 코드 1
self.hash_list: list = [Bucket() for _ in range(self.capacity)]
def __hash_function(self, value: str):
...
def store_data(self, data):
hash_value: int = self.__hash_function(value=data)
hash_move_count = 0
while hash_move_count < self.capacity:
# 조건문 코드(Head) 및 조건 실행문(Suite) 변경
if self.hash_list[hash_value].status < 2:
self.hash_list[hash_value].value = data
self.hash_list[hash_value].status = 2
print(f"[INFO] 데이터 '{data}(Hash - {self.__hash_function(value=data)})가 '{hash_value}'번 Bucket에 추가되었습니다.")
return
# 조건문 코드(Head) 변경
elif self.hash_list[hash_value].value == data:
print(f"[WARNING] 데이터 '{data}'는 이미 저장된 값입니다.")
return
hash_value = (hash_value + 1) % self.capacity
hash_move_count += 1
print("[WARNING] Hash List 내 저장 공간이 없습니다.")
def search_data(self):
pass
def remove_data(self, data):
pass
|
cs |
위와 같이 변경된 코드에서도 데이터 저장은 정상적으로 이루어지는 것이 확인된다.
이제 변경된 코드를 토대로 데이터 삭제와 관련된 매서드를 작성해보려한다.
(3) 데이터 삭제
데이터 삭제도 추가와 마찬가지로, Hash 추출 값과 동일한 Index의 Bucket부터 시작한다. 만약 해당 Bucket에 저장된 데이터가 동일하면 바로 삭제를 진행하면서 status를 1로 변경하면 되고, 저장 데이터가 일치하지 않는다면 다음 Bucket에서 동일한 작업을 진행하면 된다. Bucket에 저장된 값이 None이라면, status 값을 참조하며, status 값이 0인 경우 종료, 아닌 경우 다음 Bucket에 대해 스캔을 진행하도록 하면 된다.
코드는 아래와 같다.
|
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
|
from hashlib import sha256
class HashList():
# 인스턴스 생성 시, capacity 크기의 List를 생성. List는 기본값으로 None이 입력
def __init__(self, capacity: int):
...
def __hash_function(self, value: str):
...
def store_data(self, data):
...
def search_data(self):
pass
def remove_data(self, data):
hash_value = self.__hash_function(value=data)
hash_move_count = 0
while hash_move_count != self.capacity:
if self.hash_list[hash_value].value == data:
self.hash_list[hash_value].value = None
self.hash_list[hash_value].status = 1
print(f"[INFO] '{data}'가 삭제되었습니다.")
return
elif self.hash_list[hash_value].status == 0:
print(f"[WARNING] '{data}'는 저장되지 않은 값입니다.")
return
hash_value = (hash_value + 1) % self.capacity
hash_move_count += 1
print(f"[WARNING] '{data}'는 저장되지 않은 값입니다.")
return
|
cs |
동작을 살펴보자. 지금까지의 main 코드는 싸그리 지우고, Hash 값을 7로 반환받는 데이터 3개를 넣어보려한다.
연속된 Bucket에 동일한 Hash 값을 가진 데이터가 저장되었음을 확인했다. 이번에는 "hello world!!!!"를 삭제한 직후, 바로 "Excessive data"를 삭제해보려한다. 수정 전의 코드로는 "hello world!!!!"를 삭제하면 "Excessive data"를 인식할 수 없었던 것을 기억하자.
앞단의 Bucket에서 동일한 Hash 값을 가지는 데이터가 사라지더라도, 뒤에 있는 데이터의 검색과 삭제에 영향이 없음을 확인할 수 있었다. 두 데이터가 삭제된 상태에서 새로운 Hash 7 데이터를 추가하면 비어있는 7번 Bucket에 제대로 저장됨을 확인할 수 있다.
(4) 데이터 조회
여기까지 왔다면 데이터 조회는 크게 어렵지 않다. 별로 추가할 내용도 없으니 바로 코드를 올리자면...
|
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
|
from hashlib import sha256
class HashList():
def __init__(self, capacity: int):
...
def __hash_function(self, value: str):
...
def store_data(self, data):
...
def search_data(self):
data: str = input("\n * 검색 데이터 입력: ")
hash_value = self.__hash_function(value=data)
hash_move_count = 0
while hash_move_count != self.capacity:
if self.hash_list[hash_value].value == data:
print(f"[INFO] 데이터 '{data}'는 {hash_value}번째 Bucket에 저장되었습니다.")
return
elif self.hash_list[hash_value].status == 0:
print(f"[WARNING] '{data}'는 저장되지 않은 값입니다.")
return
hash_value = (hash_value + 1) % self.capacity
hash_move_count += 1
print(f"[WARNING] '{data}'는 저장되지 않은 값입니다.")
return
def remove_data(self, data):
...
|
cs |
검색을 진행해보자. 필자의 경우, 테스트를 위해 Hash 7 값을 가지는 4개의 데이터를 다시 활용하려한다. 우선 3개를 등록하고 가운데에 위치한 값을 삭제한 뒤, 마지막 4번째 동일 Hash 값을 Hash List에 추가할 것이다. 이 상태에서 마지막 저장 값에 대한 Bucket 위치를 확인하면 8이 출력될 것이다.
개방 주소법도 사실 문제가 없지는 않은 자료 형식인데, 우선 저장하려는 데이터보다 작은 크기의 Hash List가 존재하는 경우, 데이터를 온전히 저장할 수 없다는 문제가 있다. 따라서 데이터의 양을 고려하여 적절한 크기의 Hash List를 설계해야 한다.
또한 Hash List 전체에 데이터가 저장되었다가 삭제된 경우, status가 0인 Bucket이 존재하지 않기 때문에 결국 Hash List가 아닌 선형 검색과 동일해진다는 문제가 있다. 따라서 필자는 개방주소법은 메모리 공간이 넉넉하고 데이터가 적절한 선에서 저장될 수 있는 환경에서 효율적으로 사용할 수 있을 것이라는 생각이 든다.
다음 포스팅에서는 탐색과 관련된 다른 내용을 다루어볼까 한다
End.
'Python > Python Data Structure and Algorithm' 카테고리의 다른 글
| [자료구조 with Python] 9. 정렬 알고리즘(2) - 버블 정렬과 Shaker 정렬 (0) | 2024.03.08 |
|---|---|
| [자료구조 with Python] 8. 정렬 알고리즘(1) - 버블 정렬 개요 (0) | 2024.03.07 |
| [자료구조 with Python] 6. 선형 자료 구조 - 배열(5), Hash 충돌과 Chaining (0) | 2021.01.23 |
| [자료구조 with Python] 5. 선형 자료 구조 - 배열(4), Hash검색 (0) | 2021.01.10 |
| [자료구조 with Python] 5. 선형 자료 구조 - 배열(3), 선형/이진 검색 (0) | 2021.01.05 |
댓글