체이닝 (Chaining)

해시는 사실상 배열 한 개에 요소가 추가되어서 만들어지는 것입니다.

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

체이닝

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

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

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

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

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

재해싱

체인을 사용하면 자료구조가 찰수록 λ는 1보다 큰 수가 됩니다.
그렇기 때문에 크기 조정이 필요합니다.

1. 크기가 2배인 배열을 만듭니다.
2. 아래 코드에 따라 data의 index를 다시 결정하여 연결 리스트의 요소들을 옮깁니다.

// data의 index 결정
int idx = x.hashCode(s);
idx = idx & ox7FFFFFFF;
idx = idx % tableSize;

크기를 두배로 하면서 리스트의 위치를 새로운 배열에 그대로 옮기면 정보를 다시 찾고나 제거할때 올바른 위치를 찾을 수 없습니다.
그렇기 때문에 각 요소의 위치를 초기화 한 후, 처음부터 위치를 다시 지정해주어야합니다.