Python의 딕셔너리 내부 구현과 해시 충돌 처리 방식을 설명해주세요.

Python 딕셔너리는 해시 테이블을 기반으로 구현되어 있습니다. 해시 테이블은 키를 해시 함수를 통해 특정 인덱스로 변환하여 값을 저장하는 자료구조입니다.

딕셔너리에 키-값 쌍을 저장할 때, 먼저 키의 해시값을 계산합니다. 이 해시값을 인덱스로 사용하여 해당 위치에 값을 저장합니다.

문제는 서로 다른 키가 동일한 해시값을 가질 수 있다는 점입니다. 이를 해시 충돌이라고 합니다. Python은 충돌 해결을 위해 개방 주소법(Open Addressing) 중 하나인 탐사(Probing) 방식을 사용합니다. 충돌이 발생하면, 미리 정의된 규칙에 따라 다음 빈 슬롯을 찾아 값을 저장합니다. 일반적인 탐사 방식으로는 선형 탐사, 이차 탐사 등이 있습니다.

Python 딕셔너리는 성능을 위해 테이블의 크기를 동적으로 조절하며, 키의 개수가 일정 비율 이상으로 증가하면 테이블 크기를 확장하여 탐색 효율을 유지합니다.