[Data-Structure] Hash Table(해시 테이블)

 

 

 

---

1. Hash Table(해시 테이블)

 

해시 테이블은 (Key, Value) 쌍으로 데이터를 저장하는 자료구조이며, 일반적으로 O(1)의 시간복잡도로 빠른 속도로 데이터를 저장하고 조회할 수 있다.

 

 

 

- 기본 구조

해시 테이블의 기본 구조는 아래와 같이 이루어져 있다.

 

Key가 되는 데이터를 해시 함수에 입력하면 인덱스가 생성이 되고, 해당 인덱스가 가리키는 버킷에 데이터를 저장하는 것이다.

 

 

 

인덱스 사용하기 때문에, 평균적으로 O(1)의 시간을 가지게 된다는 특징이 있다.

 

• 버킷(Bucket): 실제 데이터가 저장되는 공간
• 해시 함수(Hash Function): Key를 고정된 길이의 해시값으로 변환하는 함수
• 인덱스(Index): 해시값을 기반으로 계산된 버킷의 주소

 

[출처 : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94]

 

 

 

---

2. 해시 함수(Hash Function)

 

해시 테이블에 대하여 알아봤으니, 해시 테이블에 사용되는 해시 함수에 대하여 알아볼 것이다.

 

 

해시 함수는 아래 두 가지 성질을 동시에 만족하며, 임의의 비트열을 고정된 길이의 비트열로 변환하는 함수라고 정의한다.

 

조건 1) 하나의 출력에 대하여, 이 값으로 투입이 된 입력 값을 찾는 것이 불가능

조건 2) 하나의 입력에 대하여 같은 출력으로 나타낼 수 있는 또 다른 입력을 찾는 계산이 불가능

 

 

그렇기에 특정 입출력 값에 대한 계산이 불가능한 성질을 가지고 있기 때문에 보안에서도 중요한 요소로 사용된다.

 

 

 

- 해시 함수 종류

해시 함수는 알고리즘에 따라 고유한 인덱스를 생성하는데, 그로 인하여 아래와 같이 여러 종류의 해시 함수가 존재한다.

 

1. Division Method
2. Multiplication Method
3. Mid-Square Method
4. Folding Method
5. Cryptographic Hash Functions
6. Universal Hashing
7. Perfect Hashing

 

아래는 차례대로 각 해시 함수에 대한 설명이다.

 

 

1) Division Method

 

Division Method는 키를 소수로 나누고 그 나머지를 해시값으로 사용하는 방식

 

              h(k) = k % m             

 

- k : 키 값

- m : 소수 값

 

 

장점:

• 구현이 간단

단점:

• m을 잘못 선택하면 충돌이 잦음

 

 

2) Multiplication Method

Multiplication Method는 상수 A(0 < A < 1)를 키에 곱하고, 그 곱의 소수 부분을 m과 곱하여 해시값을 계산

 

 

              h(k) = ⌊m(kA % 1)⌋              

 

- k : 키 값

- m : 소수 값

- A : 상수 값(0과 1 사이의 실수)

 

여기서 ⌊ ⌋는 내림 함수를 의미한다.

 

장점:

• m 선택에 덜 민감

단점:

• 나눗셈법보다 복잡함

 

 

3) Mid-Square Method

Mid-Square Method는 키를 제곱하고, 그 결과의 중간 자릿수들을 해시값으로 사용

구현 방법 :

1. 키를 제곱
2. 결과 값의 중간 자릿수를 추출하여 사용

 

장점:

• 해시 값의 분포가 좋음

단점:

• 계산 비용이 클 수 있음

 

 

4) Folding Method

Folding Method는 키를 동일한 크기의 부분들로 나누고, 이 부분들을 합산한 후 m으로 나눈 나머지를 취하는 방식

 

 

구현 방법 :

1. 키를 여러 부분으로 분할
2. 부분들을 합산
3. 합계를 m으로 나눈 나머지를 사용

 

장점:

• 단순하고 구현이 쉬움

단점:

• 분할 방식에 따라 결과가 다름

 

 

5) Cryptographic Hash Functions

Cryptographic Hash Functions는 보안을 위해 설계되었으며, 암호학에서 사용된다.

 

MD5, SHA-1, SHA-256 등이 그 예시이며, 사용되는 암호화 과정에 따라 다른 알고리즘으로 구현되어 있다.

 

 

장점:

• 높은 보안성

단점:

• 계산 비용이 큼

 

 

6) Universal Hashing

Universal Hashing은 해시 함수들의 집합을 사용하여, 주어진 입력들에 대한 충돌 가능성을 최소화하는 함수이다.

 

        h(k) = ((ak+b) % p) % m       

 

 

- a, b  : 무작위 상수 값

- k : 키 값

- m : 소수 값

- p : m보다 큰 소수 값

 

장점:

• 충돌 가능성 감소

단점:

• 더 많은 계산과 저장 공간 필요

 

 

7) Perfect Hashing

Perfect Hashing은 정적인 키 집합에 대해 충돌이 없는 해시 함수를 만드는 것을 목표로 하여, 서로 다른 키들이 같은 값으로 해시되지 않도록 구현한다.

 

 

특정 알고리즘이 있는 것이 아닌, 해시 함수에 대입되는 키와 저장되는 범위 값을 일치시키거나 저장 공간을 더욱 크게 잡고 충돌이 없도록 구현한다는 방법을 의미한다.

 

 

Perfect Hashing에는 아래 두 가지 유형이 존재한다.

• Minimal Perfect Hashing : 해시 함수의 범위가 키의 개수와 정확히 일치
• Non-minimal Perfect Hashing : 범위가 키의 개수보다 클 수 있음

 

장점:

• 충돌이 없음

단점:

• 구성이 복잡

 

 

---