What is a Hash Table?

해시 테이블(hash table)은 키-값 쌍을 저장하는 데이터 구조로, 키를 통해 항목을 찾는 사전과 같습니다. 핵심은 속도입니다. 잘 구축된 해시 테이블은 항목의 개수에 상관없이 평균 O(1) 시간 내에 항목을 찾거나, 삽입하거나, 삭제할 수 있습니다.

비결은 해시 함수(hash function)에 있습니다. 모든 키는 버킷 인덱스로 변환되므로, 전체 테이블을 훑지 않고도 정확히 어디를 찾아야 할지 알 수 있습니다. 서로 다른 두 키가 동일한 버킷에 도달하는 경우(충돌(collision)), 해당 버킷의 리스트에 함께 보관합니다. 이 전략을 체이닝(chaining)이라고 합니다.

해시 테이블의 다섯 가지 주요 연산은 다음과 같습니다:

1. Put: 키-값 쌍을 저장하거나, 키가 이미 존재하는 경우 값을 업데이트합니다.
2. Get: 주어진 키에 해당하는 값을 찾습니다.
3. ContainsKey: 테이블에 키가 저장되어 있는지 확인합니다.
4. Remove: 키-값 쌍을 삭제합니다.
5. Size: 현재 저장된 쌍의 개수를 반환합니다.

HashMap 클래스를 만들어 봅시다!