[자료구조] 해시 테이블 (Hash Table)

1. 해시 테이블(Hash Table) 이란?

: 해시 테이블은 (Key, Value) 식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에  value를 검색할 수 있는 자료구조이다. 

해시테이블은 key  값을 해시함수(Hash Function) 를 사용하여 변환한 값을 색인(index)으로 삼는다.

해시함수(Hash Function)를 사용해 key 값을 index로 변환하는 과정을 Hashing 이라고 한다. 

2. 해시 함수(Hash Function)

해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)로 이어지게 된다. 따라서 해시함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시테이블에 사용되는 대표적인 해시 알고리즘에는 다음과 같은 것들이 있다. 

• Division Method : 숫자 Key를 테이블의 크기로 나누어 나온 나머지를 인덱스로 사용한다. ( index = Key % 테이블 크기 ) 이때 테이블의 크기를 소수(Prime Number)로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋다. 예를 들어 Key 값이 23일 때 테이블 사이즈가 7이라면 index는 2다. 
• Digit Folding : Key의 문자열을 ASCII 코드로 바꾸고 그 값을 합해 테이블 내의 주소로 사용하는 방법이다. 위 예시와 비슷한 상황에서 사용될 수 있다. "Ryan" 같은 문자열을 R->82 + y->121 +  a->97  + n->110 = 410을 index로 사용하면 된다. 만약 이때 index가 테이블의 크기를 넘어간다면 Division Method를 적용할 수 있을 것이다.
• Multiplication Method : 숫자로 된 Key 값 K와 0과1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 index로 사용한다. index = (K*A mod 1)*m

 

참고

https://code-lab1.tistory.com/14