Python 알고리즘 인터뷰 - 문제 28. 해시맵 디자인

leetcode 706.Design HashMap - https://leetcode.com/problems/design-hashmap/

 

예제

다음 인터페이스를 만족하는 HashMap을 구현한다.

myHashMap = MyHashMap();
myHashMap.put(1, 1); #The map is now [[1,1]]
myHashMap.put(2, 2); #The map is now [[1,1], [2,2]]
myHashMap.get(1);    #return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    #return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); #The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    #return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); #remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    #return -1 (i.e., not found), The map is now [[1,1]]

 

풀이

python에서 dict 자료구조로 해시맵을 제공하지만 해당 자료구조는 오픈 어드레싱 방식을 사용한다. 개별 체이닝 방식을 사용하는 해시맵을 직접 구현해보도록 한다.

 

먼저 key, value를 가지고 있는 ListNode 클래스를 정의한다. key, value는 None으로 초기화한다.

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

 

이후 MyHashMap 클래스의 초기화 함수에서 ListNode 클래스 를 사용한 defaultdict를 생성하고, 버킷 사이즈를 1000으로 설정한다.

class MyHashMap:
	def __init__(self):
    	self.size = 1000
        self.tables = defaultdict(ListNode)

 

put 함수를 구현을 중 정수 key에 hash 값은 size로 모듈로 연산을 한 나머지를 저장하는 방식으로 간단히 구현한다.

def put(self, key:int, value:int) -> None:
	index = key % self.size
    ...

 

이 후 tables에 해당 index값이 있는지 확인하고 없을 경우 ListNode를 추기한다.

if tables[index].value is None:
	tables[index] = ListNode(key, value)
    return

 

여기서 table[index] 대신, tables[index].value를 참조한 이유는 defaultdict에 특성 때문이다. tables[index]를 참조하는 순간 해당 index에 해당하는 key가 없으므로, defaultdict는 {index, ListNode(key=None, value=None)}을 생성한다. 따라서 tables[index]를 비교하면 다음과 같은 문제가 발생한다.

tables[index]는 항상 None이 아니기 때문에 이에 따라 value의 None을 비교하여 해당 노드가 존재하지 않음을 체크한다.

만약 tables[index]에 노드가 존재할 경우 리스트에 key가 존재할 경우 값을 변환하고, key가 없을 경우 마지막 노드에 ListNode를 추가한다.

key가 리스트에 존재할 경우 value 변경

key가 리스트에 존재하지 않을 경우 신규 노드 추가

코드로 나타내면 다음과 같다.

p = tables[index]

while p:
	if p.key == key:
    	p.value = value
        return
    elif p.next is None:
    	break
    p = p.next
    
p.next = ListNode(key, value)

 

get 함수의 구현은 다음과 같다. 우선 put과 동일한 방법으로 index값을 구하고 tables에 index가 존재하지 않으면 -1을 반환한다. put 함수와 동일하게 defaultdict의 특성으로 기본 노드가 생기는 것을 감안하여 tables[index].value is None을 체크하도록 한다.

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

tables[index]에 리스트 중 key가 일치하는 Node의 value를 반환한다. key가 존재하지 않을 경우 -1을 반환한다.

p = tables[index]
while p:
	if p.key == key:
    	return p.value
	p = p.next
    
return -1

 

이제 삭제 함수 remove는 다음과 같이 구현을 살펴본다. get과 동일하게 index가 존재하지 않으면 pass한다.

def remove(self, key: int):
	index = key % self.size
    if tables[index].value is None:
    	return pass
    ...

remove함수에서 2가지 상황이다. 버킷에 리스트의 노드가 1개 있는 경우와 1개 이상인 경우이다. 

먼저 리스트에 Node가 1개 있는 경우는 비어 있는 리스트 노드 ListNode(None,None)으로 초기화한다. tables에서 삭제해도 되지만, 해당 index에 접근할 경우 defaultdict가 ListNode(None, None)를 생성하므로 동일한 로직이 진행된다. 따라서 ListNode(None, None)으로 초기화한다.

리스트에 노드가 하나인 경우 ListNode(None, None)으로 초기화한다.

노드가 2개 이상인 경우, 삭제할 노드를 기준으로 prev, next를 연결한다.

코드는 다음과 같다.

def remove(self, key: int):
	index = key % self.size
    if self.tables[index].value is None:
    	return
        
    p = self.tables[index]
    if p.key == key:
    	self.tables[index] = ListNode() if p.next is None else p.next
        return
    
    prev, p = p, p.next
    while p:
    	next = p.next
    	if p.key == key:
        	prev.next = next
            return
        
        prev, p = p, p.next

 

put, get, remove 함수를 구현한 전체 코드는 다음과 같다.

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


class MyHashMap(object):
    def __init__(self):
        self.size = 1000
        self.tables = defaultdict(ListNode)

    def put(self, key, value):
        index = key % self.size
        if self.tables[index].value is None:
            self.tables[index] = ListNode(key, value)
            return

        p = self.tables[index]
        while p:
            if p.key == key:
                p.value = value
                return
            elif p.next is None:
                break
            p = p.next
        p.next = ListNode(key, value)

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

        p = self.tables[index]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1

    def remove(self, key):
        index = key % self.size
        if self.tables[index].value is None:
            return

        p = self.tables[index]
        if p.key == key:
            self.tables[index] = ListNode() if p.next is None else p.next
            return

        prev, p = p, p.next
        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev, p = p, p.next