▶ 해쉬 테이블이란?
해쉬 테이블이란 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으로 모두 동일하게 나오는 경우에 충돌 문제가 발생할 확률이 높다.
▶ 좋은 해쉬 함수의 조건
위 그림은 테이블의 메모리 상황을 표현한 것으로 검은 영역은 데이터가 채워진 슬롯을 의미한다. 이 그림을 보면 데이터가 테이블의 전체 영역에 골고루 분포되어 있음을 알 수 있으며 그만큼 충돌이 발생할 확률이 낮다는 것을 의미한다.
반면 위 그림은 테이블의 특정 영역에 데이터가 몰린 상황을 보이고 있으며 충돌이 발생할 확률이 높은 상황이다.
'CS > 자료구조' 카테고리의 다른 글
레드블랙트리 연습예제 (0) | 2024.04.09 |
---|---|
AVL 트리 연습용 예제 (0) | 2024.04.04 |
자료구조 - AVL 트리 (1) | 2024.02.01 |
자료구조 - 이진탐색트리 (0) | 2024.01.31 |
자료구조 - 보간 탐색 (0) | 2024.01.26 |