(Java) Map 구조 정리 - ADT 관점에서의 이해 (****별 다섯개****)

1. Map의 개념

핵심 특징

• Key - Value 쌍으로 구성
• Key는 중복 불가, Value는 중복 가능
• Key를 기준으로 빠르게 검색 및 저장 가능

Java에서는 Map<K, V> 인터페이스를 통해 이 ADT를 정의하고, 여러 구현체를 제공합니다.

---

2. Map의 주요 구현체

구현체특징

HashMap	내부적으로 Hash Table 구조 사용. 평균 O(1) 접근
TreeMap	내부적으로 Red-Black Tree 기반. O(log n) 접근
LinkedHashMap	해시 구조 + 삽입 순서 유지

이 글에서는 가장 널리 사용되는 HashMap을 기준으로 설명합니다.

---

3. Hash Table 기반 Map 구조

HashMap은 내부적으로 다음 구조를 가집니다:

📌 구성 요소

• 배열: 일정 크기의 버킷 공간 (예: 8, 16 등)
• Hash 함수: Key를 입력받아 정수(HashCode)로 변환
• Index 계산: hash % capacity 연산을 통해 배열 인덱스 결정

int index = hash(key) % capacity;

 

이렇게 계산된 index는 배열의 슬롯(bucket)을 가리키며, 여기에 해당 Key-Value가 저장됩니다.

---

4. 해시 함수 (Hash Function)

역할

• 임의의 Key 객체 → 고정된 정수로 변환
• Java에서는 기본적으로 Object.hashCode()를 사용

예시

String key = "apple";
int hash = key.hashCode();  // 예: 93029210
int index = hash % 16;      // capacity = 16일 때

 

 

사진 출처 - 유튜브 쉬운코드

---

 

5. 해시 충돌 (Hash Collision)

충돌이란 서로 다른 Key가 동일한 배열 인덱스에 매핑되는 현상입니다.

충돌 발생 상황

1. Key는 다르지만 hash 값이 동일
2. Hash 값이 달라도, 배열 크기(capacity)로 나눈 index가 동일

hash(key1) % capacity == hash(key2) % capacity

 

---

6. 충돌 해결 방식

HashMap에서는 두 가지 대표적인 방식으로 충돌을 해결합니다.

1. Separate Chaining (분리 체이닝)

• 버킷 슬롯마다 연결 리스트 또는 트리 구조를 만들어 충돌된 데이터를 저장
• Java 8부터는 충돌이 많아지면 리스트 → 트리(Red-Black Tree)로 전환

[4] → (key1, val1) → (key2, val2)

 

 

2. Open Addressing (개방 주소법)

• 충돌이 발생하면 다음 빈 슬롯을 찾아 데이터를 저장
• Java의 HashMap은 기본적으로 이 방식을 사용하지 않지만, 다른 언어나 라이브러리에서 자주 사용됨

대표 전략

• Linear Probing: 다음 인덱스를 순차적으로 검색
• Quadratic Probing: 제곱 증가 간격으로 검색
• Double Hashing: 2개의 해시 함수 사용

---

7. HashMap의 성능 특성

 

연산	평균 시간복잡도	최악의 경우
검색	O(1)	O(n)
삽입/삭제	O(1)	O(n)

최악의 경우는 모든 키가 같은 버킷으로 몰리는 경우 (예: 해시함수 성능이 나쁠 때)

---

8. 메모리 구조: Capacity와 Load Factor

• Capacity: 배열의 크기 (기본 16)
• Load Factor: 최대 적재율 (기본 0.75) → (저장된 요소 수 / capacity)가 이를 초과하면 배열의 크기를 2배로 재할당 (resize)

---

마무리

Map은 단순히 데이터를 저장하는 도구를 넘어서, 내부적으로는 효율적인 검색을 위한 자료구조 설계와 메모리 최적화 기법이 녹아든 구조입니다.
특히 Hash 기반 Map은 적절한 해시함수 설계와 충돌 해결 전략이 성능을 결정짓는 핵심입니다.

실무에서는 HashMap을 기본으로 사용하되, 정렬이 필요하다면 TreeMap, 삽입 순서를 유지하고 싶다면 LinkedHashMap 등을 선택하면 됩니다.