HashMap의 동작 원리와 해시 충돌 해결 방법에 대해 설명해주세요.

HashMap은 키-값 쌍을 저장하는 자료구조로, 빠른 검색 속도를 제공합니다. 동작 원리는 다음과 같습니다.

1. 해시 함수: 키를 해시 함수에 넣어 배열의 인덱스(버킷)를 얻습니다.
2. 저장: 해당 인덱스에 키-값 쌍을 저장합니다.

문제는 서로 다른 키가 같은 인덱스를 가리키는 해시 충돌이 발생할 수 있다는 점입니다. 이를 해결하는 방법은 크게 두 가지입니다.

• 체이닝(Chaining): 각 버킷을 연결 리스트로 만들어, 같은 인덱스에 여러 키-값 쌍을 저장합니다. 검색 시에는 해당 연결 리스트를 순회합니다.
• 개방 주소법(Open Addressing): 충돌이 발생하면, 다른 빈 버킷을 찾아 저장합니다. 선형 탐사, 이차 탐사, 이중 해싱 등의 방법이 있습니다.

HashMap의 성능은 해시 함수의 품질과 로드 팩터(데이터 개수 / 버킷 개수)에 따라 달라집니다. 로드 팩터가 높아지면 충돌 가능성이 커져 성능이 저하될 수 있습니다.