[자료구조] 해시테이블

Gogozzi 2022. 5. 19. 02:26

해시테이블?

해시 테이블 또는 해시 맵은 키를 값에 맵핑할 수 있는 구조로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

해시 테이블의 가장 큰 특징은 시간 복잡도가 O(1) 이라는 점이다.

덕분에 데이터에 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다.

해시 함수?

해시함수는 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수이다.

입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환한다.

동일한 값이 입력되면 언제나 동일한 출력값을 보장한다.

ex) AFJQOPJF -> A1, FKQG -> B5 여기서 화살표가 해시 함수를 뜻함.

해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고한다. 해싱에는 다양한 알고리즘이 있으며, 데이터에 따라 최상의 분포가 제각각이다.

가장 단순하면서도 널리 쓰이는 정수형 해싱 기법인 모듈로 연산을 이용한 나눗셈 방식

h(x)=x mod m
x: 입력값
m: 해시 테이블의 크기(2의 멱수가 아닌 소수)
h(x): 이 값의 모듈로 연산의 결과

매우 단순한 방법이지만 이미 실무에서는 이미 많은 키 세트가 충분히 랜덤한 상태이고, 실제로 잘 동작한다.

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

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

아무리 좋은 해시 함수라도 충돌이 발생한다.

충돌은 생각보다 쉽게 발생한다. 흔한 문제로 생일문제를 들 수 있다. 생일의 가짓수는 365개 이므로,

여러 사람이 모였을 때 생일이 같은 2명이 존재할 확률을 얼핏 생각해보면 366명 이상이 모여야 일어나는 일 같다.

하지만 실제로 23명만 모여도 50%를 넘고 57명이 모이면 이때 부터는 99%를 넘어간다.

충돌을 대처하기전에 로드 팩터라는 개념먼저 설명하면,

로드 팩터?

해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것을 의미하는데(버킷이 얼마나 차있는지)

로드 팩터 배율에 따라서 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야 할지를 결정한다. 일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소한다.

load factor = n / k

자바 10에서는 해시맵의 디폴트 로드 팩터를 0.75로 정했으면 '시간과 공간 비용의 절충안' 이라고 얘기한다.

충돌 대처 방법 - 개별 체이닝

해시 테이블의 기본 방식인 개별 체이닝은 충돌 발생시 아래 그림과 같이 연결 리스트로 연결하는 방식이다.

흔히 해시 테이블이라고 하면 개별 체이닝방식을 말한다.

간단히 원리를 요약하면

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

잘 구현 했다면 대부분의 탐색은 O(1) 이지만, 모든 해시 테이블이 충돌이 발생했다고 가정했을 때는 O(n)이 된다.

충돌 대처 방법 - 오픈 어드레싱

충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식이다. 사실상 무한정 연결 할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.

여러 오픈 어드레싱 방식 중에서 가장 간단한 방식인 선형 탐사 방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다.

선형 탐사의 한 가지 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다는 점이다. 이러한 현상은 탐사 시간을 오래 걸리게 하며, 전체적으로 해싱 효율을 떨어뜨리는 원인이 된다.

오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없다.

따라서 일정 이상 채워지면, 즉 기준이 되는 로드 팩터 비율을 넘어서게 되면, 로드 팩터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어난다.

파이썬은 오픈어드레싱 방식을 사용하는데 이유는 체이닝 시 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 채택!

해시 테이블 vs 해시 맵

Java에서 HashTable과 HashMap의 차이는 동기화 지원 여부이다. 키(Key)에 대한 해시(Hash)값을 사용하여 값을 저장, 조회 하는 것은 동일하다.

해시 테이블(Hash Table)
- 병렬 처리를 할 때 (동기화를 고려해야하는 상황)
- Null 값을 허용하지 않는다.
해시 맵(Hash Map)
- 병렬 처리를 하지 않을 때 (동기화를 고려하지 않는 상황)
- Null 값을 허용한다.