3-3) 해시 - LoadFactor 메소드, 충돌 해결, 체이닝

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

LoadFactor(적재율) 메소드

LoadFactor(적재율)는 해시에 데이터가 얼마만큼 있는지 알려주는 메소드이다. 배열의 크기에 비해 얼마정도 차 있는지를 알기 위합이다.  적재율은 자료 구조에 있는 항목 수를 자료 구조의 크기만큼 나눈 값으로, λ(람다)로 표기한다. (100 배열에 25칸 = 0.25λ)

 

 λ의 크기(0 - 비어있음 /  1/2 - 반 차있음  / 1 - 완전히 차 있음)에 따라 해시 테이블의 크기를 조절해야 한다. 해시 충돌을 해결하는 방식에 따라 적재율은 달라지기 때문에 충돌을 해결하는 것이 중요하다.

 

 

해시 충돌의 해결 방법

1. 개방 주소법

선형 조사법 (linear probing)

채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸(+1)을 확인하는 방법입니다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 합니다. 이를 사용하면 자료 구조가 채워지면서 더 많은 칸을 살펴봐야 한다. 또한 그렇기 때문에 다른 요소를 찾고자 할 때를 위해, 중간에 있는 요소를 제거하고자 하면 단순히 비워두어서는 안되며 표시를 남겨야 한다. 선형 조사법을 활용하게 되면 결국 배열에 순차적으로 추가하게 되어 데이터가 뭉치게 된다. 

 

2차식 조사법 (quadratic probing)

다음 칸 대신 1부터 순서대로 제곱하여 더한 칸( +1^, + 2^​​, ...  )을 확인하는 방법이다. 이렇게 하게 되면 선형 조사법을 사용했을 때보다 덜 순차적으로 요소를 채울 수 있다. 이러한 방법들을 사용할 때 테이블의 끝을 넘어간다면 % 연산을 해서 다시 테이블의 범위 안에 들어오게 한다. 선형 조사법과 2차식 조사법 모두 적재율이 빠르게 증가하여 테이블 크기를 바꿔주어야 한다.

 

이중 해싱 (double hashing)

이중 해싱에서는 서로 다른 2개의 hashCode 함수가 있다.(hashCode가 0을 반환해서는 안 된다.) 채우려는 공간이 이미 차 있다면 두 번째 hashCode를 불러와 두 hashCode의 결과를 더한 값을 테이블 내의 위치가 되게 하는 방법이다. 이중 해싱은 앞선 두 방법과 비교하여 데이터를 더 골고루, 더 임의적으로 넣을 수 있다는 장점이 있다. 그러나 해시 함수가 2개 필요하며, 자바는 두 번째 해시 함수가 있다는 것을 보장할 수 없다. 

 

 

2. 체이닝 (Chaining)

 

적재율 문제를 해결하기 위한 체이닝

체이닝(Chaining)은 요소마다 연결 리스트를 만들어 수많은 데이터를 수용할 수 있게 하는 방법이다. 각 위치에서 연결리스트의 head 노드를 갖고 addFirst를 호출한다. 이미 hashCode위치에 요소가 자리잡고 있을 때, 연결 리스트에 add 하면 된다. 

 

체인해시의 적재율 λ은 항목의 개수를 가능한 체인 개수로 나눈 것이다. λ가 1, 2, 3, 10이 될 수도 있으나 추가할 수 있는 자리는 남아있다. 수용 가능한 요소 개수에 제한이 없어지고 배열에 비해 크기 조정도 자주 할 필요가 없어지므로 체인 해시는 가장 안정적이고 보편적으로 사용되는 자료 구조 중 하나이다. 

 

그러나 만약 hashCode가 같은 숫자만 반환하여 같은 위치에만 계속해서 추가하게 되면(Worst case), 해시는 기본적인 연결리스트가 되므로 요소를 찾거나 제거하기 위한 시간 복잡도가 O(n)이 된다. 

반대로 hashCode가 매번 다른 숫자를 반환한다면(Best case), 다시 찾거나 제거하려 할 때 상수 시간 O(1)이 걸리게 된다. 즉, 체인 해시를 효율적으로 사용하기 위해서는 hashCode 함수가 최대한 해시충돌을 방지할 수 있도록 설계해야 한다.