해시 테이블(Hash Table) 자료구조는 무엇이며, 해싱(Hashing)의 기본 원리와 충돌(Collision)이 발생했을 때 해결하는 일반적인 방법 두 가지를 설명해주세요.

해시 테이블은 키(Key)와 값(Value)을 저장하는 자료구조로, 키를 해시 함수를 통해 배열의 인덱스로 변환하여 데이터를 빠르게 저장하고 검색할 수 있게 해줍니다. 해싱은 이 해시 함수를 이용해 키를 고정된 크기의 해시 값으로 변환하는 과정입니다.

하지만 서로 다른 키가 같은 해시 값을 가질 수 있는데, 이를 충돌(Collision)이라고 합니다. 충돌을 해결하는 대표적인 방법 두 가지는 다음과 같습니다.

첫째, 체이닝(Chaining)입니다. 각 배열의 인덱스마다 연결 리스트와 같은 별도의 자료구조를 두어, 같은 해시 값을 가진 데이터들을 연결 리스트에 저장하는 방식입니다.

둘째, 개방 주소법(Open Addressing)입니다. 충돌이 발생했을 때, 비어있는 다른 인덱스를 찾아 데이터를 저장하는 방식입니다. 이때 탐사(Probing)라는 과정을 통해 다음 저장될 위치를 결정합니다.