연결 노드 구현

→ 키와 값을 보관하고 연결 리스트로 처리할 별도의 객체이다.

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

해시맵 구현

→ 초기화, 삽입, 조회, 삭제 기능이 있다.

1. 초기화 구현

   • size에 기본 사이즈를 적당히 설정한다.
   • table은 딕셔너리 대신 편리하게 구현하기 위해 collections.defaultdict를 사용한다.
     • defaultdict 알아보기

   class MyHashMap:
       def __init__(self):
           self.size = 1000  # 해시테이블 사이즈 지정
           self.table = collections.defaultdict(LinkNode)  # defaultdict 생성
   

2. 삽입 구현

   → 해싱 방법 중 정수형 모듈러를 사용한다. 이를 인덱스 값으로 참조한다.

   def put(self, value, key):
           # 해싱 모듈러 사용
           index = key % self.size
   

   → 테이블에서 해당 인덱스값에 존재하지 않는경우 바로 노드를 생성한다.

   if self.table[index].value is None:
               self.table[index] = LinkNode(value, key)
               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 = LinkNode(value, key)

1. 조회 구현

   → 해당 인덱스가 비어있을 경우 -1을 출력

   def get(self, key):
           index = key % self.size
   
           # 해당 인덱스의 table이 비어있으면 -1 출력
           if self.table[index].value is None :
               return -1
   

   → 다음 노드가 있을경우 일치할때까지 이동한다.

   # 다음 노드가 있으면 키값과 일치할때까지 이동
           while p :
               # 일치하면 값 출력
               if p.key == key :
                   return p.value
               p = p.next
   

   → 일치하는 키가 없을 경우 -1 출력

   # 키가 없으면 -1  출력
           return -1
   

2. 삭제 구현

   → 해당 인덱스 값이 없으면 아무것도 하지 않는다.

   def remove(self, key):
           index = key % self.size
           # 해당 인덱스 값이 없으면 나띵
           if self.table[index].value is None :
               return
   

   → 인덱스에서 첫번째 노드일 경우 삭제.

   # (1) 첫번째 인덱스일때 바로 삭제
           p = self.table[index]
           if p.key == key :
               self.table[index] = LinkNode()
   

   → 첫번째가 아닌 다음 노드일 경우 삭제.

   # (2) 연결리스트를 삭제할때
           prev = p
           while p :
               # 일치하는 키를 찾으면 현재 노드를 끊고 다음 노드와 연결
               if p.key == key :
                   prev.next = p.next
                   return
               #
               prev, p = p, p.next