Hash Table

Hash Table 해시 테이블

해시 테이블은 키와 값을 함께 저장하는 자료구조 중 하나로, 데이터 검색이 빠른 자료구조이다.

 

해시 테이블은 키(Key), 해시 함수(Hash Function), 해시(Hash), 값(Value), 저장소(Bucket Slot)로 이루어져 있다.

 

키 Key

키는 고유한 값이며, 해시 함수의 input이 된다. 이때 input되는 키는 해시 함수를 통해 해싱된 값으로 바뀌어 저장된다. 

 

Javascript의 Object와 Map은 키의 자료형의 차이가 있다.

 

Object의 키는 오직 문자열과 심볼만으로 사용할 수 있지만, Map은 모든 데이터 타입을 키로 사용할 수 있다.

아래에서 설명하겠지만, 값이 저장되는 버킷을 가르키는 인덱스로 사용된다.

 

 

값 Value

값은 최종적으로 버킷에 저장되는 값이며, 키와 매칭되어 저장, 삭제, 검색, 접근이 가능하다.

 

 

해시 함수 Hash Function

해시 함수는 key를 고정된 길이의 해시로 변환해주는 역활을 하며, 다양한 길이를 갖는 key를 고정된 길이의 해시로 변환해 버킷의 접근을 보다 효율적으로 할 수 있게 도와준다.

 

이때 해시 함수를 통해 키 값을 해시로 변환해주는 작업을 해싱(Hashing)이라 한다.

해싱(Hashing)은 데이터 구조나 암호화, 데이터베이스 인덱싱 등에서 효율적인 데이터 관리를 위해 사용되는 기법이다.

데이터를 고정된 크기의 고유한 값으로 변환해 빠른 검색, 저장, 삭제, 접근 등의 연산을 수행할 수 있게 해준다. 

 

 

해시 Hash

해시는 해시 함수의 결과물로, 해시 테이블의 저장소(bucket)을 가리키는 인덱스(주소)로 사용된다.

 

즉, 해시 값이 value 값과 매칭되어 저장소에 저장된다. 이는 value 값 데이터의 고유한 식별자로 사용된다.

 

 

정리

해시 테이블은 키, 값(value), 해시 함수, 해시, 버킷으로 구성되며, 해시 함수를 통해 키를 해시로 변환한 값을 주소로 삼아 버킷에 저장된 값(value)과 함께 쌍을 이루는 자료구조이다.

 

해시 테이블의 시간 복잡도

연산	Big-O
저장	평균 O(1), 최악 O(N)
검색	평균 O(1), 최악 O(N)
삭제	평균 O(1), 최악 O(N)

 

해시 테이블은 저장, 검색, 삭제 동작에서 평균적으로 O(1)의 시간복잡도를 갖기에 빠르게 데이터를 다룰 수 있는 효율성이 좋은 자료구조이다.

 

하지만, 최악의 경우 O(N)의 시간복잡도를 갖을 수 있다. 이유는 해시 함수가 해싱 동작을 할때 서로 다른 두개의 입력에 같은 해시를 출력할 때 발생하는 해시 충돌 때문이다. 유한한 가짓수 중 같은 출력이 있을 수 있다는 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

위의 사진에서도 John Smith와 Sandra Dee가 같은 해시를 갖으며 해시 충돌이 발생한다. 이때 해당 해시의 버킷에 공간이 없다면 추가로 담기는 데이터는 오버플로우가 발생한다.

 

해시 충돌

해시 충돌을 해결할 수 있는 방법은 다음과 같다.

1. 체이닝(Chaining) → 연결 리스트만 사용, 개방 주소법에 비해 복잡한 계산식이 적음

각 버킷 내에 연결 리스트를 할당해 충돌이 발생하면 오버플로우되는 데이터를 연결 리스트로 저장하는 방법이다. 사진을 보면 John Smith가 이미 버킷에 저장되있으니 연결 리스트에 Sandra Dee가 저장되는 모습을 볼 수 있다.

2. 개발 주소법(Open Addressing) → 데이터가 적을 때 유리, 지정한 메모리외 추가적인 공간 불필요

체이닝의 경우 연결 리스트에 데이터가 저장된다 하지만, 데이터의 주소값은 바뀌지 않는다. 하지만 개발 주소법의 경우 해시 충돌이 발생하면 다른 버켓에 데이터를 삽입하는 방식으로 동작하기에 데이터의 주소값을 갖는다는 차이점이 있다.

개방 주소법은 대표적으로 3가지가 존재한다.
1. 선형 탐색: 해시 충돌시 다음 혹은 몇개의 버켓을 건너뛰어 데이터를 저장
2. 제곱 탐색: 해시 충돌시 제곱만큼 건너뛴 버켓에 데이터 저장
3. 이중 해시: 해시 충돌시 다른 해시 함수를 한 번더 적용한 결과를 이용

체이닝과 개발 주소법의 선형탐색의 비교