해시 알고리즘

컴공생의 코딩 일기·2024년 10월 10일

회사 공부

목록 보기

3/7

해시 알고리즘

데이터를 빠르게 저장하고 검색하기 위한 알고리즘으로 키(key)를 사용하여 데이터(value)을 조회하는 방법을 의미한다. 이러한 키-값을 해시 테이블이라는 데이터 구조에 저장하여 키에 매핑되는 인덱스 값으로 빠르게 찾을 수 있다.

해시 함수(Hash Function) & 해싱(Hashing)

해시함수(Hash Function): Key값을 고정된 길이의 Hash로 변환하는 역할
- 해시 값(hash value) 또는 해시 코드(hash code)로 변환
해싱(Hashing): 해시 함수에서 Key값을 Hash로 변환하는 과정

해시테이블(Hash Table)

해시 테이블은 데이터를 저장하고 검색할 수 있도록 설계된 자료 구조이다. 해시 테이블은 키(Key)와 값(Value) 쌍을 저장하며, 키를 이용해 데이터를 빠르게 검색할 수 있도록 해시 함수를 사용하여 인덱스 위치를 계산한다. 이로 인해 해시 테이블은 평균적으로 O(1) 시간 복잡도를 가지고, 삽입, 삭제, 검색이 매우 빠르다.

해시 테이블 구성 요소

키(Key):
- 저장하려는 데이터의 고유한 식별자
값(Value):
- 키와 연관된 데이터
해시 함수(Hash Function)
- 키를 해시 테이블의 특정 위치에 매핑하는 역할을 하는 함수
해시 버킷(Hash Bucket)
- 해시 테이블의 각 인덱스가 가리키는 저장소로, 특정 해시 값에 해당하는 데이터를 저장하는 공간, 하나의 인덱스에 여러 데이터가 저장될 수 있는 구조도 있어야 한다.

해시 충돌(Hash Collision)

서로 다른 키가 동일한 해시 값을 가질 때 발행하는 현상이다. 해시 테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.

분리 연결법(Separate Chaining)

분리 연결법이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결해서 관리해주고 있다. 실제로 Java8이 Hash 테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현한다.
이러한 Chaining 방식은 해시 테이블의 확장이 필요 없고 간단하게 구현이 간능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 Chaining 되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

개방 주소법(Open Addressing)

개방 주소법은 해시 테이블에서 해시 충돌이 발생했을 때, 데이터를 저장할 빈 슬롯(주소)을 찾아가는 방법이다. 개방 주소법은 해시 테이블 내부에서 다른 빈 슬롯을 찾아 데이터를 저장하거나 검색을 수행한다. 개방 주소법은 해시 테이블의 각 슬롯이 연결 리스트와 같은 다른 구조를 사용하지 않고, 오직 테이블 자체의 공간을 이용한다.

개방 주소법에서는 해시 테이블의 각 슬롯이 하나의 키-값 쌍만을 저장하며, 충돌이 발생하면 해시 함수로 계산된 인덱스가 아닌 다른 슬롯을 찾는다. 빈 슬롯을 탐색할 때 사용하는 규칙을 프로빙(탐사, Probing)이라 하며, 이러한 탐색 규칙에 따라 개방 주소법의 종류가 구분된다.

개방 주소법의 탐사 방식 (Probing Methods)

선형 탐색(Linear Probing):
- 충돌이 발생하면 고정된 간격(일반적으로 +1)으로 다음 슬롯을 순차적으로 확인하며, 빈 슬롯이 나올때 까지 탐색한다.
- 예를 들어, 해시 인덱스가 5이고, 5번 슬롯에 데이터가 이미 있다면 6, 7, 8, ...순으로 빈 슬롯을 찾는다.
- 장점: 구현이 간단하고, 메모리 로컬리티(Locality)가 좋아 성능이 좋다.
- 단점: 클러스터링 현상(Clustering)이 발생할 수 있다. 해시 테이블의 특정 구간에 데이터가 집중되면서 빈 슬롯을 찾는데 시간이 오래 걸릴 수 있다.
제곱 탐색(Quadratic Probing)
- 선형 탐색의 클러스터링 문제를 해결하기 위해, 충돌이 발생할 때 탐사 간격을 제곱 형태로 증가시키는 방법이다.
- 예를 들어, 1, 4, 9, 16, ... 순으로 인덱스 간격이 증가하며 빈 슬롯을 탐색한다.
- 장점: 선형 탐사보다 클러스터링 문제가 줄어든다.
- 단점: 이차 클러스터링(Secondary Clustering)이 발생할 수 있다.
이중 해싱(Double Hashing)
- 두 개의 해시 함수를 사용하여 충돌이 발생할 때마다 다른 해시 값을 기반으로 탐색한다. 즉 첫 번째 해시 값이 충돌이 나면, 두 번째 해시 값으로 다음 인덱스를 계산하여 탐색을 진행한다.
- 장점: 이중 해싱은 충돌 시 탐색 패턴이 다양해져 클러스터링 문제를 최소화한다.
- 단점: 해시 함수 2개를 사용해야 하므로 계산 비용이 다소 증가할 수 있다. 또한, 두 번째 해시 함수가 테이블 크기와 상관 관계가 없도록 선택해야 한다.

Java에서 해시 테이블(Hash Table)과 해시 맵(Hash Map) 차이점

동기화
- 해시 테이블은 동기화 되어 Thread-safe한다. 즉, 멀티스레드 환경에서 한 번에 하나의 스레드만 해시 테이블에 변경을 가할 수 있다.
- 반면에, 해시 맵은 비동기화되어 있어 Thread-safe 하지 않는다. 이로 인해 해시 맵이 해시 테이블보다 빠르며, 동시성을 요구하지 않은 경우에는 해시 맵이 더 적합하다.
NULL 허용 여부
- Null Key 및 Null Value: 해시 맵은 하나의 Null Key와 여러 개의 Null Value를 허용한다. 반면, 해시 테이블은 Null Key 또는 Null Value를 허용하지 않는다.