📝 해시 테이블

개별체이닝 방식 해시 테이블 구현

import collections


class Hashmap:
    def __int__(self):
        self.size = 1000
        # 존재하지 않는 키를 조회할 경우 자동으로 디폴트를 생성 : collections.defaultdict()
        self.table = collections.defaultdict(ListNode)

    def put(self, key: int, value: int) -> None:
        index = key % self.size
        # 인덱스에 노드가 없다면 삽입 후 종료
        '''
        self.table[index] is None 이 아닌이유 ? ( 굳이 value 를 찾아 비교한 이유 )
        -> collections.defaultdict(ListNode) 때문 
         위는 존재하지 않는 인덱스로 조회를 시도할 경우 에러를 발생하지 않고 그 자리에서 바로 디폴트
         객체를 생성, 여기서는 defaultdict(ListNode) 로 선언하여서 존재하지 않는 인덱스를 
         조회할 경우 바로 빈 ListNode 를 생성한다. 
         즉 디폴트객체를 생성하였을 수도 있으니 value 값으로 확인을 해뵈야함
        '''
        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[key]
        while p:
            if p.key == key:
                return p.value
            # 연결리스트로 연결하기 위해 p 값을 다음값으로 업데이트
            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 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

‼️ 알아두어야 할 부분

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

🤔 self.table[index] is None 이 아닌이유는 ? 굳이 value 를 찾아 비교한 이유는?

• collections.defaultdict는 Python의 표준 라이브러리 collections에 포함된 딕셔너리의 서브클래스이다. defaultdict의 주요 특징은 딕셔너리에 존재하지 않는 키로 조회를 시도할 때, 에러를 발생시키지 않고 대신 미리 정의된 디폴트 값(또는 객체)를 자동으로 생성하여 해당 키의 값으로 설정한다는 점이다.
• 이 코드에서 self.table = collections.defaultdict(ListNode)라고 선언함으로써, self.table 딕셔너리는 존재하지 않는 키로 조회를 시도할 경우 자동으로 ListNode 객체를 생성하게 된다. 여기서 ListNode는 연결 리스트의 노드를 나타내는 클래스로 가정하며, 키-값 쌍을 저장하는 데 사용된다.
• collections.defaultdict(ListNode)를 사용하였기 때문에, self.table에서 존재하지 않는 인덱스로 접근을 시도하더라도 defaultdict는 자동으로 그 자리에서 빈 ListNode 객체를 생성하고 반환합니다. 이는 딕셔너리에 index 키가 실제로 존재하지 않더라도 에러를 발생시키지 않고 처리할 수 있게 해줍니다.

-> 즉 defaultdict 로 인해 생성된 "빈 객체의 공간" 인지 확인을 해주는 것!!