ch11-1(leetcode 706). 해시맵 디자인

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 706번 ( https://leetcode.com/problems/design-hashmap/ )

 

풀이 1. 

(leetcode에서 정답 처리되었으나 hash collision이 발생하는 경우를 처리하는 로직이 없어서 수정이 필요한 풀이입니다. 풀이 2에서 hash collision 처리 로직을 포함하였습니다.)

문제에서는 해시맵(hashmap)의 크기나, hash collision이 발생했을 때 어떤 방식으로 대처할지 등을 제시하지 않았다. 그러므로 임의로 크기를 할당하면 된다. 

 

put()으로 해시맵에 (key, value) entry를 넣으려면 해시 함수(hash function)를 만들어야 한다.

해시맵의 key, value는 모두 정수형이므로 가장 간단한 방식으로는 key값 mod hashmap size를 해시 함수로 둘 수 있다. 

def put(self, key, value):
        index = key % self.size		# hash function
        self.hashMap[index] = value

 

전체 코드는 다음과 같다. 

class MyHashMap(object):

    def __init__(self):
        self.size = 10 ** 6
        self.hashMap = [None] * self.size

    def put(self, key, value):
        index = key % self.size
        self.hashMap[index] = value
        

    def get(self, key):
        index = key % self.size
        if self.hashMap[index] is None:
            return -1
        return self.hashMap[index]
        

    def remove(self, key):
        index = key % self.size
        if self.hashMap[index] is not None:
            self.hashMap[index] = None

 

풀이 2. 

위의 풀이는 hashmap을 일반 리스트로 구현하였다. 하지만 collections 라이브러리를 사용해서 딕셔너리로 구현한다면 해시맵에 없는 키를 조회했을 때 오류가 나지 않고 자동으로 새 값을 만들  수 있다. 

self.hashMap = collections.defaultdict()

 

위의 풀이도 정답으로 처리되지만 hash collision이 일어날 경우를 처리하지 않는다. 

예를 들면 size=10인 해시맵에 (7, 20), (17, 30) 두 개의 entry를 put()으로 넣는다고 해 보자. 

 

hash collision을 처리하지 않은 위의 경우는 key=7을 get()으로 조회하였을 때 20이 아닌 30을 리턴한다. 

7 mod 10 = 7, 17 mod 10 = 7로 key 깂이 같아서 hashmap[7]의 값이 20에서 30으로 대체되었기 때문이다. 

 

만약 hash collision을 개별 체이닝(separate chaining) 방식으로 처리한다고 가정한다면 hashmap[7]을 조회하면 20, hashmap[17]을 조회하면 30이 나온다. 교재를 참고해서 수정해 보자. 

 

open addressing

교재에서도 separate chaining 방법을 사용해서 hash collision에 대처하고 있다. 개별 체이닝 방법 말고도 오픈 어드레싱(open addressing) 방법이 있다. 하지만 이 방법은 hash collision이 발생할 경우 선형 탐색(linear probing)이나 다른 해시 함수를 추가로 사용해야 하며 clustering(같은 bucket(인덱스) 값을 가진 entry들이 서로 뭉쳐서 분포하는 현상) 등의 문제가 있기 때문에 사용하지 않은 것으로 보인다. 

 

separate chaining

separate chaining은 hash collision이 발생했을 때 하나의 bucket을 연결 리스트로 연결해서 bucket 값은 같고 key 값은 다른 entry들을 계속 연결한다. 이 방법은 open addressing처럼 hash collision을 발생시킨 entry를 어느 자리에 추가로 배치할지를 고려하지 않아도 된다는 장점이 있다. 반면 해시 함수가 들어오는 entry들을 고르게 분포시키지 못할 경우 탐색 시간이 최대 O(n)만큼 걸릴 수 있다는 단점도 있다. 

 

separate chaining을 사용하려면 개별 entry가 들어올 때마다 노드를 생성해야 한다. 그래야 포인터를 통해 연결 리스트를 탐색할 수 있다. 

연결 리스트의 경우 보통은 단일 연결 리스트(singly linked list)로 구현한다. 

class ListNode(object):

	def __init__(self, key=None, value=None):
		self.key = key
		self.value = value
		self.next = None