[자료구조] 해시 Hash

해시함수란?

데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 

이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다.

 

 

해시함수는 해쉬값의 개수보다 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에

서로 다른 두 개의 키에 대한 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다.

 

 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 모두 ‘02’로 매핑해 해시충돌을 일으키고 있다. 

 

해시테이블 Hash table

 

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 데이터의 값(value)을 키와 함께 저장하는 자료구조이다.

 

버킷(bucket) or 슬롯(slot): 데이터가 저장되는 곳

 

해시테이블의 기본 연산은 삽입, 삭제, 탐색이다.

 

 

예를 들어, 각 버킷에는 데이터가 이러한 형식으로 저장된다.

 

인덱스 (Hash Value)	데이터
01	(Lisa Smith, 521-8976)
02	(John Smith, 521-1234)
...	...

 

키 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 한다.

 

Direct-address table

키 개수와 해시테이블 크기가 동일하기 때문에 해시충돌 문제가 발생하지 않는다.

하지만 전체 키(unverse of key) 가 실제 사용하는 키(actucal key) 보다 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 만들어야 하므로 메모리 효율성이 떨어진다.

 

그러므로 보통 해시테이블 크기가 실제 사용하는 키의 개수보다 적은 해시 테이블을 운용한다.

다뤄야할 데이터가 정말 많고, 메모리 등 리소스 문제도 생기기 때문이다.

 

Direct-address table의 load factor는 1 이하이며, 1보다 큰 경우 해시충돌 문제가 발생한다.

 

Load Factor

해시테이블의 크기 = m, 키 개수 = n
n / m = load factor

해시테이블의 한 버킷에 평균 몇 개의 키가 매핑되는지 나타내는 지표

 

해시테이블의 장점

• 적은 리소스로 많은 데이터를 효율적으로 관리
  • 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있다. 
• 인덱스에 해시값을 사용하여 검색/삽입/삭제를 빠르게 수행
  • 인덱스는 계산이 간단한 상수시간으로 작동하기 때문에 매우 효율적이다.
  •  데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 O(1)을 지향한다.
• 보안에 자주 사용된다.
  • 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵다.
  • 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행한다.

 

 

이후로 해시충돌을 해결하기 위한 다양한 기법들이 고안되었다.

 

Chaining

해시테이블의 크기를 유연하게 만든다.

한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 개념이다.

 

 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현(연결리스트)한다.

 

 

해시함수는 ‘John Smith’와 ‘Sandra Dee’를 같은 해시값(152)으로 매핑하고 있다. 

이러한 경우 동일한 버킷에 2개의 데이터를 저장하는 것이다.

 

체인은 유연하지만 메모리 문제가 있다.

 

Chaining에서 삽입을 제외한, 탐색/삭제의 계산복잡성은 버킷당 요소 개수의 평균 α가 기준인 구조이다.
최악의 경우 한 버킷에 모든 데이터가 들어있어 O(n)이 될 수 있다.
하지만 데이터의 개수가 해시테이블 크기의 두 세배쯤(α가 2~3)만 되어도 탐색, 삭제는 O(1)이 된다.

 

 

 

Open addressing

한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이다.

해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용한다는 개념이다.

 

예를 들어, 키에 해당하는 데이터를 저장하려고 할 때 해당 버킷에 이미 데이터가 있는 경우 다른 비어있는 버킷을 찾아 할당하는 것이다. 

즉, 버킷에 데이터가 있다면 다음, 다음다음, 다음다음다음.. 버킷에 저장하는 형식이다.

 

open addressing은 구조상 해시충돌 문제가 발생할 수 있다. 

위 예시처럼 특정 해시값에 키가 몰리게 되면 효율성이 크게 떨어진다. 메모리 문제가 발생하지 않으나 해시충돌이 생길 수 있다.

그리하여 해시충돌은 탐사(probing) 방식으로 해결한다.

 

탐사(probing)

삽입, 삭제, 탐색을 수행하기 위해 해시테이블 내 새로운 주소(해시값)를 찾는 과정

 

선형 탐사(Linear probing)

최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(ex.1칸)을 옮겨 다음 해시값의 버킷에 액세스(삽입, 삭제, 탐색) 한다.

 

이러한 개념으로 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustring 문제에 취약하다.

 

제곱 탐사(Quadratic probing)

고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어난다.

데이터에 액세스할 때 충돌이 일어나면 1^2 칸을 옮기고, 충돌이 또 일어난다면 이번엔 2^2칸, 3^2칸 옮기는 것이다.

 

하지만 서로 다른 키들이 동일한 초기 해시값(아래에서 initial probe)을 갖는 secondary clustering에 취약하다.

초기 해시값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어지기 때문이다. 

 

이중해싱(double hashing)

탐사할 해시값의 규칙성을 없애버려서 clustering을 방지한다.

일단 이중해싱은 2개의 해시함수를 준비한다.

하나는 최초의 해시값을 얻을 때 사용하고, 다른 하나는 해시충돌이 일어날 때 탐사 이동폭을 얻기 위해 사용한다.

 

이러한 방식은 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering의 문제점을 해결할 수 있다.