28. Design HashMap

🎯 leetcode - 706. Design HashMap

---

🤔 나의 풀이 + 오류 수정

📌 문제

- 파이썬 알고리즘 인터뷰 28번 문제

📌 날짜

2020.02.01

📌 시도 횟수

3 try

💡 Code

from collections import defaultdict

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


# 개별 체이닝 방식 + dict로 풀기
class MyHashMap:
    def __init__(self):
        self.hash_map = defaultdict(ListNode)

    def hash_function(self, key): # hash_address를 리턴함
        return key % 1000

    def put(self, key: int, value: int) -> None:
        hash_address = self.hash_function(key)

        # 만약 hash_address에 처음 추가하는 값이라면
        if self.hash_map[hash_address] is None:
            self.hash_map[hash_address] = ListNode(key, value)
            return

        # 이미 hash_address에 값이 존재하는 경우
        node = self.hash_map[hash_address]
        while node:
            # 이미 같은 키가 존재하면 값만 바꾸기
            if node.key == key:
                node.val = value
                return
            # 모든 키를 조사했지만 같은 키가 존재하지 않는다면
            if not node.next:
                break
            node = node.next

        node.next = ListNode(key, value)
        print("     >> 충돌!:", node.next.val)

    def get(self, key: int) -> int:
        hash_address = self.hash_function(key)

        # 해당 hash_address가 비어있다면
        if not self.hash_map[hash_address]:
            return -1

        # 해당 hash_address에 값이 1개 이상 있다면
        node = self.hash_map[hash_address]
        while node:
            if node.key == key:
                return node.val
            node = node.next

        # 다 찾았는데 여전히 키가 같은 것이 존재하지 않는다면
        return -1

    def remove(self, key: int) -> None:
        hash_address = self.hash_function(key)

        # 삭제할 것이 존재하지 않는다면
        if self.hash_map[hash_address] is None:
            return

        prev = node = self.hash_map[hash_address]

        # 만약 삭제할 노드가 첫번째 노드일때
        if node.key == key:
            if node.next:  # 뒤에 노드들이 더 존재하면
                self.hash_map[hash_address] = node.next
            node = None
            return

        # 첫번째 노드가 아니라면 차례대로 검사
        while node:
            if node.key == key:
                prev.next = node.next
                return
            prev = node
            node = node.next

💡 문제 해결 방법

- 파이썬에는 기본적으로 dict라는 오픈 어드레싱 방식의 해시테이블이 존재한다.
- 따라서 위의 풀이에서는 dict를 사용한 개별 체이닝 방식으로 해시테이블을 새롭게 구현했다.

✔ 삽입(put) 함수 구현
1. 입력받은 key의 hash_address를 구한다.
2. 만약 hash_address에 아무것도 없다면 (키, 값)을 삽입하고 종료
3. 만약 hash_address에 노드가 존재한다면 해당 노드와 연결된 연결 리스트를 순회
3-1) 만약 순회 중 이미 같은 키가 존재하면 값만 바꾸고 종료
3-2) 모두 순회했지만 같은 키가 존재하지 않으면 새로운 (키, 값)을 맨 마지막 노드 뒤에 삽입

✔ 조회(get) 함수 구현
1. 입력받은 key의 hash_address를 구한다.
2. 만약 hash_address에 아무것도 없다면 종료
3. 만약 hash_address에 노드가 존재한다면 해당 노드와 연결된 연결 리스트를 순회
3-1) 만약 순회 중 키 값이 같은 노드가 존재한다면 해당 노드의 value를 리턴
3-2) 모두 순회했지만 키가 같은 노드가 없다면 -1을 리턴

✔ 삭제(remove) 함수 구현
1. 입력받은 key의 hash_address를 구한다.
2. 만약 hash_address에 아무것도 없다면 종료
3. prev = node = self.hash_map[hash_address] 라고 미리 설정
4-1) 삭제할 노드가 첫번째 노드인 경우
4-1-(1) 첫번째 노드 뒤에 노드들이 더 연결돼있으면 self.hash_map[hash_address] = node.next
4-1-(2) 첫번째 노드(node)는 None이 되도록 하고 종료
4-2) 삭제할 노드가 n번째 노드인 경우 (n >= 2)
4-2-(1) 순회 중 키 값이 같은 노드가 존재한다면 prev.next = node.next 연결 후 종료
4-2-(2) 아니라면 node가 존재하지 않을 때까지 계속해서 순회

💡 새롭게 알게 된 점

- remove 함수 구현 시, 삭제할 노드가 첫번째 노드인 경우를 미리 처리하면 더 직관적인 코드가 된다.

🌵게시물 다시보기 - 해시 테이블🌵

❌ (한번에 맞추지 못한 경우) 오답의 원인

- ListNode 클래스 구현 시, key의 default 값을 None으로 설정하지 않아 처음에 오류가 생겼다.

---