[자료구조] 해시테이블이란?

해시테이블이란?

• 해시(hash) 테이블은 Key, Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다.
• 아래 그림은 해시구조를 나타내는 그림입니다.
• John Smith라는 Key는 해시함수를 통해 02라는 값으로 변환되고 02라는 인덱스의 값에 521-1234라는 데이터를 저장하고 있습니다.
  
• 해시 테이블(hash table): Key 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  고유한 키(Key)값을 이용하여 해당 데이터에 접근가능하다는 뜻입니다.
• 키(Key): hash 함수의 input이 되는 고유한 값
  키(Key)는 해시함수(hash function)를 통해 해시(hash)로 변경되어 value 값과 매칭되어 저장소에 저장됩니다.
• 해시 함수(hashing function): Key 값에 대한 연산을 통해 고정길이의 값으로 변환시키는 함수
• 해시 (hash): 임의의 값을 고정 길이로 변환한 값
  키(Key) 값 그대로 저장소에 저장되게 되면 다양한 길이의 저장소를 구성해야 하기 때문에 효율성을 위해 일관적으로 해시(hash)로 변경하여 저장함으로써 공간 효율성을 최적화합니다.
• 버킷(Bucket), 슬롯(Slot): hash table에서 하나의 데이터가 저장되는 공간

해시 테이블의 기능

1. 데이터 삽입(저장)

• key값을 hash function을 이용하여 고정된 길이의 값으로 변경후 해당 데이터를 저장합니다.

2. 데이터 삭제

• Key와 매칭되는 value 값을 찾아서 삭제합니다.

3. 데이터 검색

• Key를 이용해 value를 찾아내는 과정입니다. 먼저 key값과 hash function을 이용해 hash를 찾아내고 해당 hash로 value값을 찾을 수 있습니다.

시간 복잡도

• 삽입, 삭제, 검색에 대한 시간복잡도는 기본적으로 O(1)입니다.
• 단, Key값이 해시함수를 통해 고정된 길이로 변환됬을 때 기존 다른 Key를 고정된 길이로 변환된 값과 일치하는 해시 충돌이 일어날 수 있습니다. 이때를 제외했을 때의 시간복잡도가 O(1) 입니다.
• 예를들면 shbae라는 Key값과 smith라는 Key값을 해시함수를 통하여 해시된 고정값을 output하는 과정에서 두 Key값이 모두 01이라는 해시값으로 나온다면 해시 충돌이 일어났다고 합니다(다양한 길이를 고정된 길이로 변경하다보면 중복되는 값이 생길 수 밖에 없습니다.)

해시(hash)값이 충돌하는 경우 해결법

1. 분리 연결법(Separate Chaining)

• 동일한 버킷의 데이터에 대해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것입니다.
  ex) 위 그림에서 John Smith, Sandra Dee라는 Key값의 해시값이 일치하여 해시 충돌이 일어났습니다.
  해당 bucket에서는 먼저 들어온 John Smith키의 데이터가 먼저 들어가고 그다음 연결리스트를 통해 Sandra Dee 키값의 데이터가 bucket에 저장되었습니다.
• Chaining을 통해 hash table을 생성하였을 때 기능들의 시간복잡도는 O(n)까지 늘어 날 수 있습니다(linked list의 요소들을 처음부터 하나씩 찾아야 하므로)
• Java의 HashMap은 분리 연결법을 이용하고 있습니다.

2. 개방 주소법(Open Addressing)

• 비어있는 hash를 찾아 데이터를 저장하는 기법입니다.
• 1개의 hash에 1개의 value만이 매칭되게 됩니다.
• linear probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장합니다.
• Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식입니다. 예를 들어 처음 충돌이 발생한 경우 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식입니다.
• Double Hahsing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식입니다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 됩니다.

위 그림에 대한 설명은 아래와 같습니다.

Linear Probing

고정폭이 1이며 해시값 52에 대한 bucket이 172로 들어가 있으며 각 해시값인 53,54,55번에는 이미 값이 할당되어 있을 때 해시값 52로 새로운 데이터가 접근하는 경우 52에 값이 있음 -> 53에 값이 있음 -> 54에 값이 있음 ... 을 통해 56번에 값이 없다는 것을 알고 해시값이 56인 bucket에 472라는 데이터가 입력됩니다.

Quadratic Probing

해시값 7에 대한 bucket이 656으로 들어있으며 7~11 해시값에 대해서도 bucket이 저장되어 있을 때 해시값 7로 새로운 bucket이 저장되어야 할 때 해시값 7비교 값이 있음 -> 1^2(해시 값8 = 7 + 1)의 값만 큼 이동 한 해시 bucket이 저장되어 있는지 확인 -> 2^2(해시 값 11 = 7 + 4)의 값만 큼 이동 한 해시 bucket이 저장되어 있는지 확인 -> 3^2(해시 값 16 = 7 + 9)의 값만 큼 이동 한 해시 bucket이 저장되어 있는지 확인을 통해 비어있는 해시 16에 420이라는 데이터가 저장되고 있습니다.