[해시] 개념

해시

• 해시 테이블, 해시 맵 : 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조이다.
• 해시 함수 : 임의 크기 데이터를 고정 크기 값으로 매핑하는 함수
  ABC -> A
  13245BC -> B2
  ANE34 -> D4
  위의 예시처럼 입력의 길이가 달라도 고정 크기(2) 값으로 변환한다.
• 해시 함수는 checksum, 손실 압축, 무작위화 함수, 암호 등과도 관련이 깊다.
• 성능이 좋은 해시 함수의 특징 : 해시 함수 값 충돌의 최소화, 쉽고 빠른 연산 등...

생일 문제(Birthday Problem)

여러 사람이 모였을 때 생일이 같은 2명이 존재할 확률은 비둘기집의 원리(Pigeonhole Principle)에 따라 366명 이상이 모여야 일어나는 일 같지만, 실제로는 23명만 모여도 발생할 확률이 50%가 넘는다. 생일 문제를 코드로 작성해서 직접 실험해보면 다음과 같다.

import random

TRIALS = 100000  # 10만번 실험
same_birthdays = 0  # 생일이 같은 실험의 수

for _ in range(TRIALS):
    birthdays = []

    # 23명이 모였을 때 생일이 같으면 same_birthdays += 1
    for i in range(23):
        birthday = random.randint(1, 365)
        if birthday in birthdays:
            same_birthdays += 1
            break
        birthdays.append(birthday)

print(f'{same_birthdays / TRIALS * 100}%')  # 50.806%

위의 실험을 통해 23명이 모이는 경우를 10만번 실험했을 때 생일이 같을 확률이 50%가 넘는 것, 충돌은 생각보다 쉽게 발생하는 것을 확인할 수 있다.

비둘기집 원리(Pigeonhole Principle)

n개의 아이템을 m개의 컨테이너에 넣을 때, n>m 이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 말한다.

9개의 공간이 있는 곳에 10개의 아이템이 들어온다면 반드시 1번 이상 충돌은 발생하게 된다. 좋은 해시 함수라면 충돌 횟수를 최소화해 1번의 충돌만 발생하겠지만, 좋지 않은 해시 함수의 경우 심하면 9번 충돌이 일어날 수도 있다.

로드 팩터(Load Factor)

로드 팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것이다.
load factor = n/k

로드 팩터 비율에 따라서 해시 함수의 재작성 여부와 해시 테이블 조정 여부를 결정한다. 이 값은 해시 함수가 키들을 잘 분산해 주는지를 의미하는 효율성 측정에도 사용된다.
일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소한며 자바10에서는 0.75를 넘으면 해시 테이블의 공간을 재할당한다.

해시 함수

해싱(Hashing)이란: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것

충돌 발생 시 해결 방법

1) 개별 체이닝
충돌 발생 시 연결 리스트로 연결하는 방식

1) 키의 해시 값을 계산한다.
2) 해시 값을 이용해 배열의 인덱스를 구한다.
3) 같은 인덱스가 있다면 연결 리스트로 연결한다.
'윤아'와 '서현'아이템이 충돌한 경우, '윤아'의 다음 아이템이 '서현'으로 연결됨

2) 오픈 어드레싱
충돌 발생 시 빈 공간을 찾는 방식
체이닝 방식은 무한정 저장할 수 있지만, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 오픈 어드레싱 방법 중 가장 간단한 방식인 선형 탐사(Linear Probing)방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 빈 공간이 있는지 확인하며, 이미 선점되어 있으면 다음 위치를 확인한다.

선형 탐사의 한 가지 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다는 점이다. 해시테이블 곳곳에 연속된 데이터 그룹이 생기는 것을 클러스터링(Clustering)이라고 하는데, 이 현상은 전체적으로 해싱 효율을 떨어뜨린다.

• 해시 테이블로 구현된 파이썬의 자료형은? 딕셔너리
  파이썬의 딕셔너리는 오픈 어드레싱 방식으로 구현되어 있다.
  체이닝 시 malloc으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다.

파이썬이 체이닝을 사용하지 않는 이유: 연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요한데, 추가 메모리 할당은 상대적으로 느리기 때문이다.

References
파이썬 알고리즘 인터뷰