Data Structure(3) Hash Table(해시 테이블)

Hash Table (해시 테이블)

---

해시 테이블은 { 키(key) : 값(value) } 쌍을 저장하고 있는 자료 구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키(key)를 '해시 함수'(Hash function)라는 함수를 통해 특정 숫자값의 인덱스(index)로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

 

해시테이블 : 키(key) → 해시 함수(Hash function) → 인덱스(index)로 변환해 저장하는 자료구조!

 

관련 용어

 

키(key) : 원래의 데이터 값(해시 함수 입력 전)
값(value) : 최종 저장되는 값
해싱(hashing) : key → index로 바꾸는 과정
해시함수(hash function) : key → index로 바꿔주는 함수
해시값(hash value) : key에 해시함수를 적용한 값 (index)

 

 

해시 함수 (Hash Function)

---

해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.

key의 인덱스는 어떻게 알 수 있을까? 해당 key를 index로 바꿔주는 것이 바로 해시함수(hash function) 이다. 해시함수는 얼마든지 다양하게 만들 수 있다. 해시함수로 어떤 계산을 해서 → 어떤 고유한 숫자값으로 index를 만드는데, 이렇게 나온 index를 해시값(hash value)라고 부르고, 이런 전반적인 과정을 해싱(hashing)이라고 부른다.

 

해싱(hashing) 과정

 

해시 함수의 세 가지 조건

 

1. 같은 키(key) → 해시함수 → 같은 해시값(index)
해시함수는 같은 키를 넣었을 때 같은 해시값을 반환하는 일관성을 가지고 있어야 한다.

2. 키(key)를 저장하지 않고 값에 따라 반환
키를 따로 저장해 두는 것이 아니라, 그때 그때 함수를 적용한 값을 반환한다. 따라서 미리 출력값을 예상할 수 없다. 

3. 배열크기를 알아야 함, 유효한 인덱스만 반환

보통 해시함수는 특정 숫자를 배열 크기로 나눈 나머지를 반환한다. 그래야 저장소 크기를 넘지 않는 유효한 index를 만들어 낼 수 있기 때문이다.

 

 

해시테이블 (Hash Table)

---

해시테이블은 실질적으로 데이터를 저장하는 공간이며, 인덱스가 가리키는 공간에 value를 저장한다.

 

hash table : 데이터 저장 공간
storage : 배열 형태의 가장 큰 저장소 (해시 테이블)
bucket(slot) : storage 내부 저장소 (index에 따라 데이터를 담고 있음)
tuple : key, value 쌍이 저장됨 (읽기전용, 덮어쓰기만 가능!)

스토리지

위의 그림을 코드로도 한번 표현해보자. bucket이나 tuple는 다른 방법으로도 표현할 수 있지만, 일단은 배열과 객체로 표현해보도록 하겠다. 여기서 [ ]은 bucket을, { }는 tuple을 의미한다. 그리고 tuple 안에는 key와 value가 쌍으로 들어간다.

 

let storage = [
  0: [{key1: value1}, {key2: value2}]
  1: [],
  2: [],
  3: [],
  4: [{key3: value3}],
  5: [],
  6: [],
  7: []
]

 

 

해시 테이블 메서드 (Method)

---

insert : 키, 값을 해시테이블에 삽입
retrieve : 키를 입력하면 해당하는 값을 반환
remove : 데이터 삭제
_resize : 배열의 사이즈를 키우거나 줄임 (필요시에만 늘리고, 가능한 작게 유지 (25~75%))

 

리사이징(resizing)

 

해시 충돌 (Collision)

---

문제 : 서로 다른 key가 동일한 해시값(index)을 가지는 현상

해결 방안 : 해당 테이블 안에서 배열이나 연결리스트같은 다른 자료구조 사용

 

1. 체이닝 (chaining)

체이닝은 충돌이 발생하는 경우 충돌된 값들을 해당 주소에 있는 연결리스트에 삽입해 문제를 해결하는 방법이다. 한 버킷당 들어갈 수 있는 개수에 제한을 두지 않기 때문에 모든 자료를 해시테이블에 담을 수 있다. 버킷에 이미 데이터가 존재해도, 체인처럼 노드들을 계속 추가하고 다음 노드를 가리키도록 하기 때문에 (= 연결리스트) 크기를 유연하게 조절할 수 있다. (참고로 이 방법이 아래 소개할 개방해싱보다 많이 사용된다고 한다)

 

체이닝(chaining) 방식

 

2. 개방 해싱 (open addressing)

개방 해싱은 해시테이블 밖의 새로운 공간에서 문제를 해결하는 방식이다. 해시함수로 얻은 주소가 아닌 다른 주소에도 데이터를 저장하는데, 버킷의 크기는 고정시키지만 저장할 위치를 좀 더 잘 찾는 데 중점을 둔 방법이라고 할 수 있다.

 

 

 

해시테이블의 Big O (시간복잡도)

---

보통의 경우 해시테이블은 배열(Array)이나 연결리스트(Linked List)보다 삽입, 삭제, 탐색이 빠르다. index로 접근이 가능해 데이터의 추가, 삭제, 탐색이 모두 O(1)밖에 걸리지 않기 때문이다. 하지만 해시 충돌이 일어나면, 그때부터 해시테이블의 시간 복잡도는 점점 늘어나게 된다. 최악의 경우를 생각해보자. 버킷(bucket)에 담긴 모든 튜플(tuple)들을 탐색해야 하기 때문에 최대 O(n)까지 걸리는 상황이 생길 수 있다. 리사이징을 할 때도 모든 데이터를 처음부터 끝까지 다시 배치하기 때문에 무려 O(n)이라는 시간이 걸리게 된다.