본문으로 건너뛰기

1. 해시 테이블(Hash Table)​

  • 해시 테이블은 키와 값을 쌍으로 저장할 수 있는 자료구조입니다.
  • 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점입니다.
  • 덕분에 데이터의 양에 관계 없이 빠른 성능을 기대할 수 있습니다.

1.1 해시 함수(Hash Function)​

  • 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말합니다.
  • 해시 테이블의 핵심은 해시 함수입니다.
  • 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라고 합니다.

좋은 해시 함수의 특징

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

1.1.1 완전한 해시 함수​

  • 완전한 해시 함수는 서로 다른 두 개의 키를 해시 함수를 통해 해시 값으로 변경할 때 항상 다른 값을 반환하는 함수를 말합니다.
  • 동일하지 않은 어떤 객체 X와 Y가 있을 때, 즉 X.equals(Y)가 '거짓'일 때 X.hashCode() != Y.hashCode()가 같지 않다면, 이때 사용하는 해시 함수는 완전한 해시 함수( perfect hash functions)라고 합니다.
  • Boolean 같이 서로 구별되는 객체의 종류가 적거나 Integer, Long 같은 객체는 객체가 나타내는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있습니다.
  • 하지만 POJO에 대해서는 완전한 해시 함수를 제작하는 것은 사실상 불가능합니다.
  • 자바의 HashMap은 기본적으로 각 객체의 hashCode() 메서드를 사용합니다.
    • 결과 자료형이 int이기 때문에 32비트 정수 범위 내에서 해시 값이 반환됩니다.
  • 32비트 정수 자료형으로는 완전한 해시 함수를 만들 수 없습니다.
    • 논리적으로 생성 가능한 객체의 수가 2^32보다 많기 때문입니다.
    • 모든 객체에서 O(1)을 보장하기 위해 랜덤 접근이 가능하게 하려면 2^32인 4,294,967,296개의 버킷이 필요합니다.
    • 따라서 HashMap을 비롯한 많은 해시 테이블 구현체는 메모리 절약을 위해 해시 함수의 표현 정수 범위보다 작은 M개의 버킷을 사용합니다.
  • 즉 완전한 해시 함수를 사용하는 것이 사실상 불가능하고, 충돌이 발생할 수밖에 없습니다.

1.2 충돌(Collision)​

  • 여러 개의 키를 해시 함수를 통해 해시 값으로 변경할 때 해시 값이 중복될 수 있는데 이를 충돌이라고 합니다.
  • 서로 다른 두 개의 해시 값이 같은 인덱스를 가리키는 경우도 충돌이라고 합니다.
  • 비둘기집 원리에 따라 키의 수가 해시 테이블의 크기보다 크다면 반드시 충돌이 일어나게 됩니다.
비둘기집 원리

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

2. 해시 테이블의 구현​

  • 충돌 발생을 어떻게 처리하는지에 따라 개별 체이닝, 오픈 어드레싱 방식으로 구분됩니다.

2.1 개별 체이닝(Separate Chaining)​

  • 해시 테이블의 기본 방식으로 충돌 발생 시 연결 리스트로 연결하는 방식을 사용합니다.
  • 대부분의 탐색은 O(1)이지만 최악의 경우 O(n)이 될 수 있습니다.
  • 최악의 경우: 모든 경우의 해시 값이 중복되어 충돌이 발생한 경우입니다.
  • 자바 8에서는 데이터의 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용하기도 했습니다.

2.1.1 동작 방식​

  1. 키의 해시 값을 계산합니다
  2. 해시 값을 이용해 배열의 인덱스를 구합니다
  3. 같은 인덱스가 있다면 연결 리스트로 연결합니다

2.1.2 장단점​

  • 장점: 무한 확장성, 삭제 연산의 용이성, 높은 적재율 허용, 구현 용이성, 좋은 해시 분포 등
  • 단점: 추가 메모리 오버헤드, 캐시 지역성 부족, 최악의 경우 성능 저하, 외부 포인터 관리 등

2.2 오픈 어드레싱(Open Addressing)​

  • 충돌 발생 시 탐사를 통해 빈공간을 찾아 빈 공간에 키 밸류를 저장하는 방식입니다.
  • 값을 무한정 저장할 수 있는 체이닝 방식과 달리 오픈 어드레싱 방식은 전체 해시 테이블의 크기 이상의 데이터를 저장할 수 없습니다.
  • 해시 테이블의 크기가 n이면 n개의 데이터만 저장 가능합니다.
  • 따라서 버킷 사이즈보다 데이터의 수가 큰 경우 더 큰 크기의 다른 버킷을 생성한 후 복사하는 리해싱 작업이 필요합니다.

2.2.1 선형 탐사(Linear Probing)​

  • 오픈 어드레싱 방식 중 가장 간단한 방식입니다.
  • 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 진행하고 비어있는 공간에 데이터를 삽입합니다.
  • 구현이 간단하고 의외로 전체적인 성능이 좋은 편입니다.
  • 그러나 데이터들이 고르게 분포되지 않고 뭉치는 현상인 클러스터링이 발생할 수 있습니다.
  • 이로 인해 탐사 시간이 증가하고 전체적인 효율이 떨어집니다.

2.2.2 장단점​

  • 장점: 메모리 효율성, 캐시 지역성, 적은 메모리 단편화, 예측 가능한 메모리 사용, 구현 단순성 등
  • 단점: 크기 제한, 클러스터링, 삭제 연산의 복잡성, 적재율 민감성, 리해싱 비용 등

2.3 비교​

  • 둘 모두 최악의 경우(Worst Case) O(M)입니다.
  • 오픈 어드레싱(Open Addressing)
    • 오픈 어드레싱은 연속된 공간에 데이터를 저장하기 때문에 개별 체이닝에 비하여 캐시 효율이 높습니다.
    • 따라서 데이터 개수가 충분히 적다면 오픈 어드레싱이 개별 체이닝보다 더 성능이 좋습니다.
    • 하지만 배열의 크기가 커질수록(M 값이 커질수록) 캐시 효율이라는 오픈 어드레싱의 장점은 사라집니다.
    • 배열의 크기가 커지면, L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문입니다.
  • Java HashMap에서 사용하는 방식은 개별 체이닝(Separate Chaining)입니다.
    • 오픈 어드레싱은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문입니다.
    • 게다가 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 오픈 어드레싱은 개별 체이닝보다 느립니다.
    • 오픈 어드레싱의 경우 해시 버킷을 채운 밀도가 높아질수록 최악의 경우(Worst Case) 발생 빈도가 더 높아지기 때문입니다.
    • 반면 개별 체이닝 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 최악의 경우(Worst Case) 또는 최악의 경우에 가까운 일이 발생하는 것을 줄일 수 있습니다.

참고

  • 파이썬 알고리즘 인터뷰(박상길 저)