해시테이블(Hash Table)

키 (Key), 값 (Value)을 대응 시켜 저장하는 데이터 구조

• 키를 통해 해당 데이터에 빠르게 접근 가능

해싱

• 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

해시 테이블 구조

키 : 해시 테이블 접근을 위한 입력 값
해시 함수 : 키를 해시 값으로 매핑하는 연산
해시 값 : 해시 테이블의 인덱스
해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조

해시 충돌

해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우

• 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우

해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법 이 있음

해시 충돌 해결 방법 (1)

개방 주소법 (Open Address)

• 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
• hash와 value가 1:1 관계 유지
• 비어 있는 공간 탐색 방법에 따라 분류
  -- 선형 탐사법, 제곱 탐사법, 이중 해싱

개방 주소법 - 선형 탐사법

Linear Probing
빈 공간을 순차적으로 탐사하는 방법

• 충돌 발생 지점 부터 이후의 빈 공간을 순서대로 탐사

일차 군집화 문제 발생

• 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생

개방 주소법 - 제곱 탐사법

Quadratic Probing
빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법

• 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사

일차 군집화 문제 일부 보완
이차 군집화 문제 발생 가능성

개방 주소법 - 이중 해싱

Double Hashing
해싱 함수를 이중으로 사용

• 해시 함수 1 : 최초 해시를 구할 때 사용
• 해시 함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할 때 사용

선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨

해시 충돌 해결 방법(2)

분리 연결법 (Speparate Chaining)

• 해시 테이블을 연결 리스트로 구성
• 충돌 발생 시, 테이블 내의 다른 위치를 탐새하는 것이 아닌
  연결 리스트를 이용하여 해당 테이블에 데이터를 연결