[CS] 해시 충돌, Chaining, Open Addressing
해시 충돌을 알기 위해서는
- 해시
- 해시 테이블
- 해시 함수
을 알아야 하고,
-해시 충돌 해소 기법에 대해서도 알아보자.
해시
Hash
● 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것
● 키에 대한 해시값을 사용하여 값을 저장하고 key-value쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array이다.
● 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이 때 사용하는 함수(알고리즘)을 해시함수라고 한다.
● 해시 값 자체를 index로 하기 때문에 평균 시간복잡도가 O(1)로 매우 빠르다.
해시 테이블
Hash Table, Tash Map
Key와 Value를 갖는 자료구조,
주로 효율적인 검색에 활용.
해시 테이블은 해시 함수를 거쳐 연산된 값(hash 값)을 key값으로 하고, key에 해당하는 데이터를 Value로 하는 테이블 형태로 만든다. 이게 바로 해시 테이블이고, 버킷(or 슬롯)이라고 한다.
| key(hash value) | value(data) |
| 01 | 521-8976 |
| 02 | 521-1234 |
| ... | ... |
key를 통해서 value를 찾기 때문에 시간 복잡도는 O(1)이다.
Insert하는 경우도 O(1)
예를 들어
John Smith 사람의 전화번호를 찾는 과정을 보자.
해시 함수의 입력값은 "John Smith"이고 출력값은 "01"이다.
색인(Index)이 "01"인 bucket에서 "521-8976"을 찾을 수 있다.
해시함수는 해시테이블의 키 값으로 레코드가 저장되어 있는 주소(or 색인)를 산출하는 함수이다.
해시 함수
Hash Function
● 키에 대한 해시 값을 만드는 함수
● 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 함수
(충돌이 일어나지 않을수록 좋다)
● 대표적으로 나눗셈법(Division Method), 곱셈법(Multiplication Method)가 있다.
- 나눗셈법
: 원소를 해시테이블의 크기로 나누어 나머지 값을 테이블의 주소로 사용하는 방법.
테이블의 크기보다 원소의 갯수가 많으면 충돌이 일어난다.
key % 나머지 연산 = 결과값 → 결과값은 bucket에 들어간다.
나머지 연산 2보다는 10으로 하게되면 1~10까지의 골고루 결과값이 나올 수 있다. 하지만 아무리 잘 분산시키는 Hash Function을 만들더라도 결국에는 중복된 결과값이 나올 수 있다. 이를 해시함수 충돌 이라고 한다.
해시 충돌
Hash Collision
다른 내용의 데이터가 같은 키를 가지는 경우를 해시 충돌이라고 한다.
키에 대한 해시값이 같은 경우 = 사용하고자 하는 버킷이 이미 사용중인 경우
데이터를 key로 간소화하여 저장하는 아이디어는 좋지만, 해시 충돌이 발생할 수 있다.
같은 키 값을 가지는 데이터가 생긴다는 것은 특정 "키"의 버켓에 데이터가 집중된다느 뜻이다.
그래서 너무 많은 해시 충돌은 해시테이블의 성능을 떨어뜨린다.
그러므로 해시 함수를 잘 정의하여 해시 충돌을 최소화하는 것이 성능 개선에 도움이 된다.
해시함수의 입력값은 무한하지만, 출력값의 가짓수는 유한하므로 해시 충돌은 반드시 발생한다(비둘기집 원리)
Chaining
버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시충돌이 발생하면 연결 리스트로 데이터들을 연결하는 방식이다.
키 값을 포인터로 이어서 연결한다.
버켓이 꽉 차더라도 연결리스트로 계속 늘려가기 때문에 데이터의 주소값은 바뀌지 않는다.
최악의 경우 모든 데이터가 같은 해시 값을 가져 O(N)의 복잡도를 가진다.
JDK라이브러리에 구현된 HashMap은 Chaining방식을 사용하며 해당 버킷의 길이에 따라 LinkedList에서 Tree로 변경될 수 있다.
해시 충돌이 나면 해당 버킷(노드)에 chaining형태로 계속 뒤로 붙인다.
John Smith와 Sandra Dee가 152번에서 충돌이 났다.
open addressing기법과 다르게, 이 경우에는 John Smith의 체이닝 형태로 뒤에 바로 Sandara Dee가 붙는 것을 확인할 수 있다.
Open Addressing
해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방 주소법이라고 한다.
모든 데이터를 테이블에 저장하는 방법.
포인터를 사용하지 않아 오버헤드를 방지할 수 있고, 데이터가 적을 경우 연속된 공간에 인자를 저장하기 때문에 공간 효율이 높다.
하지만 테이블의 크기가 커질수록 장점이 사라진다.
비어있는 버킷을 찾아간다. 찾아가기 위해서는 아래와 같은 방법들이 있다.
- Linear probing (선형 탐색) : 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입
- Quadratic probing (제곱 탐색) : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..., 충돌 시 i^2 만큼씩 이동 )
- Double hashing (이중 해시) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.
John Smith와 Sandra Dee가 152번으로 해시 충돌이 발생했다.
이 경우 다음 빈 버켓을 찾아서 153번으로 Sandra Dee가 들어간 것을 확인할 수 있다.
Ted Baker도 153번에서 충돌이 발생해 다음 빈 버킷인 154번으로 밀려났다.
해시 충돌이 났을 때 바로 다음 버켓이 빈 경우가 가장 좋지만, 최악의 경우는 끝까지 모든 버킷이 차있는 경우이다.
정리
▷ 체이닝의 장점
연결 리스트만 사용하면 된다. 즉, 개방 주소법에 비해 복잡한 계산식을 사용할 필요가 적다.
해시테이블이 채워질수록, Lookup성능 저하가 Linear하게 발생한다.
▷ 개방 주소법의 장점
체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.
삽입, 삭제 시 오버헤드가 적다.
저장할 데이터가 적을 때 더 유리하다.
참고
https://umanking.github.io/2022/06/23/hash-function/
https://preamtree.tistory.com/20
https://power-overwhelming.tistory.com/42