[알고리즘][해시 테이블] - 1. 해시맵 디자인

 

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/design-hashmap/submissions/

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

---

[해시]

• 임의 크기의 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 해시라고 한다.
• 해시 테이블의 핵심은 해시 함수고 이때 해시 함수를 사용하는 것을 해싱이라고 한다.
• 파이썬의 경우 딕셔너리를 사용해서 해시 테이블을 구현한다.
• 파이썬은 해시 테이블 충돌 시 오픈 어드레싱을 사용해서 대처하고 이 이유는 malloc으로 메모리 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다. (자바나 C++은 개별 체이닝 방식을 사용하여 해시테이블 충돌 시 대처한다.)

[개별 체이닝 방식을 이용한 해시 테이블 구현]

import collections

class ListNode(object):
    def __init__(self,key = None,value=None):
        self.value = value
        self.key = key
        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