해시 테이블
hash table이란 해시함수(hash function)를 사용하여 변환한 해시(hash)를 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조이다.
- 키(key): 해시 함수의 입력값, 해시 함수를 통해 변환되지 않은 값
- 해시(hash): 키를 해시 함수를 사용해서 변환한 결과값
- 버킷: 테이블의 각 요소
- 데이터: 키에 매칭되어 저장되는 값
- 해시 함수: 키를 해시로 바꿔주는 함수
- 다양한 길이를 가진 키를 일정한 길이의 해시로 변경해서 저장소를 효율적으로 운영할 수 있도록 해준다.
- 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요하다.
특징
- 저장, 삭제, 검색 과정이 빠르다 -
O(1) - 데이터가 저장되기 전에 저장공간을 미리 만들어둬야 하기 때문에 공간 효율성이 떨어진다.
- 해시함수에 의존도가 높다.
- 해시 함수가 복잡하다면, 해시값을 만들어내는 데 많은 시간이 소요된다.
- 해시 충돌이 발생할 수 있다.
- 사용 예제
- 보안(암호화)
- Address Book(주소록)
- 블록체인
- DNS
저장, 삭제, 검색
해시 함수에 키를 넣어서 해시를 만든 후, 해당 해시(인덱스)에 데이터를 저장하거나 삭제, 검색한다. -> 시간 복잡도가 O(1)
하지만, 해시 충돌이 발생하게 되면 충돌을 해결해야 하기 때문에 시간 복잡도가 커진다.
해시 충돌
해시 충돌을 해결할 수 있는 방법은 크게 2가지가 있다.
1. 개방 연결법(Open Addressing)
해시 충돌이 발생하면 탐사를 통해 비어있는 다른 인덱스에 데이터를 삽입하는 방법
개방 연결법도 대표적인 3가지 방법이 있다.
- 선형 탐사(Linear Probing): 충돌이 발생한 인덱스로부터, 고정된 숫자만큼 이동해서 비어있는 버킷(저장소)에 데이터를 저장한다.
- 2차 탐사(Quadratic Probing): 충돌이 발생한 인덱스로부터, 이동할 숫자의 제곱만큼 이동하여 빈 버킷에 데이터를 저장한다.
ex) 처음 충돌이 발생하면 1만큼 이동, 또 충돌이 발생하면 4(2^2)만큼 이동, 또 발생하면 9(3^2)만큼 이동 - 이중 해싱 탐사(Double Hashing Probing): 충돌이 발생하는 기존 해시함수 대신에 다른 해시 함수를 이용해서 해싱을 한다.
2. 분리 체인법(Separate Chaining)
같은 인덱스를 가지는 데이터가 여러 개인 경우, 그 인덱스에 연결 리스트 (Linked List)를 선언하고 각 데이터들을 리스트에 저장한다.
하지만 한 버킷에 중복으로 저장되는 데이터가 많아질수록(한 인덱스의 링크드 리스트의 사이즈가 커지면) 검색의 효율성이 떨어지기 때문에 해시 함수의 설계를 다시 고려해봐야 한다.
해시 충돌을 해결한다고 해도 해시 충돌로 인한 성능 저하는 막을 수 없다. 일정 데이터 수용률을 넘어서게 되면 저장/조회 성능이 점점 떨어지게 된다. 그럴 때는 더 큰 테이블을 만들어서 데이터를 옮기는 방법이 있다.(하지만 이 경우에는 공간 복잡도가 늘어나게 됨)
HashSet
HashMap
https://developer-talk.tistory.com/392
https://kumgo1d.tistory.com/41
