해시테이블

해시

해시 테이블의 핵심은 해시함수이다.
입력값으로 어떤 길이의 값이 주어져도, 해시함수를 통과하게 되면 모두 2바이트의 고정 크기 값으로 매핑된다.

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

다양한 크기의 입력을 해시테이블에 인덱싱 하기 위해 해시 함수를 사용하는 것을 해싱이라고 한다.
이러한 해싱을 통해 정보를 빠르게 저장하고 검색할 수 있게 된다. 이러한 특징 때문에, 해싱은 빠른 검색이 필요한 경우에 사용하면 좋다.

다음의 리스트는 좋은 성능의 해시함수의 특징을 보여준다.

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

충돌이 얼마나 많이 일어날 지에 대해 고민해보기 위해 생일 문제에 대해 짚고 넘어간다.

생일 문제

생일의 가짓수는 365개이다.
생일이 같은 2명이 존재할 확률은 23명만 모여도 50%를 넘어가고 57명이 모이면 99%를 넘어간다.
아래의 파이썬 코드를 통해 생일 문제를 직접 계산해볼 수 있다.

import random

TRIALS = 100000 # 10만번 실험
same_birthdays = 0 # 생일이 같은 실험의 수
birthdays = []
# 10만번 실험 진행
for _ in range(TRIALS):
    birthdays = []
    for i in range(23):
        birthday = random.randint(1, 365)
        if birthday in birthdays:
            same_birthdays += 1
            break
        birthdays.append(birthday)
# 전체 10만 번 실험 중 생일이 같은 실험의 확률
print(f'{same_birthdays / TRIALS * 100}%')

몇 회를 실행해도 항상 50% 이상의 확률이 확인된다.

비둘기집의 원리

그렇다면 왜 충돌이 일어날 수밖에 없을까?
비둘기집의 원리는 이를 설명한다.
n개의 아이템을 m개의 컨테이너에 넣을 때 n>m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어간다는 원리이다.

비둘기집의 원리에 따라 좋은 해시함수는 한번의 충돌만을 일으키겠지만, 좋지 않은 해시함수라면, 9번 모두를 충돌시킬 여지가 있다.

로드팩터

이러한 충돌을 위한 연산값이 있다.
로드팩터이다.
로드팩터란 해시테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것을 의미한다.

load factor = n/k

로드 팩터의 비율에 따라 해시 함수를 재작성해야 할지 또는 해시 테이블의 크기를 조정해야 할지를 결정한다.
자바 10에서는 해시맵의 디폴트 로드팩터를 0.75로 정하고 있다. 로드팩터가 증가할 수록 해시테이블의 성능은 점점 감소하게 되며, 자바10에서는 0.75를 넘을 때 동적 배열처럼 해시 테이블의 공간을 재할당한다.