데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.
Hash Function (해시 함수)
정의
- key를 고정된 길이의 Hash로 변경해주는 역할을 한다.
- 이 과정을 hashing이라고 한다.
- Input : key, Output : Hash
Hash Table (해시 테이블)
정의
-
해시 함수를 사용하여 key를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조 이다.
-
단순하게, key & value로 이루어진 자료구조 라고 생각하면 된다.
구성
-
key
- 고유한 값, hash function 의 Input이 된다.
- key 값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼의 정보를 저장해야 하는 공간도 따로 마련해야 하기 때문에(key의 길이가 제각각 일 수 있다.), 고정된 길이의 해시로 변경한다.
-
hash function
- key를 고정된 길이의 hash 로 변경해 주는 역할을 한다.
- 서로 다른 key가 hashing 후 같은 hash 값이 나오는 경우가 있다. 이를 해시 충돌이라고 부른다. 해시 충돌 발생확률이 적을 수록 좋다.
- 해시 충돌이 균등하게 발생하도록 하는것도 중요하다. 모든 키가 같은 해시값이 나오게 되면, 데이터 저장시 비효율성도 커지고 보안지 취약해져서 좋지 안다. -
value
- 저장소(버킷, 슬롯)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장되어진다. -
has table
- 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소 또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조 이다.
- 데이터가 저장되는 곳을 버킷, 슬롯 이라고 한다.
장점
- 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있다.
(key-value 가 1:1 로 매핑되어 있기 때문에)
단점
- 해시 충돌이 발생
- 순서 / 관계 가 있는 배열에는 어울리지 않는다.
- 공간 효율성이 떨어진다.
(데이터가 저장되기 전에 저장공간을 미리 만들어놔야 한다.) - hash function의 의존도가 높다.
(해시 함수가 복잡하다면, hash를 만들어 내는데 오래 걸릴 것 이다.)
해시 충돌 해결 방법
체이닝
-
연결 리스트로 노드를 계속 추가해 나가는 방식
-
제한 없이 계속 연결 가능, but 메모리 문제
Open Addressing
-
해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방식
-
해당 키 값에 저장되어 있으면 다음 주소에 저장
선형 탐사
- 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
제곱 탐사
- 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함
