Hash Chaining & loadFactor

💡 Hash Chaining

가장 안정적이며 보편적으로 사용되는 자료구조 중 하나이다.

파이썬의 딕셔너리도 이것을 기반으로 만들어졌으며 자바에서도 쉽게 해시를 만들 수 있게 API를 제공한다.
펄에서도 이 방법으로 연상 배열과 해시를 만든다.

 

해시는 사실상 배열 1개로 구성되어 있으며,

요소들이 들어가야 할 위치에 추가되면서 배열은 점점 채워진다.

 

그래서 배열의 위치마다 새로운 자료구조를 만들면서 수많은 데이터를 수용할 수 있도록 만드는것이다.

즉, Hash 배열의 각 요소에 자료구조인 LinkedList를 사용하며 각 요소는 테이블의 크기보다 클 수 있다.

 

어떤 자료구조가 가장 적합할까?

정답은 LinkedList 이다.

체인을 만들기 위해 배열의 각 위치마다 LinkedList를 만들어 주는 방법이며 위치마다 head 포인터가 존재한다.

 

예시

한 데이터의 hashCode를 구해서 정수를 반환받고 양수 변환 + 테이블의 크기만큼 % 연산한다.

그럼 테이블 내에 데이터를 넣을 위치가 나오고 그 자리로 가서 LinkedList의 head 포인터를 찾은 후,
LinkedList의 addFirst 메서드를 호출하여 값을 추가한다.

이때 LinkedList에 추가할때 시간복잡도는 상수여야 하므로 addFirst() or add()를 사용한다.

 

이전에 동일한 위치에 값을 추가해야 하는 문제가 있을때 이제는 LinkedList에 그냥 추가를 하면 된다.

즉, 상수 시간으로 어떤 요소든 추가하고 제거하며 찾을 수 있다. (add, remove, find)

수용할 수 있는 요소의 개수에도 제한이 없다. (물리적인 메모리 제한 제외)

---

Hash Chain 주의점

해시 내의 한 요소인 LinkedList 체인에 값을 계속 추가하면 해시가 연결 리스트가 되고,
이 상태의 해시에서 요소를 찾으려고 할때의 시간복잡도는 O(n)으로 바뀌어 버린다.

 

Worst Case : O(n)

즉, 체인 해시의 최악의 경우는 hashCode가 같은 숫자만 반환된다면 시간복잡도가 O(n)이 되는 경우이다.

 

Best Case : O(1)

반대로 최선의 경우는 hashCode가 매번 다른 숫자값을 반환하는 경우이다.

요소를 추가하려 할때 마다 다른위치에 저장이 되며 이때의 시간복잡도는 상수이다.

---

💡 loadFactor (적재율)

테이블 안 항목의 개수를 테이블의 크기만큼 나눈 값

해시 체인의 경우 적재율은, 항목의 개수를 다른 자료구조와 같이 가능한 체인 개수로 나눈 것이다.

간단히 말해서 체인의 배열에 들어있는 요소의 개수이다.

해시 체인의 요소인 자료구조가 금방 1이 될수 있으며 요소의 개수와 체인의 개수가 같다는 의미이다.

혹은 2,3,10 등 체인의 크기보다 훨씬 더 커질수도 있다.