HashMap의 작동 원리는 무엇인가요?

HashMap은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조로, 효율적인 검색, 삽입, 삭제가 가능하도록 설계되었습니다.

HashMap의 작동 원리는 다음과 같은 주요 개념들을 기반으로 합니다.

1. 해시 함수(Hash Function) - 키를 해시 코드(hash code)로 변환하는 함수입니다.

- 해시 코드는 일반적으로 정수 값이며, 키의 내용을 바탕으로 고유하게 생성됩니다.

- 이 해시 코드는 배열 내 저장 위치(인덱스)를 계산하는 데 사용됩니다.

2. 버킷(Bucket) 및 배열 구조 - HashMap은 내부적으로 여러 개의 버킷을 담고 있는 배열을 가집니다.

- 각 버킷은 연결 리스트(또는 Java 8 이후부터는 트리 구조)로 구성되어, 같은 해시 인덱스를 가진 여러 엔트리를 저장할 수 있습니다.

- 해시 코드에서 배열 크기로 나눈 나머지를 인덱스로 사용하여 버킷 위치를 찾습니다.

3. 충돌 해결(Collision Resolution) - 서로 다른 키가 같은 해시 인덱스를 갖는 상황을 충돌이라고 합니다.

- 충돌이 발생하면 해당 버킷에 연결 리스트 형태로 엔트리를 추가합니다.

- Java 8 이후에는 충돌이 많아져 특정 임계치 이상이 되면 연결 리스트를 균형 잡힌 트리(예: 레드-블랙 트리)로 전환해 탐색 시간을 줄입니다.

4. 주요 동작 - 삽입(Put): 키의 해시 코드를 계산해 배열에서 적절한 버킷을 찾고, 해당 버킷 내에서 키가 이미 존재하는지 검색합니다.

존재하면 값을 갱신, 없으면 새로운 엔트리를 추가합니다.

- 검색(Get): 키의 해시 코드를 바탕으로 버킷을 찾고, 버킷의 리스트나 트리에서 키를 비교하여 값을 반환합니다.

- 삭제(Remove): 키로 버킷을 찾고, 해당 버킷 내에서 키와 일치하는 엔트리를 찾아 삭제합니다.

5. 확장(Resize) - HashMap의 내부 배열이 일정 크기 이상으로 차면, 성능 저하를 막기 위해 배열 크기를 두 배로 늘리고, 기존 엔트리들을 새 배열에 재배치(재해싱)합니다.

HashMap은 키를 해시 함수로 변환해 배열의 인덱스를 찾고, 같은 인덱스에 여러 키가 포함될 때는 충돌 해결 기법으로 연결 리스트 또는 트리 구조를 사용하여 데이터를 효율적으로 저장·관리하는 자료구조입니다.

이를 통해 평균적으로 O(1)의 빠른 접근 속도를 보장합니다.