[자료구조와 알고리즘] Hash Table

해시테이블이란?

- 해시테이블은 키를 활용하여 값에 직접 접근이 가능한 구조

- 해싱의 장점 : 데이터 양에 영향을 덜 받으면 성능이 빠름 ( 키를 통해 값을 검색함 )

- 파이썬의 딕셔너리는 내부적으로 해시테이블 구조로 구현되어있음

- 해시테이블은 검색을 위한 역할도 하고, 딕셔너리를 위한 자료구조의 역할도 함

- 해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블형태의 자료구조

- 해시함수는 여러 키를 분할하기 위해 키를 해시값 ( 정수값 ) 으로 매칭시키는 역할

- 해싱 ( Hashing ) 은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정

class hash_table:
    def __init__(self):
        self.table = [None for _ in range(256)]

    def hash_function(self, name):
        return ord(name[0])

    def hash_put(self, name, num):
        self.table[self.hash_function(name)] = num

    def hash_search(self, name):
        return self.table[self.hash_function(name)]

▶ 해시성능

- 해시테이블 자체는 충돌을 해결해주지 않음

- O(1) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있음

▶ 해시충돌

- 해시충돌은 키가 들어갈 자리 ( 버킷 ) 가 없는 경우에 발생함

- 충돌이 적은 해시함수를 만드는 것이 해시테이블의 가장 중요한 목적

- 충돌상황을 방지하기 위한 방법으로 체이닝과 오픈어드레싱이 있음

■ 충돌 방지 방법 - 체이닝 ( Chaining )

• 해시 테이블에서 동일한 해시값에 대해 충돌이 일어나면, 그 위치에 있던 버킷에 키값을 뒤이어 연결함
• 체이닝의 원리
  1. 키의 해시값을 계산함
  2. 해시값을 이용해 리스트의 인덱스를 구함
  3. 같은 해시값이 있다면 ( 충돌 한다면 ) 리스트로 연결함
• 충돌을 줄이기 위해, 각 리스트에 대해 연결 ( 리스트 형태 ) 하도록 함

■ 충돌 방지 방법 - 오픈어드레싱 ( Open Addressing )

• 다른 로직의 함수를 활용하기 때문에 Open Addressing 이라 함
• 오픈어드레싱은 비어있는 배열 슬롯이 발견될 때까지 Array의 위치를 검색하여 해시 충돌을 해결함
• 충돌이 일어나는 경우, 탐사 ( Probing ) 를 진행하면서 빈 공간을 찾아야 해결이 됨

▶ 좋은 해시함수란?

- 해시함수를 어떻게 구현하는지에 따라 해시의 성능이 결정됨

- 키와 값의 계산과정이 쉬워야 함

- 충돌을 피할 수 있어야함

▶ 해시를 사용할 때 주의할 점

- 키 데이터타입에 맞는 좋은 해시함수가 있는지 확인

- 적절한 해시테이블 크기 ( 배열크기 )