[Python] 알고리즘 개념10 퀴즈 - 해시 테이블과 해싱

 

 

📌 퀴즈 개요

다음 퀴즈를 통해 해시 테이블(Hash Table)과 해싱(Hashing) 개념을 정확히 이해하고 있는지 확인해 보세요! 😊

---

 

🧩 1. 개념 이해 문제

 

(1) 해시 테이블(Hash Table)의 특징으로 옳지 않은 것은?

1. 키-값(Key-Value) 쌍을 저장하는 자료구조이다.
2. 해시 함수(Hash Function)를 사용해 특정 위치에 데이터를 저장한다.
3. 검색, 삽입, 삭제 연산의 평균 시간복잡도는 O(1)이다.
4. 모든 경우에서 항상 O(1)의 성능을 보장한다.

 

(2) 해시 충돌(Hash Collision) 해결 방법이 아닌 것은?

1. 체이닝(Chaining)
2. 개방 주소법(Open Addressing)
3. 선형 검색(Linear Search)
4. 이차 탐사(Quadratic Probing)

---

 

 

🧩 2. 실전 문제

 

(3) 다음 코드의 실행 결과는?

hash_table = {}
hash_table['apple'] = 5
hash_table['banana'] = 3
print(hash_table['apple'])

1. 3
2. 5
3. 'apple'
4. KeyError 발생

 

(4) 다음 코드가 실행될 경우 발생할 수 있는 문제는?

from collections import defaultdict
hash_table = defaultdict(list)
hash_table[hash("apple")].append("apple")
hash_table[hash("banana")].append("banana")
print(hash_table)

1. 해시 충돌이 발생할 가능성이 있다.
2. 실행 시간이 O(n)으로 증가한다.
3. KeyError가 발생한다.
4. 무한 루프가 발생한다.

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

(1) 정답: 4
✅ 해시 테이블은 일반적으로 O(1)의 성능을 가지지만, 충돌이 많아지면 최악의 경우 O(n)까지 성능이 저하될 수 있습니다.

(2) 정답: 3
✅ 선형 검색(Linear Search)은 해시 충돌 해결 방법이 아닙니다. 충돌 해결 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing) 등이 있습니다.

(3) 정답: 2
✅ hash_table['apple'] = 5로 저장했으므로, hash_table['apple']을 출력하면 5가 나옵니다.

(4) 정답: 1
✅ 해시 값이 같은 경우 해시 충돌(Hash Collision)이 발생할 가능성이 있습니다. 따라서 체이닝 등의 충돌 해결 방법을 사용해야 합니다.

---