자료구조 - 해쉬테이블

▶ 해쉬 테이블이란?

해쉬 테이블이란 key 와 value 로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있는 자료구조이다.

 

 

 

▶  해쉬 테이블의 구조

해쉬 테이블의 구조는 다음과 같다. F(key) → HashCode → Index → Value

즉 key 값을 해시 함수에 넣어 해쉬코드를 얻은 다음 특정 계산에 의해 배열의 Index 값을 얻고 그 배열에 저장한다.

 

다음 그림에서는 각 알파벳을 아스키코드로 변환한 다음 그 숫자들을 모두 더해 hashcode 로 나타낸다.

 

sung : s(115) + u(117) + n(110) + g(103) = 445

jin : j(106) + i(105) + n(110) = 321

hee : h(104) + e(101) + e(101) = 306

min : m(109) + i(105) + n(110) = 324

 

그리고 hashcode 를 배열의 인덱스로 나누면 

445 % 3 = 1

321 % 3 = 0

306 % 3 = 0

324 % 3 = 0

라는 값이 나타나고 배열 방에 LinkedList 형태로 저장한다.

 

▶ 해쉬 값이 충돌하는 경우

위 그림에서 jin, hee, min 을 해쉬 함수를 돌린 결과 Index 값이 0으로 모두 동일하게 나오는 경우에 충돌 문제가 발생할 확률이 높다.

 

 

 

 

 

▶ 좋은 해쉬 함수의 조건

위 그림은 테이블의 메모리 상황을 표현한 것으로 검은 영역은 데이터가 채워진 슬롯을 의미한다. 이 그림을 보면 데이터가 테이블의 전체 영역에 골고루 분포되어 있음을 알 수 있으며 그만큼 충돌이 발생할 확률이 낮다는 것을 의미한다.

 

 

 

 

반면 위 그림은 테이블의 특정 영역에 데이터가 몰린 상황을 보이고 있으며 충돌이 발생할 확률이 높은 상황이다.