3.3.1 체이닝

앞에서는 하나의 해시 값에 대해 하나의 원소만을 저장했습니다. 그래서 특정 해시 값 위치에 이미 원소가 존재한다면 새로운 값과 예전 값 중 하나를 버릴 수밖에 없었습니다. 체이닝(chaining)은 두 값을 모두 저장할 수 있는 여러 방법 중 하나입니다. 이 방법은 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라 하나의 연결 리스트를 저장합니다. 그러므로 새로 삽입된 키에 의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가합니다. 따라서 다수의 원소를 원하는 만큼 저장할 수 있습니다. 벡터 대신 연결 리스트를 사용하는 이유는 특정 위치의 원소를 빠르게 삭제하기 위함입니다. 다음 연습 문제에서 실제 체이닝 구현 방법을 살펴보겠습니다.