[TIL] 자료구조 - 체이닝(Chaining)

※ 체이닝(Chaining)

- 요소마다 연결 리스트를 생성해 수많은 데이터를 수용할 수 있게 하는 방법으로 체인 해시는 가장 안정적이면서 보편적으로 사용되는 자료 구조 중 하나이다.

 

체이닝을 하면 수용 가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없다. 적재율 λ는 항목의 개수를 가능한 체인 개수로 나눈 값이고 체인 1개에 여러 항목을 넣을 수 있어 λ는 1보다 큰 수가 될 수 있다.

 

하지만 hashCode가 같은 숫자만 반환해 하나의 체인이 지나치게 길어진 경우 연결 리스트와 시간 복잡도가 같아지는 문제가 발생한다.