들어가며
해시법에 대해 다루기 전에 한 가지 경우를 살펴보도록 하자. 만약, 아래와 같은 배열에서 a[2]에 새로운 원소 6를 추가하는 경우, 일반적인 배열에서의 처리 과정은 다음과 같을 것이다.
a = [1, 7, 10, 13, 16, 22]a[0](=1)와a[1](=7)사이에 새로운 값이 추가될 수 있도록 이진 검색으로 검색a[0](=1) 이후의 모든 원소를 한 칸씩 뒤로 이동a[1](=None)에 새로운 원소 6을 대입
이와 같이 데이터 추가 또는 삭제 시 배열의 원소가 이동하는데 필요한 복잡도는 O(n)이고, 이는 배열의 크기가 커짐에 따라 그 비용 또한 커질 수 밖에 없다는 것을 의미한다.
해시법
해시법은 간단한 연산을 통해 데이터 저장 위치 = 인덱스를 구하는 방법으로, 데이터 검색 뿐만 아니라 데이터 추가 또는 삭제가 빈번하게 발생하는 경우 이를 효율적으로 수행할 수 있는 방법이다. 여기서 해시(hash)란 특정 연산의 결과 값이라고 표현할 수 있으며, 이는 데이터에 접근할 때 기준이 되는 값이다. 이해를 돕기위해 위의 경우를 해시법으로 해결해보자. 먼저, 위의 배열에서 데이터 추가 전의 배열을 해시법으로 나타내었을때 해시 테이블은 다음과 같다. 이때, 원소값을 8로 나눈 나머지를 해시값으로 하였다.
| 해시값(원소값 % 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 원소값 | 16 | 1 | 10 | None | 22 | 13 | None | 7 |
새로운 원소 6을 8로 나눈 나머지는 6이므로, 그 결과 다음과 같이 새로운 원소 6 이후의 원소들을 뒤로 한 칸씩 이동할 필요가 없는 것을 확인할 수 있다.
| 해시값(원소값 % 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 원소값 | 16 | 1 | 10 | None | 22 | 13 | 6 | 7 |
이를 배열로 나타내면 다음과 같다.
x = [16, 1, 10, None, 22, 13, 6, 7]이와 같이 특정 원소 값을 해시값으로 변환하는 과정을 해시 함수라고 하고, 이는 일반적으로 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다. 또한, 해시 함수에서 사용된 원소값을 키(key)라고 하고, 해시 테이블의 x[0] ~ x[7]과 같은 원소를 버킷(bucket)이라고 한다.
다만, 해시법에도 한 가지 문제가 있는데, 이를 확인하기 위해 새로운 원소 8을 추가해보도록 하자. 새로운 원소 8을 8로 나눈 나머지는 0이므로, 버킷 x[0]에 저장되어야 하나, 버킷 x[0]에는 이미 16이라는 값이 존재하는 것을 확인할 수 있다. 일반적으로 키와 해시값의 대응 관계는 n:1이므로 저장할 버킷이 중복될 수 있는데, 이를 해시 충돌(hash collision)이라고 한다. 이처럼 해시 충돌이 발생하는 경우 체인법 또는 오픈 주소법으로 대처할 수 있다.
체인법
체인법은 해시값이 같은 데이터를 연결 리스트에 의해 체인 모양으로 연결하는 방법이며, 오픈 해시법(open hashing)이라고도 한다. 단, 여기서 등장한 연결 리스트는 파이썬에서 제공하는 리스트와는 다른 개념이며, 이는 다른 포스팅에서 따로 정리하도록 하겠다. 또한, 체인법(=오픈 해시법)과 뒷 부분에 정리할 오픈 주소법은 용어가 비슷하므로 헷갈리지 않도록 주의하여야 한다. 이해를 돕기 위해 위에서 발생한 해시 충돌을 체인법으로 해결한 결과를 먼저 보면 다음과 같다.
| 해시값(원소값 % 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 노드 | 16 | 1 | 10 | None | 22 | 13 | 6 | 7 |
| 노드 | 8 | None | None | None | None | None | None | None |
이처럼 체인법은 배열의 각 버킷에 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드를 참조하는 방식으로 값을 저장한다. 즉, 16과 8의 해시값은 모두 0이며, 이들을 연결하는 연결 리스트의 앞쪽 노드를 참조하여 x[0]에 저장한다. 이때, 해시값 3과 같이 데이터가 존재하지 않는 버킷의 값을 None이라고 한다. 각각의 노드에는 키, 값, 참조 노드 필드가 있으며, 이를 나타낸 코드는 다음과 같다.
class Node:
def __init__(self, key: any, value: any, next) -> None:
self.key = key # 키 초기화
self.value = value # 값 초기화
self.next = node # 참조 노드 초기화이때, key는 해시 함수를 통해 해시값을 구할 때 사용되며, value는 값이 된다. 또한, 참조 노드의 경우 자기 참조형 클래스인 Node를 입력받아 해당 노드에서 검색이 실패하는 경우 참조 노드를 넘겨줄 때 사용된다. 이번에는 해시 클래스를 구현해보도록 하자. 해시 클래스는 해시 테이블의 크기, 해시 테이블을 저장하는 배열 필드가 있으며, 이를 나타낸 코드는 다음과 같다.
class ChainedHash:
def __init__(self, capacity: int) -> None:
self.capacity = capacity # 해시 테이블의 크기 초기화
self.table = [None] * capacity # 해시 테이블 초기화해시 테이블의 크기가 충분히 큰 경우 해시 충돌 발생을 방지할 수 있지만, 해시 테이블의 정보를 저장하기 위해 메모리가 낭비된다는 단점이 있다. 반면, 해시 테이블의 크기가 작은 경우 해시 충돌이 발생할 가능성이 매우 커짐에 따라 각각의 참조 노드를 확인하는 과정에서 복잡도가 증가할 수 있다. 즉, 시간과 공간의 상충 관계(trade-off) 문제가 발생하게 된다. 해시 충돌을 피하기 위해 해시 함수가 해시 테이블의 크기와 같거나 작은 정수를 반환하도록 하는 방법이 있으므로 해시 테이블의 크기는 소수를 선호하며, 해시 함수는 다음과 같은 코드로 나타낼 수 있다.
import hashlib
class ChainedHash:
def __init__(self, capacity: int) -> None:
self.capacity = capacity # 해시 테이블의 크기 초기화
self.table = [None] * capacity # 해시 테이블 초기화
# 해시 함수
def hash(key: any) -> int:
if isinstance(key, int):
return key % self.capacity # key가 정수인 경우
byte_str = str(key).encode() # key → str 변환 후 바이트 문자열 생성
byte_hash = hashlib.sha256(byte_str) # 주어진 바이트 문자열의 해시값
key = byte_hash.hexdigest() # 해시값을 16진수 문자열로 변환
return int(key, 16) % self.capacity # key가 정수가 아닌 경우코드를 보면 알 수 있듯이 해시 함수의 인수 key는 모든 데이터 타입으로 입력되므로, 정수인 경우와 정수가 아닌 경우로 구분할 수 있다.
- key가 정수인 경우 : key를 capacity로 나눈 나머지를 해시값으로 반환
- key가 정수가 아닌 경우 : 나머지를 구하는 연산이 불가능하므로 표준 라이브러리 hashlib를 사용하여 key의 자료형을 변환한 이후에 capacity로 나눈 나머지를 해시값으로 반환
원하는 key로 원소를 검색하기 위한 메소드를 나타낸 코드는 다음과 같다.
class ChainHash:
# ...(중략)...
def search(self, key: any) -> any:
hash_value = self.hash(key) # 해시값
ref = self.table[hash_value] # 참조 노드
while ref is not None:
if ref.key == key: # 연결 리스트 노드에서 key를 찾은 경우
return ref.value
ref = ref.next
return None # 연결 리스트 노드에서 key를 찾지 못한 경우체인법을 해시 클래스로 구현한 것이기 때문에 검색 알고리즘을 구현하기 위해서는 먼저 클래스에 값을 입력해주어야 한다. 이때, 새로운 참조 노드를 등록하기 전에 앞서 작성한 search() 메소드를 통해 해당 키값이 이미 존재하는지에 대한 유효성 검사를 먼저 수행하여야 하는데, 이를 나타낸 코드는 다음과 같다.
class ChainHash:
# ...(중략)...
def add(self, key: any, value: any) -> bool:
if self.search(key) is not None:
return False # 이미 등록된 key
hash_value = self.hash(key) # 해시값
ref = Node(key, value, self.table[hash_value])
self.table[hash_value] = ref
return True # 등록 완료원소를 삭제할 때에는 해시 테이블의 버킷이 참조하는 연결리스트를 맨 앞에서부터 차례대로 선형 검색을 수행하여 key와 같은 값을 찾은 경우 해당 노드를 연결 리스트에서 삭제하고, 선형 검색이 완료될 때까지 해당 key와 같은 값을 찾지 못한다면 삭제에 실패한다. 이를 나타낸 코드는 다음과 같다.
class ChainHash:
# ...(중략)...
def remove(self, key: any) -> bool:
hash_value = self.hash(key) # 해시값
ref = self.table[hash_value] # 참조 노드
pref = None # 참조 노드 앞의 노드
while ref is not None:
if ref.key == key:
if pref is None: # 앞의 노드가 없는 경우
self.table[hash_value] = ref.next
else: # 앞의 노드가 있는 경우
pref.next = ref.next
return True
pref = ref
ref = ref.next
return False즉, key 값에 해당하는 노드가 맨 앞의 노드인 경우 해당 노드를 삭제하면 뒤에 참조노드 또한 모두 삭제될 수 있다. 이를 방지하기 위해서 참조노드 앞의 노드의 유무에 따라 앞의 노드가 없는 경우(맨 앞의 노드) 현재 버킷을 다음 노드로 채워주고, 그 외의 경우에는 이전 노드의 다음 노드가 현재 노드의 다음 노드가 되도록 앞으로 한 칸씩 당겨주어야 한다.
오픈 주소법
오픈 주소법은 체인법과 마찬가지로 해시 충돌 발생 시 이를 해결할 수 있는 방법 중 하나이다. 오픈 주소법은 해시 충돌이 발생하였을 때 재해시(rehasing)를 통해 빈 버킷을 찾는 방법이며, 닫힌 해시법(closed hashing)이라고도 한다. 이해를 돕기 위해 다시 위에서 언급한 예시의 해시표를 나타내면 다음과 같다.
| 해시값(원소값 % 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 원소값 | 16 | 1 | 10 | None | 22 | 13 | 6 | 7 |
마찬가지로 새로운 원소 8을 추가하면, 해시값 0의 x[0] 버킷에 이미 원소가 존재하므로 해시 충돌이 발생하는데, 이때 재해시를 수행할 수 있다. 재해시 규칙은 자유롭게 정할 수 있으나, 본 글에서는 key에 1을 더한 값에 8로 나눈 나머지를 사용하였다. 오픈 주소법으로 새로운 원소 8을 추가하는 과정을 정리하면 다음과 같다.
1. 원소값(8) % 8 = 0 : x[0]에 원소 16이 존재하므로 재해시
2. (원소값(8) + 1) % 8 = 1 : x[0]에 원소 1이 존재하므로 재해시
3. (원소값(9) + 1) % 8 = 2 : x[2]에 원소 10이 존재하므로 재해시
4. (원소값(10) + 1) % 8 = 3 : x[3]에 새로운 원소 8추가이와 같이 빈 버킷을 찾을 때까지 재해시를 수행하여 새로운 원소를 추가할 수 있다. 이와 같은 이유로 오픈 주소법을 선형 탐사법(linear probing)이라고도 한다. 오픈 주소법을 코드로 구현하기 위해서는 Node 클래스 대신에 Bucket, Attribute 클래스를 작성하여야 한다. 따라서, 오픈 주소법의 기능별로 코드를 작성하기 전에 Bucket, Attribute 클래스의 필요성을 먼저 파악해야 하므로, 원소를 삭제하는 경우에 대해서 먼저 알아보자.
위의 예시에서 새로운 원소 8을 추가한 이후 해시 테이블을 다음과 같을 것이다. 그렇다면 아래 해시 테이블에서 원소 16과 8을 순차적으로 삭제해보도록 하자.
| 해시값(원소값 % 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 원소값 | 16 | 1 | 10 | 8 | 22 | 13 | 6 | 7 |
원소 16을 삭제할 때에는 큰 문제 없이 x[0] 버킷의 원소를 삭제하면 되므로, 그 결과는 다음과 같다.
| 해시값(원소값 % 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 원소값 | None | 1 | 10 | 8 | 22 | 13 | 6 | 7 |
그런데, 원소 8을 삭제할 때에는 문제가 발생한다. 원소 8을 재해시 과정 없이 새롭게 추가한다고 가정하면, 원소 8의 해시값은 0(=8 % 8)이다. 그렇다면 해시 테이블에서 원소 8을 삭제할 때 x[0]의 버킷의 원소를 삭제하면 되는 것인데, 문제는 해당 버킷이 비어있다는 사실이다. 즉, 해시값이 0인 데이터를 삭제해야 하는데, 해당 해시값이 0인 데이터는 존재하지 않는다고 착각하여 검색에 실패하게 된다. 이와 같은 오류를 방지하기 위하여 버킷에 아래 코드와 같은 속성을 부여해준다.
from enum import Enum
class Attribute(Enum):
SAVED = 0 # 데이터 저장 상태
NULL = 1 # 비어있는 상태
DELETED = 2 # 삭제된 상태즉, 위의 예시에서 원소 16을 삭제하게 되면 해시 테이블은 다음과 같이 수정될 것이다. 이어서 원소 8을 삭제할 때에는 원소 8의 해시값 0에 해당하는 x[0] 버킷을 검색하는데, x[0] 버킷의 속성이 DELETED이므로 원소 8이 존재하는 버킷을 찾을 때까지 재해시를 수행한 후에 해당 버킷의 원소를 삭제하고, 속성을 DELETED로 변경한다.
| 해시값(원소값 % 8) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 원소값 | DELETED | 1 | 10 | 8 | 22 | 13 | 6 | 7 |
각각의 버킷에 속성을 부여하기 위해서는 해시 테이블의 모든 원소가 key, 값 뿐만 아니라 속성 필드로 구성되어야 한다. 이를 클래스로 나타낸 코드는 다음과 같다. Bucket 클래스는 버킷의 상태에 따라 key, 값, 속성을 변경하는 메소드와 속성만 변경하는 메소드를 추가하였다.
class Bucket:
def __init__(self, key: any = None, value: any = None,
attribute: Attribute = Attribute.NULL) -> None:
self.key = key # 키 초기화
self.value = value # 값 초기화
self.attribute = attribute # 속성 초기화
def set(self, key: any, value: any, attribute: Attribute) -> None:
self.key = key # 키 변경
self.value = value # 값 변경
self.attribute = attribute # 속성 변경
def set(self, attribute: Attribute) -> None:
self.attribute = attribute # 속성 변경이를 토대로 오픈 주소법으로 구현한 해시 클래스의 코드는 다음과 같다. 해시값을 구하는 메소드는 체인법과 동일하며, 재해시 메소드는 해시값에 + 1을 더한 값에 테이블의 크기를 나눈 나머지를 반환하도록 하였다.
import hashlib
class OpenHash:
def __init__(self, capacity: int) -> None:
self.capacity = capacity # 해시 테이블의 크기 초기화
self.table = [Bucket()] * capacity # 해시 테이블 초기화
def hash(self, key: any) -> int:
if isinstance(key, int):
return key % self.capacity # key type == int
byte_str = str(key).encode() # key → str 변환 후 바이트 문자열 생성
byte_hash = hashlib.sha256(byte_str) # 주어진 바이트 문자열의 해시값
key = byte_hash.hexdigest() # 해시값을 16진수 문자열로 변환
return int(key, 16) % self.capacity # key type == int
def rehash(self, key: any) -> int:
hash_value = self.hash(key) + 1
return hash_value % self.capacity앞서 언급하였듯이 해시 테이블의 모든 원소는 버킷으로 구성되어 있기 때문에 원소 추가, 삭제, 검색 시 해시값에 해당하는 버킷을 먼저 찾아야 한다. 이를 위한 코드는 다음과 같으며, key에 해당하는 버킷을 찾을 때까지 재해시하여 버킷을 반환하도록 하였고, 버킷이 현재 빈 상태인 경우에는 굳이 버킷을 반환할 이유가 없으므로 None을 반환하도록 하였다.
class OpenHash:
# ...(중략)...
def bucket(self, key: any) -> any:
hash_value = self.hash(key)
bucket = self.table[hash_value]
for i in range(self.capacity):
if bucket.attribute == Attribute.NULL:
break
elif bucket.attribute == Attribute.SAVED and bucket.key == key:
return bucket
hash_value = self.rehash(hash_value) # 재해시 수행
bucket = self.table[hash_value]
return None원하는 key로 원소를 검색하는 코드는 다음과 같다.
class OpenHash:
# ...(중략)...
def search(self, key: any) -> any:
bucket = self.bucket(key)
if bucket is not None:
return bucket.value
else:
return None원소를 추가하는 코드를 살펴보도록 하자. 체인법과 마찬가지로 search 메소드를 실행하여 버킷의 유효성 검사를 수행하여 이미 버킷이 존재하는 경우 즉, 버킷의 값이 저장되어 있는 경우에는 원소를 추가하는데 실패한다. 체인법과 비교해보았을 때 한 가지 다른 점을 코드에서 확인할 수 있는데, 체인법의 경우 해시값이 중복되어도 연결 리스트를 통해 원소를 저장하는 반면, 오픈 주소법의 경우는 저장할 수 있는 원소의 개수가 해시 테이블의 크기로 한정되어 있다는 점이다. 즉, 오픈 주소법은 해시 테이블의 모든 버킷에 원소가 저장되면 더 이상 추가로 원소를 저장할 수 없다.
class OpenHash:
# ...(중략)...
def add(self, key: any, value: any) -> bool:
if self.search(key) is not None: # 이미 등록된 키
return False
hash_value = self.hash(key)
bucket = self.table[hash_value]
for i in range(self.capacity):
if bucket.attribute == Attribute.NULL or bucket.attribute == Attribute.DELETED:
self.table[hash_value] = Bucket(key, value, Attribute.SAVED)
return True
hash_value = self.rehash(hash_value) # 재해시 수행
bucket = self.table[hash_value]
return False원소를 삭제하는 코드는 다음과 같으며, 체인법과는 다르게 굉장히 단순한 로직으로 구현되어 있다는 것을 알 수 있다.
class OpenHash:
# ...(중략)...
def remove(self, key: any) -> int:
bucket = self.bucket(key)
if bucket is None:
return False
bucket.set_attribute(Attribute.DELETED)
return True마치며
당장 써먹을 곳은 없지만 단순한 호기심에 이끌려 검색 알고리즘에 대해서 혼자 공부한 내용을 정리해보았다. 매번 느끼는 점이지만, 학교 수업(직장생활 하느라 잘 듣지도 못했던)과는 다르게 혼자서 공부하면 비록 속도는 느려도, 확실히 개념을 잡고 가는 것 같다. 더군다나 공부한 내용을 나름 정리해서 포스팅하는 과정에서 내가 작성했던 코드, 그리고 개념들을 한 번 더 정리하게 되니 더욱 확실하게 이해되는 것 같다.
'Algorithm > 개념정리' 카테고리의 다른 글
| 정렬 알고리즘(Sort Algorithm)의 퀵 정렬(Quick Sort) 개념 정리 (0) | 2022.03.28 |
|---|---|
| 자료 구조(Data Structure)의 큐(Queue) 개념 정리 (0) | 2022.01.15 |
| 자료 구조(Data Structure)의 스택(Stack) 개념 정리 (0) | 2022.01.14 |
| 검색 알고리즘(Search Algorithm)의 선형 검색과 이진 검색 개념 정리 (0) | 2022.01.12 |
| [자료구조] 이진트리(Binary Tree) 생성 개념 정리 (0) | 2021.10.25 |