-
해시(Hash)가 뭐지?
개발을 하다보면 굉장히 자주 듣는 단어 중 하나인데, 찾아본 적이 없어서 거리감이 느껴지는 단어다.
위키피디아, 나무위키에 의하면, 해시 함수를 해시로 줄여 부르는 것이고 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수를 의미한다. 예를 들어, 어떤 숫자를 10으로 나눴을 때, 나머지를 구하는 함수가 해시 함수라고 한다.
특징
- 해시 함수 적용해서 나온 고정된 길이의 값을 해시값(해시 코드, 해시섬, 체크섬)이라고 한다.
- 복잡하지 않은 알고리즘으로 구현되어, CPU와 메모리 등의 시스템 자원을 덜 소모한다.
- 같은 입력값에 대해서는 같은 출력값 보장. 이 출력값은 고른 범위에 균일하게 분포하는 경향이 있다.
- 입력값보다 출력값 범위가 좁기 때문에 같은 출력값에 대한 입력값이 다른 경우도 존재한다. 이런 경우를 '충돌'이라고 한다.
해시 테이블
해시 테이블 - 위키백과 해시의 대표적인 용도 중 하나는 해시 테이블이라는 자료 구조에 사용하는 것이다. 해시 테이블은 key - value로 데이터를 저장하는 자료 구조다. 해시 테이블은 매우 빠른 검색 속도를 제공하는데, 그 이유는 내부적으로 버킷이라 불리는 배열을 사용해 데이터를 저장하기 때문이다. 이 때, key값을 입력값으로 해시 함수에서 얻은 해시값을 index로 사용하여 값을 저장하거나 검색한다. 실제 저장되는 장소는 버킷 또는 슬롯이라고 한다.
평균적으로 매우 빠른 검색 속도를 자랑하지만 해시 함수의 연산 결과에 의존적이기 때문에 해시 함수의 연산 속도가 느리면 성능이 최악으로 변한다.
시간 복잡도
key값으로 데이터를 찾을 때, 해시 함수를 1번만 실행해주면 되기 때문에 삽입, 삭제, 조회 평균 시간 복잡도는 O(1)이다.
해시값 충돌
해시 테이블에서 위에서 언급한 해시값 충돌이 발생한다면 해결법은 대표적으로 2가지가 있다.
분리 연결법(Separate Chaining)
새로운 값을 저장하려고 접근할 때, 기존 값이 있다면 추가 메모리를 사용해 다음 값의 주소를 저장하는 방법. 즉, 연결리스트를 활용해 같은 index를 가지는 데이터를 연결해주는 것이다. 충돌을 대비해 공간을 많이 확보할 필요가 없는 장점이 있지만 데이터가 많아질 수록 연결된 값들이 늘어나고 검색 효율이 떨어진다.
분리 연결법 단점 뿐만 아니라, 위 그림처럼 Ted Baker 데이터를 저장하기 위해 테이블에 접근했지만 Sandra Dee 데이터가 있으면 의도치 않게 다른 버킷에 데이터를 저장해야한다.
개방 주소법(Open Addressing)
추가적인 메모리를 사용하지 않고 비어있는 해시 테이블의 공간을 활용한다. 이를 구현하기 위한 방법은 3가지가 있다.
- 선형 탐색(Linear Probing): 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
- 제곱 탐색(Quadratic Probing): 저장할 해시 index 이동 폭을 1, 4, 9, ... 처럼 제곱으로 늘려가는 방식.
- 이중 해시(Double Hashing Probing): 해시값을 한 번 더 해싱하여 새로운 주소를 생성. 기존 해시의 규칙성을 없애버린다.
Reference