한국어
메뉴

자료 구조와 알고리즘

해시 테이블에서 충돌(collision)에 대한 설명으로 올바른 것은?

  1. A해시값에서 원래 키를 구할 수 있게 되는 것
  2. B서로 다른 키에서 같은 해시값(저장할 위치)이 구해지는 것
  3. C같은 키에서 실행할 때마다 다른 해시값이 구해지는 것
정답과 해설 보기

정답: B. 서로 다른 키에서 같은 해시값(저장할 위치)이 구해지는 것

해시 테이블은 키로부터 해시 함수로 저장할 위치를 계산하여, 평균 O(1)로 탐색·삽입·삭제를 할 수 있는 자료 구조입니다. 키의 종류는 표의 크기보다 훨씬 많으므로, 서로 다른 키가 같은 위치가 되는 것(충돌)은 피할 수 없습니다. 그래서 같은 위치의 원소를 리스트로 잇는 체이닝이나, 비어 있는 다른 위치를 찾는 개방 주소법 등으로 충돌을 처리합니다. 같은 키에서는 반드시 같은 해시값이 구해지지 않으면 탐색을 할 수 없으며, 해시값에서 원래 키를 알 수 있는지는 암호에 사용할 때의 성질로, 충돌과는 별개의 이야기입니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 크기 7인 해시 테이블(위치 0~6)에 해시 함수 h(k) = k mod 7로 키 10, 17, 24, 3을 이 순서로 저장한다. 충돌했을 때는 위치를 하나씩 뒤로 옮기며(6 다음은 0) 빈 위치를 찾는 선형 탐사법을 사용한다. 키 3이 저장되는 위치는?
  2. 해시 테이블의 충돌을 처리하는 방법으로 체이닝(같은 위치의 원소를 연결 리스트로 잇는다)과 개방 주소법(표 안의 비어 있는 다른 위치를 찾는다)을 비교한 설명으로 올바른 것은? 적재율은 저장한 원소 수를 표의 크기로 나눈 값으로 한다.
  3. 배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?
  4. 오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?
  5. 오름차순으로 늘어선 배열 a[0]~a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60에서 이진 탐색으로 38을 찾는다. 찾는 범위를 하한 lo = 0, 상한 hi = 9에서 시작하고, 가운데 위치를 (lo + hi) ÷ 2의 버림으로 한다. 38과 비교되는 원소의 값을 차례로 나열한 것은?