자료구조 · 알고리즘 기초집LESSON 08

해시와 HashMap: 플레이어 기록을 빠르게 찾기

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

08강. 해시와 HashMap: 플레이어 기록을 빠르게 찾기

1. 이번 강의에서 해결할 문제

플레이어별 기록을 조회할 때마다 전체 목록을 훑으면 조회 횟수에 비례해 같은 비교가 반복됩니다.

2. 학습 목표

3. 핵심 개념

해시는 키를 정수 해시로 바꾸고 버킷 후보를 좁힌 뒤 동등성으로 최종 키를 확인합니다. 서로 다른 키가 같은 위치 후보를 갖는 충돌은 정상적인 상황이며 구현이 처리합니다. HashMap의 get·put은 해시가 잘 분산된 일반적인 상황에서 평균 O(1)이지만 순서 보장은 없습니다. 사용자 정의 키는 equals와 hashCode 계약을 함께 지켜야 합니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/PlayerRecordIndex.java

src/PlayerRecordIndex.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PlayerRecordIndex {
    record GameRecord(String playerId, int score) {}

    public static void main(String[] args) {
        List<GameRecord> records = List.of(
                new GameRecord("P1", 800), new GameRecord("P2", 1000),
                new GameRecord("P1", 1250));
        Map<String, List<GameRecord>> byPlayer = new HashMap<>();
        for (GameRecord record : records) {
            byPlayer.computeIfAbsent(record.playerId(), key -> new ArrayList<>()).add(record);
        }
        System.out.println(byPlayer.getOrDefault("P1", List.of()));
        System.out.println(byPlayer.getOrDefault("NONE", List.of()));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/PlayerRecordIndex.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/PlayerRecordIndex.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\PlayerRecordIndex.java
java -cp .\out PlayerRecordIndex

예상 결과: P1의 두 기록과 존재하지 않는 플레이어의 빈 목록이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

computeIfAbsent는 키가 처음 등장할 때만 새 목록을 만들고 해당 목록에 기록을 추가합니다. 색인 구축은 평균 O(n), 플레이어 키 조회는 평균 O(1), 반환된 기록 r개를 읽는 비용은 O(r)입니다. 모든 기록을 색인에도 참조하므로 O(n) 추가 공간이 필요합니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ