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

해시맵 디자인

리트코드로 풀러 가기

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

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

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

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

---

개별 체이닝 방식을 이용하여 해시 테이블을 직접 구현해보자.

개별 체이닝 방식을 이용하면, 중복되는 해시 값에 대한 키와 값을 연결 리스트로 묶어서 처리하게 된다.

해시 맵을 구현하는 데에 가장 중요한 것은 해시 함수를 어떻게 작성하는지에 대한 고민이다.

위 문제에서는 모든 키 값을 정수로 지정하였으므로, 현재의 해시 맵의 사이즈와 모듈로 연산을 한 결과를 해시값으로 처리하게끔 하자.

put 메소드 구현

def put(self, key, value):
    index = key % self.size
    ...

위와 같은 연산을 통해 index 값은 해싱된 결과이자, 해시 테이블의 인덱스가 된다.

    if self.table[index].value is None:
        self.table[index] = ListNode(key, value)
        return

다음과 같이 table에 해당 인덱스가 없다면, 추가한다.

만약 인덱스가 있다면, 개별 체이닝 방식을 통하여 처리한다.

체이닝하며 키가 존재한다면 값을 업데이트하고, 키가 없다면 맨 끝에 노드를 붙인다.

    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)

get 메소드 구현

def get(self, key):
    index = key % self.size
    if self.table[index].value is None:
        return -1

key 값을 해시 함수를 통해 인덱스로 만들고 테이블을 인덱스 값으로 조회하여서 값이 없다면 -1를 리턴한다.

    p = self.table[index]
    while p:
        if p.key == key:
            return p.value
        p = p.next
    return -1

테이블에 인덱스 값에 해당하는 리스트 노드가 있다면 차례대로 순회하며 key값이 있는지 조회하고, 없으면 -1를 리턴한다.

remove 메소드 구현

def remove(self, key):
    index = key % self.size
    if self.table[index].value is None:
        return
    ...

remove 또한 위의 get과 크게 다르지 않다.

해시 함수를 통해 인덱스를 구하고, 해당값이 없으면 바로 리턴한다.

    p = self.table[index]
    if p.key == key:
        self.table[index] = ListNode() if p.next is None else p.next

인덱스의 첫 노드일 때, 해당 인덱스를 빈 리스트 노드로 초기화한다.

    prev = p
    while P:
        # 처음 이터레이션일 때는, 위에서 검사했으므로 당연히 넘어간다.
        # 따라서, 다음에 prev는 이전 노드를 가리키게 됨.
        if p.key == key:
            prev.next = p.next
            return
        prev, p = p, p.next

앞의 조건이 false이기 때문에, 처음 실행될 때 p는 첫 노드를 가리키고 있다.

첫 노드의 key값과 일치하는 경우는 앞에서 검사했기 때문에 넘어가게 되며 다음 루프에서 prev값은 첫 번째 노드, p는 두 번째 노드를 가리키게 된다.

루프를 돌며 노드의 key값과 찾을 key값이 같아지게 되면 이전의 노드와 다음 노드를 연결시켜 현재 노드를 삭제한다.

code: MyHashMap.py