Java TIL - 250423

Java에서의 HashMap

1️⃣ HashMap이란?

Java에서 제공하는 Map 인터페이스의 구현체로,
키(Key)를 기준으로 값(Value)을 저장하고 조회하는 자료구조

2️⃣ HashMap 기본 사용법

import java.util.HashMap;

public class HashMapBasic {
    public static void main(String[] args) {
        // HashMap 생성 (키: 국가 이름, 값: 수도 이름)
        HashMap<String, String> capital = new HashMap<>();

        // put(): 키-값 쌍 추가
        capital.put("한국", "서울");
        capital.put("일본", "도쿄");

        // get(): 키를 이용해 값 조회
        System.out.println(capital.get("한국"));  // 출력: 서울

        // remove(): 키-값 쌍 삭제
        capital.remove("일본");

        // containsKey(): 특정 키의 존재 여부 확인
        if (capital.containsKey("한국")) {
            System.out.println("한국 수도는 " + capital.get("한국"));
        }
    }
}

3️⃣ 내부 구조 - 해시 테이블

hash("apple") → index 2 → [2] → (apple, 사과)
hash("banana") → index 7 → [7] → (banana, 바나나)

1. key.hashCode() → 해시값 생성

2. 해시값을 배열 인덱스로 변환 → index = hash % 배열크기

3. 해당 인덱스에 키-값 쌍을 저장 (Entry)

4. 같은 인덱스에 또 저장되면? → 충돌 발생

4️⃣ 해시 충돌(Collision) 처리 방식

서로 다른 두 개 이상의 키(key)가 같은 해시값 또는 같은 인덱스로 매핑되는 현상

윽...아직...이해...안....됨.....

1) 체이닝 (Chaining)

같은 인덱스의 버킷에 여러 Entry를 LinkedList로 연결

[5] → (apple, 사과) → (banana, 바나나)

2) 트리화(Treeification)

버킷에 Entry가 8개 이상이면 → 트리(레드-블랙 트리)로 변환

검색 시간: O(n) → O(log n)로 향상

5️⃣ 해시맵 내부 동작 (put & get)

✅ put(K key, V value)

1. key.hashCode() → 해시값 생성

2. index = hash & (table.length - 1) → 배열 인덱스 계산

3. 해당 인덱스 버킷에 저장

4. 이미 같은 키가 존재한다면 → 값 덮어쓰기

✅ get(K key)

1. hashCode() 계산 → 인덱스 찾기

2. 버킷에서 equals()로 키를 비교

3. 같으면 → 값 반환

hashCode()는 인덱스를 찾기 위해,
equals()는 실제 키 비교를 위해 사용
따라서, 두 메서드는 항상 함께 오버라이딩