해시 테이블

TL;DR

자료구조 빈출 유형 !!!

• 해시 테이블은 키에 대한 해시 값을 사용해 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 Associate Array.
• 해시 테이블은 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있기 때문에 사용한다.
• 해시 함수에는 Division, Multiplication, Folding, Universal Hashing 등 다양한 방법이 있다.
• 충돌(Collision)을 처리하기 위해 링크드 리스트나 트리를 활용하는 Chaining 기법과 빈 공간에 저장하는 Open Addressing 방법을 사용한다.

해시 테이블

• 해시(hash) : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값
• 해시 함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 데이터가 조금만 달라져도 결과가 확연하게 달라져 무결성을 지키는데 도움을 주고,
• 기본적으로 복호화가 불가능해 보안성을 지키는데 도움을 준다.

 

1. 해시 테이블이란?

• 키(Key)와 값(Value)을 매핑해 둔 데이터 구조
• 키(Key)는 특별한 알고리즘을 이용해 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.
• 데이터의 양이 아무리 많아지더라도 이론적으로 해시 변환, 검색, 삭제에 걸리는 시간은 $O(1)$ 로 매우 빠르다.
• 해시 테이블의 기본 개념은 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이다.
• 따라서 특이하게도 데이터가 입력되지 않은 여유공간이 많아야 제 성능을 발휘할 수가 있다.

 

장점

• 데이터 삽입, 삭제, 조회가 $O(1)$로 빠르다.
• 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
• (하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능하다.)
• 키와 해시값의 연관성이 낮다면 보안 유지에 도움이 된다.

 

단점

• 순서를 보장하지 않아 순서/관계가 있는 목적에는 적합하지 않다. (데이터를 정렬된 순서로 접근할 때 비용이 높다.)
• 지역 참조성에 취약하다.
• 해시 함수 의존도가 높다.
• 해시 충돌 방생시 최악의 경우 시간복잡도가 $O(N)$이 된다.

 

프로그래밍 언어에서의 Hash Table

이미 수많은 프로그로그래밍 언어에 이미 내재되어 있다

2. 해시 함수

• 고유한 인덱스 값을 설정하는 특별한 알고리즘, Hash Function
• 좋은 해시 함수는 특정 값에 치우치지 않고 해시값을 고르게 만들어낸다.

 

1) Division Method 나눗셈

• 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 반환
• m은 대게 소수를 사용하고, 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 한다.

 

2) Multiplication Method 곱셈

• 숫자로 된 키가 $k$이고 $A$는 0과 1 사이의 실수일 때 실수의 곱셈법은 아래와 같이 정의된다.
• $m$이 얼마가 되든 크게 중요하지는 않고 보통 2의 제곱수로 정한다.
• 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 한다.

$h(k) = (kA \ mod \ 1)xm$

 

3) Digit Folding 자릿수 접기

• 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR 한 값을 해시값으로 삼기.
• ex) 583924를 각각 자릿수별로 더하면 31 -> 이제 두 자리씩 Folding -> 121

 

4) Universal hashing 전체 해싱

• 다수의 해시함수를 만들고 이 해시함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법
• H에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 1/m 로 만드려는 것이 목적
• 아래의 특정 해시함수 집합 H는 이를 가능하게 한다고 수학적으로 증명됐다.
  • 해시 테이블의 크기 m : 소수
  • 키값을 r+1 개로 쪼개기 : $k_0, k_1, …, k_r$
  • 0부터 m-1 사이의 정수 가운데 하나를 무작위로 뽑고, 분리된 키값의 개수(r+1)만큼 반복해서 뽑는다. 이를 $a = [a_0, a_1, …, a_r]$로 둔다.
  • 해시 함수 : $h_a(x) = \Sigma_{i=0}^r(a_i k_i mod m)$
  • a가 $m_{r+1}$가지이므로, 해시함수의 집합 H의 요소 수 또한 $m_{r+1}$개이다.

 

보안과 해시

• 키와 해시값 사이에 직접적인 연관이 없어 해시 값 만으로는 키값을 복원하기 어렵고,
• 해시 함수의 결과물은 고정된 길이의 숫자라 원래의 정보가 손실되어 원본데이터를 알기 어렵다.

5) MD5 (Message-Digest Algorithm)

• 임의의 길이의 값을 입력받아 128 비트의 고정 길이 해시값을 출력하는 알고리즘
• 같은 입력값이면 항상 같은 출력값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮다.
• 원래는 메시지 무결성을 검증하는 데 사용되었으나, 현재는 주로 데이터의 무결성 검사와 비밀번호 저장 등에 사용한다.
• MD5 알고리즘은 충돌 저항성이 낮기 때문에 보안 관련 용도로 쓰는 것을 권장하지 않는다.

 

6) SHA (Secure Hash Algorithm)

• 미국 국립표준기술연구소에서 표준으로 채택한 암호학적 해시 함수
• 해시 길이에 따라 SHA-256, 384, 512 비트를 선택해 사용할 수 있고, 해시 길이가 길수록 안전하다.
• MD5보다 안전하지만 느리다.

3. 충돌 처리 알고리즘

• 해시 테이블은 해시 함수에 의해 정해지는 Index가 중복될 수 있다는 문제가 존재한다.
• 위와 같은 상황을 충돌(Collision)이라고 한다.
• Collision이 많아질 수록 검색에 필요한 시간 복잡도가 $O(1)$에서 $O(N)$에 가까워진다.

👆 충돌 처리 알고리즘이 왜 필요할까?
해시 함수를 무조건 1:1 로 만드는 것은 Array와 다를 바 없고 메모리를 너무 많이 차지하게 된다. 따라서 Collision 을 최소화 하는 방향을 설계하고, 발생하는 Collision에 대비해 어떻게 대응할 것인가를 정하는 것이 더 중요하다.

 

1. Separate Chaining - 분리 연결법

• Linked List를 이용하는 방식
• 각 Index에 데이터를 저장하는 Linked List에 대한 포인터를 가지고, 충돌이 발생하면 그 Index가 가리키고 있는 Linked List에 노드를 추가한다.
• 데이터를 저장하는 구조는 Linked List만 사용하진 않는다.
  • Java8의 Hashmap의 경우 Index 노드가 6개 이하일 경우에는 Linked List를,
  • 8개 이상으로 늘어날 때는 Self-Balancing Binary Search Tree 구조로 데이터 저장 구조를 바꾼다.

👆 여기서 잠깐! WHY?

Tree는 Linked List보다 메모리 사용량이 많고 데이터 개수가 적을 때 Tree와 Linked List의 Worst case 수행 시간 차이 비교가 의미없기 때문이다. 그러나 데이터 개수가 많아지면 Tree가 더 높은 성능을 보이게 된다.
해시 함수 값이 균등분포일 때 Linked List에서는 get() 메소드의 기댓값은 E(N/M) 이고, Tree에서의 get() 메소드의 기댓값은 E(log N/M) 이므로 데이터의 개수가 일정 이상일 때에는 Linked List 대신 Tree를 사용하는 것이 성능상 이점이 있다.
(해시 테이블의 크기 m, 실제 사용하는 키 개수 n)

✌️ 왜 기준이 6개, 8개인가?

변경에 소요되는 비용을 줄이기 위해서다. 기준을 6개, 7개로 두게 된다면 하나의 값이 추가되면 자료구조를 변경해야 한다. 그리고 바로 하나의 값이 삭제되면 또 다시 자료구조를 변경해야 한다. 이런 Switching 비용 때문에 2개라는 여유를 두고 기준을 잡은 것이다.

🤟 왜 RB트리를 사용할까?

해시 테이블은 데이터 조회만 많이 일어나는게 아니기 때문에 rotation 같이 밸런스를 유지하기 위해 드는 오버헤드가 크다. RB 트리는 느슨하게 균형을 유지하면서 조회, 삽입, 삭제에 평균적으로 좋은 퍼포먼스를 보여주기 때문에 사용한다.

 

• 장점 : 테이블 확장을 늦출 수 있고, 간단하게 구현 가능.
• 단점 : 동일한 버킷에 chaining 되는 데이터가 많아져서 캐시 효율성 감소한다는 단점
  • 링크드 리스트 사용할 경우 최악의 경우 O(N)
  • 트리 활용의 경우 O(logN) 보장

2. Open Addressing - 개방 주소법

• 추가적인 메모리를 사용하지 않고 Hash Table의 빈 공간을 사용하는 방식
• 여러가지 구현 방식이 있다.
  • Linear Probing : 현재 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 저장 (선형 탐색으로 빈공간 찾기)
  • Quadratic Probing : 해시의 저장 순서 폭을 제곱으로 저장하는 방식
  • Double Hashing : 해시된 값을 한번 더 해싱 (다른 해시 함수 사용) 해서 랜덤한 인덱스에 저장하기

• 삭제할 경우 충돌에 의해 뒤에 저장된 데이터가 검색되지 않을 수 있다. 이를 방지하기 위해 삭제한 위치에 Dummy Node를 삽입한다.
• 장점 : 추가 메모리를 사용하지 않고 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 높다.
• 단점
  • 검색/삭제 시 Index의 키값이 찾고자 하는 키값이 아니라면 그 다음부터 선형 탐색을 실시해야 한다. (느리다!)
  • 해시 버킷을 채운 밀도가 높아질 수록 Worst Case 발생 빈도가 높아진다.

4. 해시 버킷 동적 확장(Resize)

• 해시 버킷의 개수가 적으면 Collision 으로 인해 성능 손실이 발생한다.
• Key-Value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다.
• 보통 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때다.
• load factor = 0.75
• Resizing은 더 큰 버킷을 가지는 array를 새로 만든 다음에, 다시 새로운 array에 hash를 다시 계산해서 복사해준다.

5. 파이썬 딕셔너리에서 사용하는 해시 함수는 무엇인가?

• 내장 hash() 함수를 사용하지만 직접 hash 매소드를 구현해 사용할 수도 있다.
• 파이썬은 충돌 방지 기법으로 오픈 어드레싱을 사용하고 Perturbation Shift Probing 이라는 고유의 알고리즘을 사용하고 있다. 매 probing 차례마다 PERTURB_SHIFT라는 값만큼 비트 이동을 하는 변수 pertrub를 기존 인덱스 계산식에 추가함으로써 조금 더 다이나믹하게 Probing을 진행할 수 있도록 한다.
• 로드 팩터는 0.66으로 설정되어 있고 4배씩 크기를 증가시키다가 일정 수준(50,000 이상)으로 커지면 2배씩 크기를 키운다.

 

 

References

• wiki.hash/해시
• Hash-Table
• JaeYeopHan/Interview…/Hash Table
• ratsgo/hash table
• Hash 함수
• CS-자료구조-해시-테이블
• leesukkyeong/해시테이블
• Neos960518/Python Dictionary 구조 CPython 소스 코드 레벨부터 파악하기