[자료구조/알고리즘] 해시 테이블

해시 테이블(Hash Table)

• 정의
  - 키(key), 값(Value)을 대응시켜 저장하는 데이터 구조
• 구조
  - 키: 해시 테이블 접근을 위한 입력 값
  - 해시 함수: 키를 해시 값으로 매핑하는 연산
  - 해시 값: 해시 테이블 인덱스
  - 해시 테이블: 키-값을 연관시켜 저장하는 데이터 구조
  
• 특징
  - 키를 통해 데이터에 빠르게 접근 가능(시간복잡도 O(1))
  - 키를 해싱하여 저장 키를 해싱하여 저장
  • 해싱: 해싱 함수를 통해 일반적으로 16진수 형식의 고정된 길이 문자열로 암호화 하는 것
  • 고정된 길이로 변환하기 때문에 다른 키 값이 같은 문자열로 변환되어 충돌이 발생할 수 있음

충돌 해결 방법

개방 주소법(Open Address)

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

선형 탐사법(Linear Probing)

• 빈공간을 순차적으로 탐사하는 방법
  - 충돌 발생 지점 부터 이후의 빈공간을 순서대로 탐사
• 일차 군집화 문제가 발생가능
  - 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생
  

제곱 탐사법(Quadratic Probing)

• 빈 공간을 N제곱만큼의 간격을 두고 탐사하는 방법
  - 충돌 발생 지점 부터 이후의 빈 공간을 N제곱 간격으로 탐사
  -> $2^0, 2^1, 2^2 ...$ 간격으로 탐사
• 일차 군집화 문제 일부 보완
• 이차 군집화 문제 발생 가능성

이중 해싱(Double Hashing)

• 해싱 함수를 이중으로 사용
  - 해시 함수1: 최초 해시를 구할 때 사용
  - 해시 함수2: 충돌 발생 시 탐사 이동 간격을 구할 때 사용
• 일차, 이차 군집화 문제 보완 가능

분리 연결법(Separate Chaining)

• 해시 테이블을 연결 리스트로 구성
• 충돌 발생 시 테이블 내의 다른 위치를 참색하는 것이 아닌 연결리스트를 이용하여 해당 테이블에 데이터를 연결
• key, value가 1:1 대응이 아니기 때문에 다른 방법에 비해 상대적으로 탐색 속도가 느릴 수 있음