[leetcode] 706. 해시맵 디자인 (Design HashMap)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

 

다음의 기능을 제공하는 해시맵을 디자인하라.

 

put(key, value) - 키, 값을 해시맵에 삽입. 만약 이미 존재 하는 키라면 업데이트할 것
get(key) - 키에 해당하는 값을 조회. 만약 키가 존재 하지 않는다면 -1을 리턴할 것
remove(key) - 키에 해당하는 키, 값을 해시맵에서 삭제

 

 

입출력 예시

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new 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]]

 

생각 과정

해시 테이블을 차근차근 구현해보자.

 

풀이

전체코드

class MyHashMap:
    # 초기화
    def __init__(self):
        # 기본 사이즈 설정
        self.size = 1000000
        
        # 존재하지 않는 키를 조회할 경우 자동으로 기본 딕셔너리를 생성해주는 defaultdict 사용 -> 왜?
        self.table = collections.defaultdict(ListNode)

    def put(self, key: int, value: int) -> None:
        index = key % self.size # 테이블의 인덱스, 모듈로 연산
		
        # defaultdict 생성, collections.defaultdict(ListNode)로 생성했기 때문에
        # 해당 인덱스와 매칭되는 value에 빈 ListNode가 생성됨
        if self.table[index].value is None: 
            self.table[index] = ListNode(key, value) # 비어있는 공간에 요소 추가
            return

        p = self.table[index]
        while p: # 인덱스의 첫번째 값

            # 종료 조건 1 - 테이블에 노드가 있을 때
            # 키 값이 같은 노드 찾기
            if p.key == key:
                # 키 값이 같은 노드에 값 업데이트 후 종료
                p.value = value
                return
            # 종료조건 2 - 다음 노드에 값이 없을 때
            # 이 코드가 없으면 p = p.next가 됐을 때, while문을 탈출하고, p.next에는 아무것도 없기 때문에
            # 다음 코드(p.next = ListNode(key, value))로 넘어갔을 때 에러가 난다.
            if p.next is None:
                break
            p = p.next

        p.next = ListNode(key, value)


    def get(self, key: int) -> int:
        index = key % self.size
        # 찾을 키가 없으면 -1 리턴
        if self.table[index].value is None:
            return -1

        p = self.table[index]
        while p:
            # 키 값과 매칭되는 요소 찾기
            if p.key == key:
                return p.value
            p = p.next

        # 찾아봤는데도 없다면 -1 리턴
        return -1

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

        p = self.table[index]

        # 인덱스의 첫번째 노드일 때. while로 p.next를 해주지 않았으니 첫번째 노드만 비교한다.
        if p.key == key:
            # 인덱스에 들어있는 노드가 하나뿐이면 해당 노드를 빈 노드로 바꿔준다.
            if p.next is None: # p.next가 None이라는 말이 첫번째 노드라는 말과 같다.
                # 빈 노드로 바꿔주는 이유? None으로 바꾸면 if self.table[index].value is None 코드에서 table[index] 자체가 None이기 때문에 .value를 수행할 수 없어서 에러가 남
                # 해시 테이블 객체를 생성하거나 추가하려는데 키 값이 없어서 if self.table[index].value is None 조건문을 탈 때에 self.table[index]는 자동으로 ListNode()로 생성되기 때문에
                # 이 조건문에서 현재의 노드를 처음 상태로 되돌려주는 것이다.
                self.table[index] = ListNode()
                return


        # 연결 리스트 노드 삭제
        prev = p
        while p:
            # 해당 키를 검색.
            if p.key == key:
                # 현재 노드의 다음노드와 현재 노드의 이전 노드를 연결해 줌으로써 현재노드의 연결을 끊는다. 왜 이렇게 되나요? 첫번째 노드는 이미 위에서 걸러지고,
                # 2번째부터는 값이 있다고 했을 때, prev에는 반복문 돌기 전 현재노드 즉, 다음 반복문에서는 이전노드가 담기고 p에는 다음 노드가 담기기 때문이다.
                prev.next = p.next
            prev = p
            p = p.next

# 개별 체이닝 방식을 이용하기 위해 연결 리스트 클래스 구현
class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

 

 

초기화

	# 초기화
    def __init__(self):
        # 기본 사이즈 설정
        self.size = 1000000
        
        # 존재하지 않는 키를 조회할 경우 자동으로 기본 딕셔너리를 생성해주는 defaultdict 사용
        self.table = collections.defaultdict(ListNode)

 

 

put()

def put(self, key: int, value: int) -> None:
        index = key % self.size # 테이블의 인덱스, 모듈로 연산
		
        # defaultdict 생성, collections.defaultdict(ListNode)로 생성했기 때문에 
        # 해당 인덱스와 매칭되는 value에 빈 ListNode가 생성됨
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value) # 비어있는 공간에 요소 추가
            return

        p = self.table[index]
        while p: # 인덱스의 첫번째 값

            # 종료 조건 1 - 테이블에 노드가 있을 때
            # 키 값이 같은 노드 찾기
            if p.key == key:
                # 키 값이 같은 노드에 값 업데이트 후 종료
                p.value = value
                return
            # 종료조건 2 - 다음 노드에 값이 없을 때
            # 이 코드가 없으면 p = p.next가 됐을 때, while문을 탈출하고, 
            # p.next에는 아무것도 없기 때문에 다음 코드(p.next = ListNode(key, value))로 넘어가면 에러가 난다.
            if p.next is None:
                break
            p = p.next

        p.next = ListNode(key, value)

 

여기서 key point는 이 부분이라고 생각한다.

if self.table[index].value is None:

비어있는 공간에 요소를 추가하는 부분의 조건문인데, 왜 self.table[index] is None이 아니라 self.table[index].val is None 로 비교할까?

 

바로 위에서 선언한 defaultdict(ListNode) 의 특성 때문인데, defaultdict()는 존재하지 않는 인덱스로 조회 시 바로 디폴트 딕셔너리 생성해준다고 정리한 적이 있었다. 

 

self.table[index].value 는 self.table에서 [index]를 조회해서 value를 가져오는 형태인데, 이 부분이 인덱스로 조회하는 부분이다.

이 코드가 실행되었을 때, 일반 딕셔너리의 경우 해당 인덱스가 존재하지 않으면 에러를 뱉어내지만 defaultdict()로 인해 즉시 새로운 디폴트 딕셔너리가 만들어진다.
self.table[index] is None 이었다면 인덱스와 매칭되는 value를 찾는 시도 없이 바로 해당 부분에 값을 넣으려는 시도를 하기 때문에 에러가 나게 된다.

 

 

get()

def get(self, key: int) -> int:
        index = key % self.size
        # 찾을 키가 없으면 -1 리턴
        if self.table[index].value is None:
            return -1

        p = self.table[index]
        while p:
            # 키 값과 매칭되는 요소 찾기
            if p.key == key:
                return p.value
            p = p.next

        # 찾아봤는데도 없다면 -1 리턴
        return -1

 

remove()

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

        p = self.table[index]

        # 인덱스의 첫번째 노드일 때. while로 p.next를 해주지 않았으니 첫번째 노드만 비교한다.
        if p.key == key:
            # 인덱스에 들어있는 노드가 하나뿐이면 해당 노드를 빈 노드로 바꿔준다.
            if p.next is None: # p.next가 None이라는 말이 첫번째 노드라는 말과 같다.
            	self.table[index] = ListNode()
                return
                
    	# 연결 리스트 노드 삭제
        prev = p
        while p:
            # 해당 키를 검색.
            if p.key == key:
                prev.next = p.next
            prev = p
            p = p.next

 

인덱스의 첫번째 노드일 때, 삭제 구현을 self.table[index]를 None이 아니라 빈 노드로 바꿔주는 이유가 무엇일까?

만약 None으로 바꾸면

if self.table[index].value is None

이 코드에서 table[index] 자체가 None이기 때문에 .value를 수행할 수 없어서 에러가 나게 된다. 그리고 해시 테이블 객체를 생성하거나 추가할 때, self.table[index]는 빈 노드인 ListNode()로 생성되기 때문에 삭제를 None 대신 빈 노드로 해주는 것이다.

첫번째 노드가 아닌 연결리스트인 노드를 삭제할 때는 먼저 이전 노드인 prev와 현재 노드인 p로 계속 p.next를 수행한다. 

첫번째 노드가 아니라는 말은 이전 노드가 존재한다. 반복문이 돌면 현재 노드는 이전 노드가 되고 (prev) 다음 노드는 현재노드가 되는데, 

이 말이 prev = p를 설명해준다.

 

prev = p
while p:
    # 해당 키를 검색.
    if p.key == key:
        prev.next = p.next
    prev = p
    p = p.next

이전 노드를 p로 지정하고 while문이 돌면서 삭제하려는 노드를 찾게 되고, 이전노드의 다음을 현재 노드의 다음과 연결한다.

이 말은, 현재 노드를 이전노드, 그리고 다음노드와의 연결에서 끊어버리는 것이다. 연결 리스트에서 연결이 끊기면 그 값은 사라지게 된다. 

 

---

마치며

이렇게 해시 테이블 구현 방식을 분석하고 복습해보았다. 얼핏 보면 어려워보이지만 연결리스트 구현과 크게 다르지 않기도 하고 사실 실제로 저렇게 구현해서 쓸 일은 아직 없기 때문에 직접 구현하는걸 달달 외우기보단 흐름을 이해하고 개념을 익히자.