해시 테이블(Hash Table)

해시 테이블이란?

• Key-Value를 대응시켜 저장하는 데이터구조
• 해시: 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
• 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

해시테이블의 구조

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

Collision

데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상

충돌 현상에도 해시 테이블을 쓰는 이유는?

• 언제나 동일한 해시값 리턴하기 때문에 index를 알면 빠른 데이터 검색이 가능해짐
• 해시테이블의 시간복잡도 O(1) (이진탐색트리는 O(logN))
• 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
• 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해짐!

해시 충돌 해결방법

1. 개방 주소법(open address)

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

1-1. 개방 주소법 - 선형탐사법

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

1-2. 개방 주소법 - 제곱탐사법

• 빈공간을 n제곱 만큼의 간격을 두고 탐사하는 방법
• 일차 군집화 문제 일부 보완
• 문제점 : 이차 군집화 문제 발생 가능성

1-3. 개방 주소법 - 이중 해싱

• 해시 함수를 이중으로 사용
  • 해시함수 1 : 최초의 해시를 구할 때 사용
  • 해시함수 2 : 충돌 발생시, 탐사 이동 간격을 구할 때 사용
• 선형 탐사, 제곱탐사에 비해 데이터가 골고루 분포됨

2. 분리 연결법 (separate chaining)

• 해시 테이블을 연결리스트로 구성
• 충돌 발생시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결리스트를 사용하여 해당 테이블에 데이터 연결
• 장점: 제한없이 계속 연결가능
• 단점: 메모리 문제