책 리뷰/파이썬 알고리즘 인터뷰

11장. 해시 테이블 (1) - 해시 함수의 이해

조조링 2024. 10. 29. 11:12
728x90
반응형

 

 

해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료구조이다. 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 

 

 

 

해시 함수와 해싱의 이해

  • 해시 함수는 임의의 크기를 가진 데이터를 고정된 크기 값으로 변환하는 함수입니다.
  • 예를 들어, 아래와 같이 다양한 길이의 문자열을 고정된 크기의 해시 값으로 매핑할 수 있습니다:
    • ABC      ->   A1
    • 12321F -> B1
    • FSR4    -> C3
  • 이처럼 입력값을 특정한 값으로 변환하는 역할을 하는 함수를 해시 함수라 합니다.
  • 이러한 해시 함수의 결과를 사용해 해시 테이블을 인덱싱하고 데이터를 빠르게 저장하고 검색하는 기법을 해싱이라고 합니다.
  • 해싱은 특히 최적의 검색 성능이 요구되는 분야나 심볼 테이블 등에서 유용하게 활용됩니다.

 

해싱의 활용 분야

해시 함수는 정보 검색 이외에도 다양한 분야에 쓰입니다:

 

  • 체크섬(Checksum): 데이터의 무결성을 확인하는 데 사용
  • 손실 압축: 대용량 데이터를 일정 크기로 줄이는 압축
  • 무작위화 함수: 예측 불가능한 난수 생성
  • 암호화: 안전한 데이터 저장과 통신

 

이와 같은 여러 용도로 해시 함수가 사용되며, 때로는 혼용되기도 합니다.

 

 

성능 좋은 해시 함수의 특징

  • 충돌 최소화: 서로 다른 입력값이 같은 해시 값을 가질 확률이 낮아야 합니다.
  • 빠른 연산: 해시 함수 계산이 간단하고 빠른 연산으로 이루어져야 합니다.
  • 균일한 분포: 해시 테이블 전체에 걸쳐 해시 값이 고르게 분포되어야 합니다.
  • 모든 키 정보 활용: 해싱할 때 키의 모든 정보를 효과적으로 사용해야 합니다.
  • 효율적인 테이블 사용: 테이블의 공간을 잘 활용해 저장 효율을 높여야 합니다.

 

 

해시 충돌 예시 - 생일 문제

  • 해시 충돌이 얼마나 쉽게 일어날 수 있는지를 잘 보여주는 예로 생일 문제가 있습니다.
  • 사람들의 생일은 총 365가지로 한정되어 있지만, 여러 사람이 모이면 생일이 같은 사람들이 있을 확률이 높아집니다.
  • 예를 들어, 23명만 모여도 두 사람의 생일이 같을 확률은 50%가 넘고, 57명이 모이면 그 확률은 99% 이상이 됩니다.
  • 이는 파이썬을 통해 간단히 시뮬레이션할 수 있으며, 일상적인 예상과 달리 충돌이 매우 쉽게 발생할 수 있음을 보여줍니다.
import random

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

for _ in range(TRY):
    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 / TRY * 100}%')   # 50.73%

 

이처럼 해시 충돌은 예상보다 쉽게 발생하므로 충돌을 줄이는 것은 해시 함수 설계에서 가장 중요한 요소 중 하나입니다.

 

 

 

 

로드팩터

  • 로드팩터(Load Factor)는 해시 테이블에 저장된 데이터의 개수 n을 버킷의 개수 k로 나눈 값으로, 해시 테이블의 채워진 정도를 나타내는 지표입니다.
  • 로드 팩터 값에 따라 해시 함수를 재작성하거나 해시 테이블의 크기를 조정할지 결정하게 됩니다.
  • 또한 로드 팩터는 해시 함수가 키를 얼마나 잘 분산시키는지를 평가하는 효율성 측정에도 사용됩니다.
  • 일반적으로 로드 팩터가 높아질수록 해시 테이블의 성능은 점차 낮아지며, 예를 들어 자바 10에서는 로드 팩터가 0.75를 초과할 경우 동적 배열처럼 테이블 공간을 재할당해 성능 저하를 방지합니다.

 

 

해시 함수

  • 해시 테이블의 인덱싱을 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라 하며, 해싱에는 다양한 알고리즘이 존재합니다.
  • 특정 데이터에 따라 최적의 분포를 제공하는 해시 방법이 다를 수 있습니다.

그림1

 

 

나눗셈 방식 해시 (Division Hashing)

  • 가장 단순하면서도 널리 쓰이는 정수형 해싱 기법 중 하나는 나눗셈 방식(Division Method)입니다.
  • 이 방법은 모듈로 연산을 사용하며, 다음과 같은 수식으로 정의됩니다:

$ h(x) = x mod(m) $

$ h(x) $: 입력값 x의 해시 함수를 통해 생성된 값

$ m $: 해시 테이블의 크기, 일반적으로 2의 멱수에 가깝지 않은 소수를 택하는 것이 좋다.

  • 이 방법은 매우 단순하지만, 대부분의 키 세트가 충분히 랜덤한 상태이므로 실무에서도 효과적으로 사용됩니다.
 
 

 

 

 

728x90
반응형