LeetCode [706]: Design HashMap

📌 LeetCode [706]: Design HashMap

🔗 문제 링크

---

문제 설명 📄

사용자 정의 해시맵(HashMap)을 구현하는 문제입니다.
다음 세 가지 연산을 지원해야 합니다:

1. put(key, value): 주어진 키(key)와 값(value)을 삽입합니다. 만약 키가 이미 존재한다면, 값을 업데이트합니다.
2. get(key): 주어진 키(key)에 해당하는 값을 반환합니다. 키가 존재하지 않으면 -1을 반환합니다.
3. remove(key): 주어진 키(key)를 제거합니다.

조건:

• 키와 값은 (0 \leq key, value \leq 10^6).
• 최대 (10^4)번의 호출이 발생합니다.

---

문제 접근 방식 📋

1. 간단한 배열 구현:
   • 고정 크기의 배열을 사용하여 인덱스를 키로 활용합니다.
   • (key) 값을 그대로 배열의 인덱스로 사용하므로 해싱이 필요하지 않습니다.
2. 해싱 기반 구현:
   • 체이닝 방식으로 충돌을 처리하는 해시 테이블을 설계합니다.
   • 작은 고정 크기 배열(예: 소수 크기)과 해싱을 사용하여 키의 충돌을 처리합니다.

---

Solution 💻

class MyHashMap:

    def __init__(self):
        self.hashMap = [-1] * (10**6 + 1)

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

    def get(self, key: int) -> int:
        return self.hashMap[key]

    def remove(self, key: int) -> None:
        self.hashMap[key] = -1

시간 복잡도 분석 ⏲️

• 시간 복잡도:
  • put, get, remove: 모두 (O(1)) (상수 시간).
• 공간 복잡도:
  • 배열 크기가 (10^6 + 1)이므로 (O(10^6)).

---

리팩토링 🛠️

개선된 코드

class MyHashMap:

    def __init__(self):
        self.size = 10007 
        self.hashMap = [[] for _ in range(self.size)]

    def hashFunction(self, key: int) -> int:
        return key % self.size

    def put(self, key: int, value: int) -> None:
        hash_key = self.hashFunction(key)
        for i, (k, v) in enumerate(self.hashMap[hash_key]):
            if k == key:
                self.hashMap[hash_key][i] = (key, value)
                return
        self.hashMap[hash_key].append((key, value))

    def get(self, key: int) -> int:
        hash_key = self.hashFunction(key)
        for k, v in self.hashMap[hash_key]:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        hash_key = self.hashFunction(key)
        for i, (k, _) in enumerate(self.hashMap[hash_key]):
            if k == key:
                self.hashMap[hash_key].pop(i)
                return

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도:
  • 평균: (O(1)) (충돌이 적을 경우).
  • 최악: (O(k)) (충돌로 인해 버킷에 저장된 키 개수가 (k)일 경우).
• 공간 복잡도:
  • 배열 크기가 (10007)이며 체이닝을 통해 추가 공간을 사용. 평균적으로 (O(n))의 공간 소모.

---