주요 용어
해시(Hash)
해시는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 의미하는데 이런 해시는 해시 함수(알고리즘)에 의해 얻게 된다. 간단하게 말해서 해시 함수를 통해서 변환된 값이 KEY 값이 되는 것이다.
기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 하지만 해시를 사용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다. 이때, 어떤 해시 함수를 사용하는지에 따라 성능이 바뀐다.
해시 테이블(Hash Table)
해시 테이블(Hash Table)은 키와 값을 함께 저장해 둔 데이터 구조인데 테이블에 데이터를 저장할 때 위치는 무작위로 지정되어 작성된다. 따라서 중간에 여유공간이 발생할 수도 있다.
해시 함수(Hash Function)
입력받은 값을 해시 값(고정된 길이)로 출력시키는 알고리즘을 의미한다. 이렇게 ㅊ출력된 해시 값은 알고리즘에 따라 다양한 결과를 보여준다.
대표적으로 나눗셈법(Devision Method)와 곱셈법(Multiplication Method)가 있다.
나눗셈법
원소를 해시테이블 크기로 나누어 나머지값을 테이블의 주소로 사용하는 방법
테이블의 크기보다 원소의 갯수가 많으면 충돌이 일어난다.
충돌(Collision)
충돌이 일어나는 이유는 키에 대한 해시값이 같은 경우 즉, 사용하고자 하는 해시 버킷이 이미 사용 중인 경우이다.
h(k1) = h(k2) 인 경우
충돌을 해결하기 위한 방법으로는 해시함수를 변경하거나 체이닝 기법을 사용, Open Addressing 방법을 사용할 수도 있다.
Chaining방법 - 충돌 o, but 최소화
체이닝이란 이름처럼 데이터들을 포인터를 이용해서 연결해나가는 것을 의마하는데 해시 테이블에서 출력이 일어나면 데이터의 key값을 포인터로 뒤이어 연결한다. 그렇기 때문에 최초의 위치를 탐색하는 해시 과정을 제외하고 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방법으로 이루어진다.
최악의 경우 모든 데이터의 해시값이 일치하여 한 인덱스에 저장될 수도 있어 O(n)의 복잡도를 가진다. JDK 라이브러리에 구현된 HashMap은 chaining 방법을 사용하며 버킷의 길이에 따라 LinkedList에서 Tree로 변경될 수도 있다.
Open Addressing 방법
모든 데이터를 테이블에 저장하는 방법으로 사용하려는 해시 테이블이 이미 사용 중이라면 다른 테이블을 사용하는 것이다. 포인터를 사용하지 않기 때문에 오버헤드를 방지할 수 있다. 그러나 테이블의 크기가 커질 수록 장점이 사라진다.
- Linear Probing
충돌이 발생하면 바로 다음 인덱스에 데이터를 저장하는 방식. 다음으로 이동해도 충돌이 발생했다면 또 다시 다음 인덱스로 저장한다. 그러나 primary clustering이라는 문제점을 가지고 있다. primary clustering이란 데이터들이 특정 위치에만 밀집하는 현상을 말한다. 이 현상으로 slot이 많아지면 많아질수록 탐색 시간이 엄청 늘어나게 된다.
- Quadratic Probing
충돌 시 primary clustering을 방지하기 위해서 hash 함수를 다음과 같이 이차식으로 만드는 것이다.
h(k, i) = (h'(k) + c1*i c2*i^2) mod mLinear probing과는 다르게 i가 2차식 형태를 취해, 한 칸씩 이동하는 것이 아니라 c1 i + c2 i^2만큼 이동한다.
그러나 Quadratic Probing에도 secondary clustering이라는 단점이 있는데 이는 처음 시작 해시값이 같을 경우 그 이후의 해시값도 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어난다는 것이다.
- Double hashing
Quadratic probing의 secondary clustering을 해결하기 위해서 사용하는 방법으로 해시 함수를 2개로 구성하는 것이다.
참고문헌
https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C
https://velog.io/@dadak/JS%ED%95%B4%EC%8B%9C%ED%95%A8%EC%88%98Hash-Function-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table
https://kang-james.tistory.com/136
