Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q28

Q28 Design HashMap

Q

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

  • MyHashMap() initializes the object with an empty map.
  • void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
  • int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
  • void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Sample Input

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]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Constraints

  • 0 <= key, value <= 106
  • At most 104 calls will be made to put, get, and remove.

1. My Own Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class MyHashMap:

    def __init__(self):
        self.l = [] #[1, a], [2, f], [3, d], [6, g]

    def put(self, key: int, value: int) -> None:
        for x in self.l: #x = [1, a]
            if x[0] == key:
                x[1] = value
                return
        self.l.append([key, value])
        return
        

    def get(self, key: int) -> int:
        for x in self.l: #x = [1, a]
            if x[0] == key:
                return x[1]
        return -1
        

    def remove(self, key: int) -> None:
        for x in self.l: #x = [1, a]
            if x[0] == key:
                self.l.remove(x)
                return
        return

아주 간단한 코드여서 따로 설명할 필요가 없는 것 같다. 위 코드는 정말 적은 메모리만을 사용해서 좋긴 한데 런타임이 너무 길다. 하위 10% 정도…? 좀 더 시간복잡도를 줄인 코드를 알아보자.

2. Given Solution #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class MyHashMap:

    def __init__(self):
        #init size = 1000, if over 1000 get same key(using individual chaining)
        self.size = 1000
        self.table = collections.defaultdict(Node)

    def put(self, key: int, value: int) -> None:
        index = key % self.size
        #No Node -> append then exit.
        if self.table[index].value is None:
            self.table[index] = Node(key, value)
            return
        
        #When Key exist, build up the duplicated values with linked-list.
        p = self.table[index]
        while p:
            #if key already exists, update the value then exit
            if p.key == key:
                p.value = value
                return
            #when index is same but key is not same(like 1 and 1001) -> break then append new node.
            if p.next is None:
                break
            p = p.next
        p.next = Node(key, value)


    def get(self, key: int) -> int:
        index = key % self.size
        if self.table[index].value is None:
            return -1
        #self.table[index] is the node saved in the list. If it's value is none, it doesn't exist.

        #when key exists
        p = self.table[index]
        #search all the node that has same index(but not the same key)
        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]
        #when the target is in the first node
        while p:
            if p.key == key:
                self.table[index] = Node() 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

책에서 주어진 풀이인데 개인적으로는…? 좀 과하게 길게 늘여뜨려 놓은 것 같다. 개별 체이닝 방식으로 구현한 방식이다. 대충 큰 폭에서 설명하자면 1000이라는 사이즈를 임의로 정하고 index는 입력된 key에서 size로 나눈 나머지 (즉 0부터 999까지의 값)으로 할당한다. 혹시라도 중복되는 경우가 생기게 되면(나머지가 같은 경우) 같은 index에서 다음 node로 넘겨서 저장하는 방식으로 구현한다.

전반적인 함수들의 형태를 살펴보면 해당 함수에서 먼저 해당 index 값의 존재 유무를 확인하고(“is None”을 이용해서) 존재하지 않으면 간단하게 끝내고 존재하면 그때부터 깊이 들어간다. put에서는 존재하면 다음 node로 넘겨서 저장하려 한다. get에서는 존재하면 그 인덱스를 들어가서 모든 노드를 다 뒤져서 key와 일치하는 값을 갖고온다. remove에서도 비슷하다.

3. Given Solution #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class MyHashMap:

    def __init__(self):
        #Initialization of list
        self._v = [-1]*1000001
        

    def put(self, key: int, value: int) -> None:
        #all value is non-negative (by constraints)
        self._v[key] = value
        

    def get(self, key: int) -> int:
        #if value is saved already, return the value
        #or return the initial value (-1)
        return self._v[key]
        

    def remove(self, key: int) -> None:
        #initiate the element to -1 (same as deletetion)
        self._v[key] = -1

아주 직관적이면서도 런타임이 아주 적게 걸리는 정말 훌륭한 풀이인 것 같다. 최대로 입력 가능한 값이 1000001개 이하라는 구조적 단점이 있기 때문에 메모리를 아주 많이 잡아먹는다. 다만 런타임이 몹시 빠르기 때문에 굉장히 합리적인 풀이라고 생각한다. 코드를 봐도 딱히 이해할 필요 없이 -1로 초기화하고 시작하며 없으면 그냥 -1를 리턴해버리는, key와 value가 0 이상이라는 점에서 착안한 풀이인 것 같다.

Overall Review

ADT를 다양하게 구현해보면서, 기존에 그냥 막 쓰고 있던 dictionary같은 자료형이 정말 무지막지하게 편한 data structure라는 것을 알게 됐다. 내 풀이처럼 막 구현해버리면 시간을 더럽게 많이 먹거나 세번째 풀이처럼 메모리를 하마같이 먹기 때문에 시간과 메모리 그 사이의 적절한 타협점을 찾아낸게 지금 파이썬의 dictionary가 아닐까…?

*ps. 영어로 후기와 설명을 남기는데에 아주 큰 제약이 걸리는 것 같아서 적어도 당분간은 영어를 포기하고 한글로 작성하려 한다…ㅠ

참고