해시 테이블

해시 함수

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

ABC    -> A1
1324BC -> CB
AF32B  -> D5

• 위 입력값의 길이가 각각 3,6,5로 다르지만, 화살표에 해당하는 해시 함수를 통과하면 2바이트의 고정 크기 값으로 매핑됨.

해시 함수 활용 분야

• 심볼 테이블, 체크섬, 손실 압축, 무작위화 함수, 암호 등

성능 좋은 해시 함수들 특징

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

생일 문제

• 생일이 같은 2명이 존재할 확률은 23명만 모여도 50%를 넘고, 57명이 모이면 그때부터는 99퍼를 넘음 ↔ 비둘기집 원리
  

로드 팩터

해시 테이블에 저장된 데이터 개수 n을 버킷 k로 나눈 것

• 자바 10은 0.75, 파이썬은 0.5

클러스터링

선형 탐사시 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 현상

• 탐사 시간이 $O(n)$ 이 걸리는 것이 아닌가?

해시 테이블 충돌 해결

개별 체이닝

• 충돌 발생 시 연결 리스트로 연결
• 데이터의 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용하기도 함

오픈 어드레싱

• 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식
• 전체 슬롯의 개수 이상은 저장할 수 없음
• 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결
• 기준이 되는 로드 팩터 비율을 넘어서게 되면, 그로스 팩터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업 일어남
  • 동적 배열에서 공간이 가득 찰 경우, 더블링으로 새롭게 복사해서 옮겨가는 과정과 유사

파이썬의 해시 테이블 충돌 해결

→ 오픈 어드레싱 방식

• 체이닝 시 malloc으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다
• 연결 리스트를 만들기 위해서는 추가 메모리 할당이 추가하고, 추가 메모리 할당은 상대적으로 느린 작업이기 때문에 택하지 않음
• 선형 탐사는 로드 팩터 비율이 높아질수록 조회당 평균 캐시 실패가 높아지는 문제가 있어 파이썬은 로드팩터를 자바(0.75)에 비해 작게 잡음(0.66)