11장. 해시 테이블 (3) - 충돌 처리 방식 (개별 체이닝 파이썬 구현)

 

 

다음의 기능을 제공하는 해시맵을 디자인하라.
- put(key, value): 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다. 
- get(key, value): 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.
- remove(key, value): 키에 해당하는 키, 값을 해시맵에서 삭제한다. 

 

풀이1. 개별 체이닝 방식을 이용한 해시 테이블 구현

 

그림1. 개별 체이닝 방식

 

우리가 구현할 MyHashMap 클래스의 전체 메소드는 아래와 같다.

• 초기화 __init__()
• 삽입 put()
• 조회 get()
• 삭제 remove()

class MyHashMap:
    def __init__(self):
        
    def put(self, key:int, value: int) -> None:
    
    def get(self, key:int) -> int:
        
    def remove(self, key:int) -> None:

 

 

이외에도 키, 값을 보관하고 연결 리스트로 처리할 별도의 객체를 구현해야 하는데, 여기서는 ListNode 클래스를 정의한다.

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

 

---

이제 MyHashMap에서 초기화부터 구현하자. 

import collections

class MyHashMap:
    def __init__(self):
        self.size = 1000   # 기본 해시 테이블 크기
        self.table = collections.defaultdict(ListNode)

•  self.size는 해시 테이블의 크기를 나타내며, 기본적으로 1,000으로 설정
• selt.table은 defaultdict로 생성되며, 각 인덱스에 ListNode 객체를 기본값으로 저장
• defaultdict를 사용하면 존재하지 않은 키를 조회할 경우 자동으로 ListNode 객체가 생성된다. 

---

이제 삽입 메소드 put()을 구현해보자.

class MyHashMap:
    def __init__(self):
        self.size = 1000
        self.table = collections.defaultdict(ListNode)
        
    def put(self, key:int, calue: int) -> None:
        index = key % self.size   # 해시 테이블의 인덱스 계산
        
        # 현재 인덱스가 비어있다면, 새로운 ListNode를 삽입
        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)

 

• 해시 함수: index = key % self.size를 통해 해시 테이블의 인덱스를 계산한다. 해시 함수의 결과로 size 개수 범위 내의 값을 얻는다.
• 빈 공간에 삽입: if self.table[index].value is None 조건을 통해 해당 인덱스가 비어 있는지 확인한다. 비어 있으면 새로운 ListNode를 추가하고 종료한다.
• 해시 충돌 처리: 만약 해시 충돌이 발생하여 이미 값이 있는 인덱스라면, 체이닝 기법을 사용하여 연결된 리스트에 새로운 노드를 추가한다.
  • p = self.table[index]로 첫 노드를 설정하고, while p 루프를 통해 충돌이 발생한 노드를 순차적으로 탐색한다.
  • 종료 조건: 이미 키가 존재하면 값을 업데이트하고 종료한다. 그렇지 않으면 리스트의 끝에 새 노드를 추가한다.

 

put() 메소드 동작 예시

1. hash_map.put(1, 10)

• index = 1 % 1000 = 1이므로 self.table[1]이 참조
• 이때, self.table[1]은 아직 값이 없으므로 if self.table[index].value is None 조건이 참
• 조건이 만족되었으므로, self.table[1] = ListNode(1, 10)으로 새로운 노드를 삽입
• 결과: self.table[1]에는 ListNode(key=1, value=10)이 저장

2. hash_map.put(1001, 20)   # 해시 충돌 발생

• ndex = 1001 % 1000 = 1이므로, self.table[1]에 저장하려고 시도
• 이때 self.table[1].value는 이미 10이므로 if self.table[index].value is None 조건은 거짓
• 따라서 p = self.table[index]로 p를 현재 노드(ListNode(1, 10))로 설정
• while p 루프에서 p.key == key 조건을 확인하는데, 현재 노드의 키는 1이고, 삽입하려는 키는 1001이므로 조건이 거짓
• if p.next is None 조건을 확인해 p.next가 None임을 알 수 있다. 즉, 현재 노드가 체인의 마지막 노드
• 조건이 참이므로, p.next = ListNode(1001, 20)로 새로운 노드를 연결
• 결과: self.table[1]의 체인은 ListNode(1, 10) -> ListNode(1001, 20)

3. hash_map.put(1, 30)   # 기존 키 1의 값을 (1,30)으로 업데이트

• index = 1 % 1000 = 1이므로, 다시 self.table[1]을 참조
• self.table[1]에는 이미 값이 있으므로, if self.table[index].value is None 조건은 거짓
• p = self.table[index]로 p를 ListNode(1, 10)로 설정
• while p 루프에서 p.key == key 조건을 확인하는데, 현재 노드의 키가 1이므로 조건이 참
• 조건이 참이면 p.value = value로 노드의 값을 30으로 업데이트하고 종료
• 결과: self.table[1]의 체인은 ListNode(1, 30) -> ListNode(1001, 20)로 변경

 

---

 

이제 조회 메소드 get()을 구현해보자

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

• 해당 인덱스에 값이 None이면, 해당 키는 테이블에 없으므로 -1 반환
• 체이닝을 통한 탐색
  • p = self.table[index]로 해당 인덱스의 첫 번째 노드에서 탐색을 시작
  • while p 루프를 통해 체인(연결 리스트)을 따라가면서 원하는 키를 찾는다.
    • 키 비교: if p.key == key 조건에서 현재 노드의 키와 조회하려는 키가 일치하면, 해당 노드의 value를 반환
    • 다음 노드로 이동: 키가 일치하지 않으면 p = p.next로 다음 노드로 이동해 계속 탐색
  • 종료 조건: 체인 끝까지 키를 찾지 못하면 -1을 반환하여 해당 키가 없음을 알린다.

---

이제 remove() 메소드를 살펴보자.

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

• 첫 번째 노드 삭제:
  • p = self.table[index]로 해당 인덱스의 첫 번째 노드부터 확인
  • if p.key == key 조건에서 첫 번째 노드의 키가 삭제하려는 키와 같으면, self.table[index]를 갱신하여 첫 번째 노드를 제거
  • 이때, 첫 번째 노드의 다음 노드가 존재하면 self.table[index]에 p.next를 할당하고, 존재하지 않으면 새로운 빈 노드(ListNode())로 설정
• 연결 리스트 중간 노드 삭제:
  • 첫 번째 노드가 아니라면 prev와 p를 사용해 현재 노드(p)의 이전 노드(prev)와 현재 노드를 계속 연결하며 탐색합니다.
  • if p.key == key 조건에서 일치하는 노드를 찾으면 prev.next = p.next로 현재 노드를 리스트에서 삭제합니다.
  • 노드 삭제 후 return하여 메서드를 종료합니다.

---

[전체 코드]

import collections

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