0Pricing
Java Academy · 강의

HashMap의 작동 원리

버킷, 해싱, 충돌을 살펴봅니다

HashMap의 작동 원리은(는) CoddyKit의 무료 Java Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Java Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

HashMap에 저장되는 것

HashMap은 키-값 쌍을 저장하며, 조회·삽입·삭제를 평균적으로 O(1)에 수행할 수 있습니다.

내부적으로 table이라는 배열을 유지합니다. 이 배열의 각 칸을 버킷이라고 합니다.

  • 키가 항목이 들어갈 버킷을 결정합니다.
  • 키를 조회했을 때 돌려받는 것이 값입니다.
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

키 해싱하기

put(key, value)를 호출하면 맵은 key.hashCode()를 호출해 int를 얻습니다.

그런 다음 HashMap은 내부 함수를 사용해 해당 비트를 분산시킵니다. 따라서 해시 코드가 좋지 않더라도 버킷 전체에 고르게 배치할 수 있습니다.

  • 최종 숫자를 hash & (table.length - 1)로 줄여 버킷 인덱스를 얻습니다.
  • table의 길이는 항상 2의 거듭제곱이므로 이 마스크가 작동합니다.
public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

버킷의 실제 동작

각 버킷에는 여러 항목이 들어갈 수 있습니다. 두 키가 같은 버킷으로 매핑되면 이를 충돌이라고 합니다.

충돌은 정상적으로 발생할 수 있으며 예상되는 상황입니다. HashMap은 버킷 안에서 항목을 서로 연결해 충돌을 처리합니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

충돌과 연결

Java 8 이전에는 충돌한 모든 항목이 버킷 내부의 단일 연결 목록에 들어 있었습니다.

조회할 때는 일치하는 키를 찾을 때까지 equals()를 호출하며 목록을 순회합니다.

  • 충돌이 적으면 사실상 O(1)입니다.
  • 한 버킷에 충돌이 많으면 해당 버킷에 대해 O(n)에 가까워집니다.
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

FB와 Ea가 충돌하는 이유

"FB"와 "Ea"라는 문자열은 Java에서 동일한 hashCode()를 가집니다. 이는 대표적인 충돌 예시입니다.

해시 코드가 같더라도 맵은 버킷 내부에서 equals()를 사용해 둘을 구분하므로 두 키를 별도로 유지합니다.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

부하율

부하율은 table이 커지기 전에 얼마나 찰 수 있는지를 제어합니다. 기본값은 0.75입니다.

  • 용량이 16이고 부하율이 0.75이면 항목이 12개일 때 크기 조정이 시작됩니다.
  • 부하율이 낮으면 메모리를 낭비하지만 충돌이 줄어듭니다.
  • 부하율이 높으면 메모리를 절약하지만 충돌이 늘어납니다.
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

table 크기 조정하기

항목 수가 capacity * loadFactor를 넘으면 table 크기가 두 배로 늘어납니다.

기존의 모든 항목은 더 크고 새로운 table에 다시 해시됩니다. 이는 비용이 큰 작업이므로 큰 맵에서는 미리 크기를 지정하는 것이 중요합니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

성능을 위한 사전 크기 지정

저장할 항목 수를 대략 알고 있다면 초기 용량을 지정해 크기 조정이 반복되는 비용을 피하십시오.

일반적인 기준은 다음과 같습니다. 초기 용량 = expectedSize / 0.75 + 1.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

null 키와 값

HashMap은 null 키 하나와 여러 null 값을 허용합니다.

  • null 키는 항상 버킷 0으로 들어갑니다(해시가 0으로 처리됩니다).
  • 키가 없는 경우와 값이 null인 경우를 구분하려면 getOrDefault를 사용하십시오.
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

순회 순서는 보장되지 않습니다

HashMap은 순회 순서를 전혀 보장하지 않습니다. 순서는 해시 코드와 버킷 배치에 따라 달라집니다.

예측 가능한 순서가 필요하다면 LinkedHashMap(삽입 순서) 또는 TreeMap(정렬 순서)을 사용하십시오.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

get() 경로 요약

조회는 다음 단계를 따릅니다:

  • hashCode()를 계산하고 비트를 확산합니다.
  • 버킷 인덱스를 찾기 위해 마스크를 적용합니다.
  • 버킷을 순회하며 equals()로 키를 비교합니다.
  • 일치하는 값을 반환하거나 널을 반환합니다.

좋은 hashCode와 올바른 equals를 사용하면 모든 단계가 빠르게 수행됩니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

빠른 확인

HashMap이 버킷을 찾는 방식을 이해했는지 확인해 보세요.

복습

HashMap이 내부적으로 작동하는 방식을 학습했습니다:

  • 키를 해싱하여 버킷에 매핑합니다.
  • 충돌이 발생하면 버킷에 항목을 연결하여 처리합니다.
  • 적재율(0.75)이 되면 크기를 두 배로 늘리고 재해싱합니다.
  • 미리 크기를 지정하면 비용이 큰 크기 조정을 피할 수 있으며, 반복 순서는 보장되지 않습니다.

다음에는 올바른 equals 없이는 hashCode만으로 충분하지 않은 이유를 살펴봅니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

자주 묻는 질문

“HashMap의 작동 원리” 강의는 무료인가요?

네 — “HashMap의 작동 원리” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Java Academy 강의 전체를 잠금 해제할 수 있습니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“HashMap의 작동 원리”에서 뭘 배우나요?

버킷, 해싱, 충돌을 살펴봅니다 브라우저에서 직접 실행하는 실습 코드로 Java Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Java Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Java Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

“HashMap의 작동 원리” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Java Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Java Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. HashMap의 작동 원리
  2. equals/hashCode 계약
  3. hashCode 구현
  4. 트리화와 성능
← Java Academy(으)로 돌아가기