해시 테이블의 충돌을 처리하는 방법으로 체이닝(같은 위치의 원소를 연결 리스트로 잇는다)과 개방 주소법(표 안의 비어 있는 다른 위치를 찾는다)을 비교한 설명으로 올바른 것은? 적재율은 저장한 원소 수를 표의 크기로 나눈 값으로 한다.

정답: A. 체이닝에서는 적재율이 1을 넘어도 저장할 수 있지만, 개방 주소법에서는 표의 크기를 넘어 저장할 수 없고, 적재율이 1에 가까워지면 탐색 횟수가 급격히 늘어난다

체이닝은 같은 위치의 원소를 리스트로 이으므로 원소 수가 표의 크기를 넘어도 저장할 수 있지만, 리스트의 평균 길이는 적재율에 비례하여 늘어나고 탐색의 수고도 늘어납니다. 개방 주소법은 표 안에만 저장하므로 원소 수는 표의 크기까지이며, 적재율이 1에 가까워지면 빈자리를 찾는 횟수가 급격히 늘어납니다. 어느 방법이든 적재율이 정해 둔 값(예를 들어 0.5~0.75 정도)을 넘으면 표를 키워서 모든 원소를 다시 넣는(재해싱) 것이 보통입니다. 개방 주소법에서도 충돌은 일어나며, 빈 위치를 찾는 것으로 대처하고 있습니다.