해시 테이블 및 해시 함수

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

1	해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.

• 성능 좋은 해시 함수들의 특징

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

---

여기서 고려해야할 문제중 하나인 충돌을 알아보자

먼저 비둘기집 원리라는게 있다.

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

비둘기집 원리처럼 해시함수는 임의크기 데이터(n개 데이터)를 고정 크기(m개 컨테이너)로 매핑하기 때문에 고정 크기가 아무리 크더라도 충돌할 수 있는 확률이 아예 0일 수는 없는 것이다.

그럼 충돌이 발생하면 어떻게 처리해야 할까?

충돌을 해결하는 방법엔 크게 2가지가 있다.

1 2	1. 개별 체이닝(Separate Chaning) 2. 오픈 어드레싱(Open Addressing)

---

개별 체이닝

1	개별 체이닝이란 충돌 발생 시 해당 충돌 인덱스를 연결 리스트로 연결하는 방식이다.

원리를 순서로 나타내면 아래와 같다.

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

---

오픈 어드레싱

1	오픈 어드레싱이란 충돌 발생 시 탐사를 통해 빈 공간을 찾아내는 방식이다.

오픈 어드레싱 방식 중 가장 간단한 방식인 선형 탐사 방식을 순서로 나타내면 아래와 같다.

1. 키의 해시 값을 계산한다.
2. 해시 값을 이용해 배열의 인덱스를 구한다.
3. 같은 인덱스가 있다면(충돌) 해당 위치부터 다음위치로 이동하면서 순차적으로 탐사를 진행한다.
4. 가장 가까운 비어있는 위치를 탐사해 새 키를 삽입한다.

선형 탐사는 비교적 개별 체이닝 방식보다 성능이 좋은편이나 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향의 문제점이 있다.

그리고 오픈 어드레싱 방식 자체는 연결리스트로 추가할 수 없기 때문에 지정된 슬롯의 개수 이상은 저장할 수 없는 문제점이 있다.

이러한 문제 때문에 로드 팩터 비율이 넘어서게 되면 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어난다.

1	로드팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷(컨테이너 개수)의 개수 k로 나눈 것이다

---

각 언어별 해시 테이블 적용 방식

언어	방식
C++	개별 체이닝
자바	개별 체이닝
Go	개별 체이닝
루비	오픈 어드레싱
파이썬	오픈 어드레싱