이 섹션에서는 연결을 사용한 해싱이 무엇인지 볼 것입니다. Chaining은 충돌 해결 기술 중 하나입니다. 충돌을 피할 수는 없지만 충돌을 줄이고 동일한 해시 값에 대해 여러 요소를 저장하려고 할 수 있습니다.
이 기술은 우리의 해시 함수 h(x)가 0에서 6까지라고 가정합니다. 따라서 7개 이상의 요소에 대해서는 같은 방 안에 위치할 몇 가지 요소가 있어야 합니다. 이를 위해 우리는 그에 따라 저장할 목록을 만들 것입니다. 매번 O(1) 시간에 삽입을 수행하기 위해 목록의 시작 부분에 추가합니다.
더 나은 아이디어를 얻기 위해 다음 예를 살펴보겠습니다. {15, 47, 23, 34, 85, 97, 65, 89, 70}과 같은 요소가 있는 경우. 그리고 우리의 해시 함수는 h(x) =x mod 7입니다.
해시 값은
체인을 사용한 해싱은 다음과 같습니다. -