해시 테이블

해시 맵과 같은 표현
키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형(ADT)을 구현하는 자료구조

가장 큰 특징 : 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1).
=> 덕분에 데이터 양에 관계 없이 빠른 성능 기대 가능

해시 함수란?

임의 크기 데이터를 고점 크기 값으로 매핑하는 데 사용할 수 있는 함수

가장 널리 쓰이는 정수형 해싱 기법 : 나눗셈 방식

	h(x) = x mod m
    
    h(x) : 결과
    x : 입력 값
    m : 해시 테이블 크기, 일반적으로 2의 멱수에 가깝지 않은 소수가 좋음

해싱(Hashing) : 해시 테이블을 인덱싱 하기 위해 해시 함수를 사용하는 것
=> 정보를 가능한 한 빠르게 저장 & 검색하기 위해 사용하는 중요 기법 중 하나.

최적 검색이 필요한 분야에 사용됨. 심볼 테이블 등의 자료구조를 구현하기에도 적합함.

성능 좋은 해시 함수들 특징

• 해시 함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것

로드 팩터(Load Factor)
해시 테이블에 저장된 데이터 개수 n을 버킷 개수 k로 나눈 것
load factor = n/k

=> 로드 팩터 비율에 따라 해시 함수의 재작성 및 크기 조정 여부 결정 & 효율성 측정 가능
로드 팩터 크기와 해시 테이블 성능은 반비례
java 10에서는 0.75 정도를 판단의 기점으로 생각(0.75보다 높으면 재설계)

충돌

해시 값이 같을 때를 일컫음.

해결 방법

• 개별 체이닝(seperate chaining)
  • 충돌 발생 시 연결 리스트로 연결하는 방식
  • 원리
    1. 키의 해시 값 계산
    2. 해시 값을 이용해 배열의 인덱스 구함
    3. 같은 인덱스가 있다면 연결 리스트로 연결
  • 주로 사용되는 방법(But not in Python)
    
• 오픈 어드레싱(open addressing)
  • 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식
  • 전체 슬롯의 개수 이상 저장 불가
  • 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장 없음
  • 클러스터링(clustering, 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상) 발생 가능성 존재
    • 해시 테이블 특정 위치에 데이터 몰리는 현상 발생 => 전체 성능 저하와 직결
  • 일정 이상 채워지면(기준이 되는 로드 팩터 비율을 넘어서게 되면) Growth Factor 비율에 따라 더 큰 크기 or 또 다른 버킷 생성 후 그 곳으로 새롭게 복사되는 리해싱 작업 발생

오픈 어드레싱 방식이 개별 체이닝보다 일정 로드 팩터까지는 효율 우수

Python에서의 해시 테이블

Dictionary, 오픈 어드레싱 방식으로 구현되어있음

Phthon의 로드 팩터 : 0.66

출처 : 파이썬 알고리즘 인터뷰