Hash

해시

정의

• 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 구하는 것
• 내부적으로 배열을 사용해 표를 저장함
• 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 것
• 원소의 검색, 추가/삭제도 효율적으로 수행할 수 있음

개념

원소의 개수가 13개인 배열이 있다고 하자
|인덱스|0|1|2|3|4|5|6|7|8|9|10|11|12|
|---|-|-|-|-|-|-|-|-|-|-|-|-|-|
|키|5|6|14|20|29|34|37|51|69|75|-|-|-|

이 배열에 원소 35를 정렬에 맞게 추가한다고 하자

키	5	6	14	20	29	34	37	51	69	75
해시값(13으로 나눈 나머지)	5	6	1	7	3	8	11	12	4	10

• 해시값 (hash value) : 데이터에 접근할 때 기준이 되는 값
• 해시테이블 (hash table) : 구한 해시값을 인덱스로 하여 원소를 새로 저장한 배열
  • 버킷(bucket) : 해시테이블에서 만들어진 원소
• 해시함수 (hash function) : 키를 해시값으로 변환하는 과정, 일반적으로 나머지를 구하는 연산 or 연산을 응용할 때 주로 사용함

  인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12
  키	-	14	-	29	69	5	6	20	34	-	75	37	51
  - 원소 35를 추가한다면 : 35 % 9 == 9 이므로...
  인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12
  ---	-	-	-	-	-	-	-	-	-	-	-	-	-
  키	-	14	-	29	69	5	6	20	34	35	75	37	51

• 해시 충돌 (hash collision) : 저장할 버킷이 중복되는 현상
  • 키:해시값 = 1:1일 필요는 없다. 일반적으로 다대1(n:1)임
  • 원소 18을 추가한다면 : 18 % 13 == 5 이므로...
    • 이미 5라는 값이 있다.
  • 충돌을 대처하는 방법:
    1. 체인법
    2. 오픈주소법

해시 충돌을 피하는 방법

1. Seperate Chaining, 체인법 (Chaining)

• 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법

• index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 LinkedList에 노드를 추가한다.

• 장점 :

  1. 한정된 Bucket을 효율적으로 사용할 수 있다.
  2. 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.

• 단점 :

  1. 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.
  2. 외부 저장 공간을 사용한다.

• 시간복잡도 :

  • 검색: 선형검색을 하기 때문에 최악의 경우 O(n)
  • 삽입: 충돌이 없으면 O(1), 최악의 경우 한 해시에 모든 연결리스트가 있어서 O(n)
  • 삭제: 검색과 비슷한 개념으로 삭제할 노드를 찾아야 하므로 최악의 경우 O(n)

2. 오픈 주소법 (Open Addressing)

• 해시 충돌이 발생하면 해시 함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장하는 방식이다. (해당 키 값에 데이터가 저장되어 있다면 다음 주소에 저장.)

• 종류

  • 선형 탐사(Linear Probing): 현재 주소에서 고정된 크기만큼 다음 주소로 이동하여 데이터를 저장한다.
  • 제곱 탐사(Quadratic Probing): 이동 크기가 제곱수로 늘어나는 방식이다. (1,4,9,16...)
  • 이중 해싱(Double Hashing): 해시 충돌 시 다른 해시 함수를 한번 더 적용하는 방식이다.
  • 재해싱(Rehashing): 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 모든 데이터를 다시 해싱하는 방식이다.

• 시간복잡도 (십입, 삭제, 검색 모두 동일)

  • Best: O(1) - 바로 찾는 경우
  • Worst: O(n) - 한 key에 모든 linked list가 연결되어 있어서 그 linked list를 모두 순회하는 경우
  • 삽입, 삭제, 검색 모두 대상이 되는 Hash를 찾아가는 과정에 따라 시간복잡도가 계산이 된다. 해시함수를 통해 얻은 Hash가 비어있지 않으면 다음 버킷을 찾아가야 한다. 이 찾아가는 횟수가 많아지면 많아질 수록 시간복잡도가 증가한다.
  • 따라서 비어있는 공간을 확보하는 것(= 저장소가 어느 정도 채워졌을 때 저장소의 사이즈를 늘려주는 것)이 필요하다.