이번 글에서는 내장 해시 테이블 라이브러리를 사용하지 않고 해시셋(HashSet) 자료구조를 직접 설계하는 방법을 알아보겠습니다.
해시셋의 기본 동작
구현해야 할 핵심 함수는 다음과 같습니다.
- add(x) – 값을 x에 해시셋에 삽입합니다.
- contains(x) – 값 x가 해시셋에 존재하는지 확인합니다.
- remove(x) – 해시셋에서 x를 제거합니다. 값이 존재하지 않으면 아무 작업도 수행하지 않습니다.
동작 예시
해시셋을 초기화한 후 다음 순서로 메서드를 호출한다고 가정해 보겠습니다.
add(1), add(3), contains(1), contains(2), add(2), contains(2), remove(2), contains(2)
이때 각 contains 호출의 출력 결과는 순서대로 다음과 같습니다.
true→ 1이 존재함false→ 2가 존재하지 않음true→ 2를 추가했으므로 존재함false→ 2를 제거했으므로 존재하지 않음
문제 해결 접근 방식
1단계: Bucket(버킷) 클래스 정의
먼저 개별 버킷을 관리할 커스텀 해시셋은 다음과 같이 구성됩니다. 각 메서드는 다음 로직으로 동작합니다. 아래 코드를 통해 더 잘 이해할 수 있습니다. 이 구현의 핵심은 모듈로 연산(%)을 활용해 임의의 키를 고정된 크기의 버킷 배열에 분산시키는 것입니다. 충돌이 발생하더라도 각 버킷이 리스트 형태로 여러 값을 저장할 수 있으므로, 체이닝(chaining) 방식의 해싱과 유사하게 동작합니다. 이러한 구조 덕분에 내장 해시 라이브러리 없이도 삽입, 검색, 삭제 기능을 모두 갖춘 해시셋을 손쉽게 만들 수 있습니다.BucketTrue를, 없으면 False를 반환합니다.2단계: MyHashSet 클래스 정의
Bucket 객체 key_space개로 이루어진 리스트입니다.hash_key = key % key_space로 해시 값을 계산한 후, 해당 버킷의 update()를 호출합니다.get() 결과를 반환합니다.전체 구현 코드
예제 코드
class Bucket:
def __init__(self):
self.bucket=[]
def update(self, key):
found=False
for i,k in enumerate(self.bucket):
if key==k:
self.bucket[i]=key
found=True
break
if not found:
self.bucket.append(key)
def get(self, key):
for k in self.bucket:
if k==key:
return True
return False
def remove(self, key):
for i,k in enumerate(self.bucket):
if key==k:
del self.bucket[i]
class MyHashSet:
def __init__(self):
self.key_space = 2096
self.hash_table=[Bucket() for i in range(self.key_space)]
def add(self, key):
hash_key=key%self.key_space
self.hash_table[hash_key].update(key)
def remove(self, key):
hash_key=key%self.key_space
self.hash_table[hash_key].remove(key)
def contains(self, key):
hash_key=key%self.key_space
return self.hash_table[hash_key].get(key)
ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))입력
ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))
출력
True
False
True
False
정리