해시 테이블

해시 테이블

• 해시 테이블(맵)은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형을 구현하는 자료구조!
• 해시 테이블의 가장 큰 특징은 삽입, 삭제, 탐색 등 연산의 시간복잡도가 O(1)
  • 데이터 양과 관련 없이 빠른 속도를 기대할 수 있음
• 해시함수는 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있다!
• 해시 테이블을 인덱싱하기 위해서 해시함수를 사용하는 것을 해싱(Hashing)이라고 한다!
• 해시 함수 값이 충돌을 최소화 시켜서 성능이 좋게 만들 수 있다!

---

로드 팩터

• 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것! → 공간이 얼마나 차있는 지!
  • load factor = n/k
• 로드 팩터 비율에 따라서 해시 함수를 재작성해야 할지 또는 테이블의 크기를 조정해야할 지를 결정!
• 일반적으로 로드 팩터가 증가할 수록 해시 테이블 성능은 점점 감소한다!

해시 함수

• 가장 단순하면서도 널리 쓰이는 정수형 해싱 기법인 모듈러 연산을 이용한 나눗셈 방법!
• h(x) = x mod m
• h(x)는 입력값 x의 해시 함수를 통해 생성된 결과이다.
• m은 해시 테이블의 크기로 일반적으로 2의 멱수에 가깝지 않은 소수를 선택하는 것이 좋다!!

충돌이 일어날 때는 어떻게 대처할까?

개별 체이닝

• 해시 테이블의 기본방식이기도 한 개별 체이닝은 충돌 발생 시 해시테이블 인덱스에 해당하는 공간에 연결 리스트로 연결하는 방식이다!

1.  키의 해시 값을 계산한다.
2.  해시 값을 이용해 배열의 인덱스를 구한다
3.  같은 인덱스가 있다면 연결리스트로 연결!

• 잘 구현한다면 대부분의 탐색은 1이겠지만, 최악의 경우에 한 인덱스에 모든 값이 연결되면 시간복잡도가 O(n)이 되어버린다!

오픈 어드레싱

• 한 곳에 하나만 저장하고 싶고 지금 받은 값이 충돌이 일어나면 다른 공간을 찾음! 
• 하지만, 이러한 이유 때문에 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다!
• 선형 탐사의 한 가지 문제점은 해시 테이블에 저장되는 데이터들이 뭉치는 경향을 보인다. (클러스터링)
• 또한, 오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에 삽입할 수 없다!

개별 체이닝 vs 오픈 어드레싱

 

• 오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다
• 그러나 슬롯의 80% 이상이 차게 되면 급격한 성능 저하가 일어난다!
• 모든 언어들은 오픈 어드레싱 방식을 채택해 성능을 높이는 대신, 로드 팩터를 작게 잡아 성능 저하 문제를 해결!

---

파이썬의 해시 테이블 구현 방식

• 해시 테이블로 구현된 파이썬의 자료형은 딕셔너리이다!
• 파이썬에서 해시 테이블에 충돌이 일어나면 오픈 어드레싱 방식을 사용!

파이썬에서 해시 테이블 문제가 나오면 딕셔너리를 활용하면 된다!

• 내부적으로는 해시 테이블로 구현
• 파이썬 3.7+에서는 입력 순서가 유지

연산	시간 복잡도	기능
len(dict)	O(1)	딕셔너리 요소 개수 리턴
dict[key]	O(1)	키를 조회하여 값을 리턴
dict[key] = value	O(1)	키와 값을 삽입
key in dict	O(1)	딕셔너리에 키가 존재하는지 확인

리스트와 꼭 비교해볼 부분

• 리스트는 안에 요소가 있는지 확인하는 in 연산이 O(n) 시간이 걸리지만 딕셔너리는 O(1) 시간이 걸린다!

개별 체이닝 방식으로 구현해보기

## 개별 체이닝을 사용하는 HashMap

from collections import defaultdict


class ListNode:
    # key와 value 가짐
    # 예를들어 key가 사람 이름 value가 나이
    # defaultDict를 사용하기 때문에 비교문에 사용하기 위해 None값을 넣어줌
    def __init__(self, key=None, val=None, next=None):
        self.key = key
        self.val = val
        self.next = next


class HashMap:

    def __init__(self):
        self.size = 1000
        self.table = defaultdict(ListNode)

    # 키와 값 추가
    def put(self, key: int, val: int) -> None:
        # key는 정수로만 구현함
        index = key % self.size
        # 해당 인덱스가 비어있을 경우
        # if not self.table[index]로 조회하지 않는 이유는
        # defaultDict 를 사용해서 조회를 하면 해당 인덱스에 해당하는
        # 객체가 자동 생성되기 때문이다!
        if not self.table[index].val:
            self.table[index] = ListNode(key, val)
            return

        # 그렇지 않으면 첫번째 노드부터 확인해서 linkedlist로 맨 뒤에 넣어준다!
        node = self.table[index]
        while node:
            # 이미 해당 키값을 가지는 노드가 있으면 업데이트
            if node.key == key:
                node.val = val
                return
            # node의 뒤가 없으면 삽입
            if not node.next:
                node.next = ListNode(key, val)
                return
            node = node.next
    # 키로 값 조회
    def get(self, key):
        index = key % self.size
        # 인덱스에 해당하는 테이블 비어있을 때
        if not self.table[index].val:
            return -1
        # 인덱스가 있을 때 첫번째부터 확인!
        node = self.table[index]
        while node:
            if node.key == key:
                return node.val
            node = node.next
        # 탐색을 다하고도 키를 못찾으면 -1 리턴
        return -1
    # 삭제
    def remove(self, key: int):
        index = key % self.size
        # 요소를 삭제할 인덱스가 비어있으면
        if not self.table[index].val:
            return -1

        # 인덱스가 있으면 첫번째 요소부터 탐색하여 삭제시작
        node = self.table[index]

        # 첫번째 요소일 때
        if node.key == key:
            # 첫번째 다음에 요소가 없으면 None이 아닌 ListNode()로 할당한다
            # 어차피 table[index]로 조회하면 defaultDict이기 때문에 알아서 Listnode를 할당한다!
            # 만약 None으로 할당해면 추가, 조회 함수에서
            # not self.table[index].val으로 비교할 때 오류가 발생한다!
            # 다음 요소가 있으면 값만 바꿔주면 된다 링크드 리스트 헤더 바꾸듯
            self.table[index] = ListNode() if not node.next else node.next
            return

        # 첫번째 요소가 아니면 끝까지 찾아서 삭제함
        prev = node
        while node:
            prev, node = node, node.next
            if node.key == key:
                prev.next = node.next
                return
        # 만약 삭제할 요소가 없다면 -1 반환
        return -1


hash = HashMap()
hash.put(0, 'a')
hash.remove(0)
hash.put(0, 'a')
hash.put(100,'b')
print(hash.get(0), hash.get(100))