706 해시맵 디자인

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

def lookup(d, key):
    h = hash(key)           # step 1
    cl = d.data[h]          # step 2: d.data는 `buckets` 또는 `충돌 리스트` 배열
    for pair in cl:         # step 3
        if key == pair[0]:  # pair는 tuple인가?
            return pair[1]
    else:
        raise KeyError, "Key %s not found." % key

- 해시 함수 값 충돌의 최소화
  - 고정 크기 값으로 변환하면서 같은 값이 나올 수 있기 때문
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
  - 최대한 겹치지 않도록
- 해시 테이블 사용 효율이 높을 것

# https://myshell.co.uk/blog/2018/11/python-f-string-formatting-cheatsheet/ 
def print_bitwise(a, op = None, b = None):
    print('============================================')
    print("a: ", a, ",op: ", op, ",b: ", b)
    if a:
        a_in_64b = f"{a:64b}"
        a_in_64b_len = str(len(a_in_64b) - a_in_64b.count(' '))
        print(a_in_64b + " [" + a_in_64b_len + "]")
    if b:
        b_in_64b = f"{b:64b}"
        b_in_64b_len = str(len(b_in_64b) - b_in_64b.count(' '))
        print(b_in_64b + " [" + b_in_64b_len + "]")

    if a and b and op:
        print('--------------------------------------------')
        if op == '&':
            result = a & b
        elif op == '|':
            result == a | b
        result_in_64b = f"{result:64b}"
        result_in_64b_len = str(len(result_in_64b) - result_in_64b.count(' '))

        print(result_in_64b + " [" + result_in_64b_len + "]")
        print(f"{result:n}")

print_bitwise(222)
print_bitwise(-222)
print_bitwise(0x7FFFFFFF)
print_bitwise(-0x80000000)
print_bitwise(222, '&', 0x7FFFFFFF)
print_bitwise(2147483648, '&', 0x7FFFFFFF)
print_bitwise(98989898989898, '&', 0x7FFFFFFF)
print_bitwise(-222, '&', 0x7FFFFFFF)
'''
============================================
a:  222 ,op:  None ,b:  None
                                                        11011110 [8]

============================================
a:  -222 ,op:  None ,b:  None
                                                       -11011110 [9]

============================================
a:  2147483647 ,op:  None ,b:  None
                                 1111111111111111111111111111111 [31]

============================================
a:  -2147483648 ,op:  None ,b:  None
                               -10000000000000000000000000000000 [33]

============================================
a:  222 ,op:  & ,b:  2147483647
                                                        11011110 [8]
                                 1111111111111111111111111111111 [31]
--------------------------------------------
                                                        11011110 [8]
222

============================================
a:  2147483648 ,op:  & ,b:  2147483647
                                10000000000000000000000000000000 [32]
                                 1111111111111111111111111111111 [31]
--------------------------------------------
                                                               0 [1]
0

============================================
a:  98989898989898 ,op:  & ,b:  2147483647
                 10110100000011111100001110001000000000101001010 [47]
                                 1111111111111111111111111111111 [31]
--------------------------------------------
                                 1100001110001000000000101001010 [31]
1640235338

============================================
a:  -222 ,op:  & ,b:  2147483647
                                                       -11011110 [9]
                                 1111111111111111111111111111111 [31]
--------------------------------------------
                                 1111111111111111111111100100010 [31]
2147483426
'''

class MyHashMap:
    PRIME = 31  # 문제의 키가 정수로만 넘어와서 사실 필요 없는 변수
    TABLE_SIZE = 300

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

    def __init__(self):
        self.hash_table = [None] * self.TABLE_SIZE

    """
    index와 key는 다르다!
    """
    def put(self, key: int, value: int) -> None:
        """
        value will always be non-negative.
        """
        index = self.get_index(key)
        head = self.hash_table[index]
        if head is None:
            self.hash_table[index] = self.ListNode(key, value)
            return None
        else:
            # 새로운 리스트 노드를 앞에 붙여야 할까? 아니면 뒤에 붙여야 할까?
            while head is not None:
                if head.key == key:
                    # 키가 같으면 넘어온 값으로 치환하고 종료
                    head.value = value
                    return None
                if head.next is not None:
                    head = head.next
                else:
                    break
            # next에 붙여 나갈 생각을 했는데, 오히려 가장 앞에 붙이는 게 더 편하다
            # 새로운 노드를 "가장 앞"에 추가하여 hash_table에 삽입
            self.hash_table[index] = self.ListNode(key, value, self.hash_table[index])

            return None

    def get(self, key: int) -> int:
        head = self.hash_table[self.get_index(key)]
        while head is not None:
            if head.key == key:
                return head.value
            head = head.next

        return -1

    def remove(self, key: int) -> None:
        index = self.get_index(key)
        head = self.hash_table[index]
        if head is None:
            return None
        else:
            # key에 해당 하는 노드 제거
            # 이전 노드와 다음 노드를 이어준다
            # 첫번째 헤드에 해당하면 바로 다음 노드로 덮어 쓴다
            if head.key == key:
                self.hash_table[index] = head.next
                return None
            # https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
            while head is not None:
                if head.key == key:
                    break
                node_prev = head
                head = head.next

            # AttributeError: 'NoneType' object has no attribute 'next'
            # key에 해당하는 게 없으면 None일 수 있으므로, None 아닌 경우에만 삭제 처리
            if head is not None:
                node_prev.next = head.next

            return None

    # 정수만 들어오므로 테이블 크기로 모듈러 연산만 한다
    def get_index(self, key: int):

        return key % self.TABLE_SIZE