[파이썬 알고리즘]해시맵 디자인

문제.

• put(key, value) : 키 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다.

• get(key) : 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.

• remove(key) : 키에 해당하는 키, 값을 해시맵에서 삭제한다.

 

MyHashMap hashMap = new MyHashMap();

hashMap.put(1, 1);

hashMap.put(2, 2);

hashMap.get(1);                 // 1을 리턴한다

hashMap.get(3);                 // -1을 리턴한다(키가 존재하지 않음)

hashMap.put(2, 1);              // 값을 업데이트한다

hsahMap.get(2);                 // 1을 리턴한다

hashMap.remove(2);            // 키 2에 해당하는 키, 값을 삭제한다.

hashMap.get(2);                 // -1을 리턴한다 ( 키에 삭제되어 존재하지 않음)

 

 

해시맵을 처음보기도 하고, 익숙치 않아 책에 있는 개별 체이닝 방식을 이용한 해시 테이블 구현을 따라해가며 익혀갔다. 다음은 책에 있는 내용이다.

 

 

풀이 1) 개벌 체이닝 방식을 이용한 해시 테이블 구현

import collections


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


class MyHashMap:
    # 초기화
    def __int__(self, key=None, value=None):
        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