해시의 정의와 핵심 원리

해시는 가변 길이의 데이터를 고정된 길이의 데이터로 변환하는 기술을 의미한다.
이때 변환을 담당하는 수학적 알고리즘을 해시 함수(Hash Function) 이라 부르며, 출력된 결과물은 해시 값(Hash Value) 또는 해시 코드(Hash Code) 라고 정의한다.

자료구조적 관점에서 해시는 이러한 원리를 이용해서 데이터를 해시 테이블(Hash Table) 이라는 배열 형태의 저장소에 기록하고 관리하는 기법을 의미한다.

해싱의 핵심은 거대한 키 공간을 유한하고 관리 가능한 크기의 해시 테이블 인덱스로 매핑하는 것에 있다.

해시 값이 곧 테이블 인덱스는 아니다. 해시 값의 범위는 보통 해시 테이블 크기보다 훨씬 크기 때문에, 이 해시 값을 유한한 사이즈의 인덱스 범위로 압축하는 과정이 필요하다.
인덱스 변환은 주로 모듈러 연산(%)을 사용한다.
index = f(hashKey) % m

해시 함수의 특성과 해시 테이블

이상적인 해시 함수는 입력값이 조금이라도 다르면 전혀 다른 해시 값을 생성해야 한다. 반대로 동일한 입력에 대해서는 항상 동일한 해시 값을 출력해야 한다.

해시 테이블은 이러한 해시 함수를 이용해 데이터를 저장하는 자료구조로, 키(Key)를 해시 함수에 대입하여 얻은 인덱스 위치에 해시 값을 저장한다.
이 구조 덕분에 해시 테이블의 탐색, 삽입, 삭제의 평균적인 시간 복잡도는 O(1)을 가진다. (평균적이라고 한 이유는 뒤에 나올 해시 충돌과 연관이 있다.)

해시 충돌과 해결 전략

해시 함수가 매핑할 수 있는 인덱스 범위는 유한하다. 따라서 서로 다른 두 개의 Key가 동일한 해시 값을 갖게 되는 현상이 발생한다. 이를 해시 충돌(Hash Collision)이라고 한다.
이는 비둘기집 원리에 의해 불가피한 현상이며, 효율적인 해시 테이블을 설계하기 위해선 이 충돌을 해결하는 전략이 필수적이다.
해결하는 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있다.

체이닝(Chaining)

충돌이 발생한 인덱스에 데이터(해시 값)를 연결 리스트 형태로 추가하는 방식이다.
구현이 단순하며 제한된 범위의 테이블보다 더 많은 양의 데이터를 저장할 수 있다는 장점이 있다.
하지만 특정 인덱스로 데이터가 몰릴 경우 해당 리스트의 길이(N)만큼 탐색 시간이 늘어난다는 단점이 있다.

개방 주소법(Open Addressing)

충돌이 발생하면 비어있는 다른 공간을 찾아 데이터를 저장하는 방식이다.
비어있는 공간을 찾는 규칙에 따라서 선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 이중 해싱(Double Hashing) 등으로 나뉜다.

선형 조사(Linear Probing)

충돌 발생 지점으로부터 일정한 간격으로 다음 슬롯을 확인하는 방식이다. 탐색을 하다가 빈 공간이 있으면 그곳에 데이터를 저장한다.
선형 조사법에서 데이터를 조회할 때, 단순히 해시 함수를 한 번 돌려 나온 인덱스만 확인하고 끝내는 것이 아니라, 삽입할 때와 동일한 규칙으로 다음 칸들을 순차적으로 탐색하는 과정을 거친다.

검색의 종료 조건은 크게 세 가지가 있다. 첫 번째는 찾고자 하는 키를 발견했을 때(데이터가 있음을 의미) 두 번째는 테이블을 한 바퀴 다 돌아서 다시 처음 위치로 돌아왔을 때(데이터가 없음을 의미), 세 번째는 빈 버킷을 발견했을 때이다.
세 번째의 경우, 선형 조사법의 논리 상 만약 찾고자하는 Key가 해시 테이블에 존재한다면 빈 버킷이 존재할 수 없다. 따라서 빈 버킷을 발견했다는 것은 요소가 없음을 의미한다.

따라서 선형 조사법의 경우 조회의 시간 복잡도는 평균적으로 O(1)을 유지하지만, 최악의 경우 해시 테이블의 크기만큼 시간 복잡도가 증가한다.

여기서 만약, 특정 키가 선형 조사법으로 인해 인덱스 5번에 저장되었을 때, 인덱스 4번의 요소가 삭제된 상황에서 해당 키를 탐색하는 경우 빈 버킷을 만나게 된다.
결국 키 값이 존재함에도 불구하고 결과는 존재하지 않는 것으로 반환된다.
이 문제를 해결하기 위해 현대적인 해시 구현체들은 삭제된 자리에 삭제되었음을 마킹한다. 이를 흔히 Tombstone이라고 부른다.
검색 엔진은 이 마커를 만나면, '여기는 비어있지만 과거에 데이터가 있었으니 검색을 계속하라'는 신호로 받아들여 선형 조사를 이어나간다.

처리하는 방식은 단순하다는 장점이 있지만, 데이터들이 특정 인덱스 범위에 뭉치는 클러스터링 현상이 발생하기 쉽다.

이차 조사(Quadratic Probing)

선형 조사에서 발생하기 쉬운 클러스터링 문제를 해결하기 위해 고안되었다.
선형 조사법이 충돌 발생 시 고정된 간격(보통 1)으로 다음 버킷을 탐색하는 것과 달리, 이차 조사법은 탐사 횟수 i의 이차 함수를 이용하여 다음으로 조사할 인덱스를 결정한다.
i가 증가함에 따라 보폭의 크기가 제곱으로 커지기 때문에, 선형 조사법처럼 데이터가 특정 영역에 몰리는 클러스터링 현상을 방지할 수 있다.

하지만 이차 클러스터링이라는 새로운 문제가 발생한다.
만약 두 키가 완전히 동일하다면, 탐사 경로가 완전히 동일하기 때문에 버킷을 찾는 데 매우 비효율적인 연산이 수행된다.
또한 테이블의 크기에 따라 영원히 빈 버킷을 찾을 수 없는 문제가 있다.

이중 해싱(Double Hashing)

개방 주소법 중 가장 고도화된 전략으로, 탐색 간격을 결정할 때 별도의 두 번째 해시 함수를 사용하는 방식이다.
이중 해싱의 공식은 h(k, i) = (h1(k) + i * h2(k)) (mod m) 과 같다.
따라서 첫 번째 해싱 결과(h1(k))가 동일하더라도 두 번째 해시 함수인 h2(k)를 거친 결과를 이용해 다음 탐색의 간격을 결정한다.

이중 해싱이 올바르게 작동하기 위해서는 두 번째 해시 함수의 결과값(h2(k))이 해시 테이블 크기 m과 서로소 관계에 있어야 한다.
만약 서로소가 아니라면 탐사 과정에서 전체 버킷의 일부만을 순회하게 되어 빈 공간을 찾지 못할 수 있기 때문이다.
이를 위한 일반적인 설계 전략은 다음과 같다.

• 테이블 크기 m이 2의 거듭제곱인 경우, h2(k)가 항상 홀수를 반환하도록 설계한다.
• 테이블 크기 m이 소수인 경우, h2(k)가 1 초과, m 미만의 값을 반환하도록 설계한다.

결국 해시 테이블 내 데이터 분포를 최대한 불규칙하게 만들어, 충돌 시에 평균 탐색 시간을 O(1)에 가깝게 유지된다.
하지만 해시 함수를 두 번 호출해야 한다는 트레이드 오프가 존재한다.

해시의 활용 사례

해시는 자료구조뿐만 아니라 보안과 데이터 무결성 검증 분야에서도 사용된다.
암호학적 해시 함수인 SHA-256이나 SHA-3은 입력값의 역산을 불가능하게 만드는 단방향성을 가지며, 이를 통해 비밀번호와 같은 데이터를 안전하게 저장하는 데 사용된다.
또한 파일의 해시 값을 비교하여 전송 과정에서 데이터가 변조되지 않았는지 확인하는 체크섬 용도로도 널리 사용된다.

자바스크립트 엔진이나 JVM 내부의 HashMap 구현체는 성능 최적화를 위해 체이닝 방식을 기본으로 하되, 리스트의 길이가 일정 수준 이상 길어지면 레드-블랙 트리(Red-Black Tree)와 같은 자가 균형 이진 탐색 트리로 구조를 변경하여, 최악의 경우에도 탐색 성능을 O(logN)으로 보장하는 기법을 사용한다.