체이닝 (Chaining)

해시를 공부하다가 접한 문제인데,
해시는 사실상 배열 한 개에 요소가 추가되어서 만들어지는 것입니다.

체이닝은 이 배열의 위치마다 새로운 자료구조를 만들어 수많은 데이터를 수용할 수 있도록 만들어 줍니다.

체이닝

충돌을 피하기 위해 체인을 사용하는 방법이 있습니다
체인을 만들기 위해 우선 배열을 만들고 그 위치마다 리스트를 만들어 줍니다.

[{ob1-1:dd,ob1-2:dd....}, {ob2-1:dd, ob2-2:dd....}, {ob3-1:dd, ob3-2:dd...}...] 이런느낌

위 그림과 같이 배열마다 리스트를 만들어주고, 자리가 찰때마다 add를 해줄 수 있습니다.

이렇게 체이닝을 하면 수용가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없어집니다.

적재율 λ는 항목의 개수를 가능한 체인 개수로 나눈 값입니다.
체인 1개에 여러 항목을 넣을 수 있어 λ는 1보다 큰 수가 될 수 있습니다.

하지만 주의해야 할 점은 hashCode가 같은 숫자만 반환하여 하나의 체인이 너무 길어지면 결국 연결 리스트와 시간 복잡도가 같아지는 문제가 생길 수 있습니다.