[LeetCode] #706. Design HashMap (python)

문제

https://leetcode.com/problems/design-hashmap/

Design HashMap - LeetCode

다음 기능을 가지는 해시맵을 디자인해야 한다.

void put(int key, int value) : (key, value) 쌍을 해시맵에 삽입

int get(int key) : 값이 있으면 반환하고 없으면 -1 반환

void 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]

 

 

풀이

 

내 풀이

class MyHashMap:

    def __init__(self):
        self.mymap={}

    def put(self, key: int, value: int) -> None:
        self.mymap[key]=value

    def get(self, key: int) -> int:
        if key in self.mymap.keys():
            return self.mymap[key]
        return -1

    def remove(self, key: int) -> None:
        if key in self.mymap.keys():
            del self.mymap[key]

딕셔너리를 사용해서 풀었다.

 

 

책 풀이

개별 체이닝 방식

import collections


# Definition for singly-linked list.
class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None


class MyHashMap:
    # 초기화
    def __init__(self):
        self.size = 1000
        self.table = collections.defaultdict(ListNode)

    # 삽입
    def put(self, key: int, value: int) -> None:
        index = key % self.size
        # 인덱스에 노드가 없다면 삽입 후 종료
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return

        # 인덱스에 노드가 존재하는 경우 연결 리스트 처리
        p = self.table[index]
        while p:
            if p.key == key:
                p.value = value
                return
            if p.next is None:
                break
            p = p.next
        p.next = ListNode(key, value)

    # 조회
    def get(self, key: int) -> int:
        index = key % self.size
        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
        return -1

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

        # 인덱스의 첫 번째 노드일때 삭제 처리
        p = self.table[index]
        if p.key == key:
            self.table[index] = ListNode() if p.next is None else p.next
            return

        # 연결 리스트 노드 삭제
        prev = p
        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev, p = p, p.next

개별 체이닝 방식이란?

해싱한 결과가 충돌하면 충돌한 값들을 서로 연결리스트로 연결하는 방식이다.

키의 해시 값을 계산하고 해시 값을 이용해 배열의 인덱스를 구한 다음에 같은 인덱스가 있다면 연결 리스트로 연결하는 것이다.

 

연결리스트 객체를 구현하기 위해 ListNode 클래스를 정의한다. 해당 클래스 안에는 키, value 값이 있다.

초기화 : 기본 사이즈를 설정하고 ListNode를 담기위해 defaultdict를 사용했다.

put : 해시 값은 키를 size로 모듈러 연산한 결과로 정한다. 만약 해당 인덱스에 아무 값도 없으면 삽입하고 종료한다. 만약 값이 있으면, 즉 충돌이 발생하면 연결리스트로 연결한다. 키가 이미 존재하면 값을 업데이트하고 기존에 존재하지 않았던 키라면 노드를 연결한다.

get : 우선 인덱스를 계산하고 해당 인덱스에 값이 있는지 확인한다. 노드가 있으면 p.next를 하면서 같은 키 값을 가지는 노드를 찾아서 값을 반환한다.

remove : 첫번째 노드일때와 아닐 때를 나눠서 처리한다. 첫번째 노드를 삭제할 때 빈노드를 할당하는 이유는 그렇지 않으면 앞에서 추가, 조회 연산을 할때 에러가 발생하기 때문이다.

연결된 노드를 삭제할 때 일치하는 노드를 만나면 다다음 노드를 연결해주는 방식으로 삭제한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰