[자료구조] MAP 원리

프레임워크에서 제공하는 편의 기능에 익숙해져, 내부 동작 원리를 놓치고 있었다. 

 

1. Map 자료구조란

 

ㄴ데이터를 "순차적"으로 저장하는 List와 달리, Key-Value의 쌍 으로 데이터를 관리하는 자료 구조 

 

▶ 핵심특징

• key의 유일성 (ID 역할)
• 순서 없음 : 데이터가 들어온 순서를 보장하지 않음
• 빠른 검색 : Key를 알면 Value를 매우 빠르게 찾을 수 있음 

 

 

2. Map의 종류 

 

▶  Java의 주요 Map 종류 

• HashMap: 가장 일반적으로 사용됨. Hashing을 사용하며 순서를 보장하지 않음.
• TreeMap: Key를 기준으로 정렬된 상태를 유지함.
• LinkedHashMap: 입력된 순서를 기억함.
• Hashtable / ConcurrentHashMap: 멀티스레드 환경에서 안전(Thread-safe)하게 사용함.

 

 

3.HashMap 과 TreeMap 알고리즘 

ㄴ "내부 자료구조가 무엇으로" 되어 있는가 

특징	HashMap	TreeMap
내부 구현	Hash Table (배열 + 연결 리스트/트리 - 충돌)	Red-Black Tree (이진 탐색 트리)
순서	무작위 (보장 안 함)	Key 기준 오름차순 정렬
검색 속도	평균 $O(1)$	$O(log n)$
null 허용	Key, Value 모두 허용	Key는 null 불가 (비교해야 하므로)

 

 

▶  Hash 알고리즘 -> HashMap

내부적으로 "배열" 을 가지고 있고, key의 해시값이 배열의 인덱스 (접근 빠름)

 

• Hashing: 임의의 길이의 데이터를 고정된 길이의 데이터(정수 등)로 매핑하는 과정
• 동작 과정:
  • put("Key", "Value")를 호출
  • Java는 "Key" 객체의 hashCode() 메서드를 실행하여 고유한 정수값(Hash Code)을 얻음
  • 이 정수값을 배열(Bucket)의 크기로 나눈 나머지 값(Index)을 구함. (예: hash % array_size)
  • 해당 Index의 배열 공간(Bucket)에 데이터를 저장

•  서로 다른 두 입력값이 해시 함수를 거쳐 동일한 해시값(또는 나머지 값)을 가지는 경우는? => 해시충돌

 

▶  이진트리 알고리즘 -> TreeMap

Red-Black Tree(레드-블랙 트리)라는 자료구조 사용

• 원리: 데이터를 저장할 때 무조건 넣는 것이 아니라, 데이터를 저장할 때 대소 비교를 통해 위치를 잡음
  • 부모 노드보다 작으면 왼쪽, 크면 오른쪽으로 가지를 쳐서 내려가며 자리
• 정렬: 트리의 왼쪽부터 순회(In-order Traversal)하면 자연스럽게 오름차순 정렬된 데이터를 얻음
• 균형: 한쪽으로 데이터가 쏠리지 않도록(Skewed - 데이터 분산 불균형), 데이터를 넣을 때마다 트리의 높이를 균형 있게 재조정(Balancing)하기 때문에 검색 속도가 항상 $O(log n)$을 유지

 

구현원리 : https://jwdeveloper.tistory.com/281

 

 

 

4.   HashMap의 시간 복잡도 

• 평균(Best Case): $O(1)$
  • 해시 충돌이 없을 때. 해시 함수가 인덱스를 완벽하게 분산시켜서, 배열의 한 칸에 데이터가 딱 하나만 있는 경우
• 최악(Worst Case): $O(n)$ (Java 8 이전) 또는 $O(log n)$ (Java 8 이후)
  • 언제 발생하나? 모든 키가 우연히 **같은 해시값(같은 인덱스)**을 가질 때. **해시 충돌(Hash Collision)**

 

▶  충돌(Collision) 해결과 복잡도 변화

ㄴ한 바구니(Bucket)에 여러 데이터가 들어가야 한다면?

1. Chaining (체이닝): 같은 인덱스에 데이터가 오면 **Linked List(연결 리스트)**로 줄줄이 엮음
   • 이때 데이터를 찾으려면 리스트를 처음부터 끝까지 뒤져야 하므로 속도가 $O(n)$으로 느려짐.
2. Java 8의 최적화: 하나의 버킷에 데이터가 너무 많이 쌓이면(기본값 8개 이상), Linked List 대신 Red-Black Tree로 변환
   • 트리는 검색 속도가 빠르므로 최악의 경우에도 $O(log n)$을 보장

✅  대용량 데이터를 처리할 때 hashCode()를 잘 재정의해야

 

 

5. 코드로 확인하는 HashMap의 원리 

import java.util.LinkedList;

// 간단한 HashMap 구현 예시
class MySimpleHashMap<K, V> {
    // 1. 데이터를 담을 노드 클래스 (Key-Value 쌍)
    class Node {
        K key;
        V value;
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 2. 내부 저장소: Bucket들의 배열 (각 Bucket은 연결 리스트로 구현 - Chaining)
    private LinkedList<Node>[] buckets;
    private int size;

    public MySimpleHashMap(int size) {
        this.size = size;
        this.buckets = new LinkedList[size];
        // 배열 초기화
        for (int i = 0; i < size; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    // 3. 해시 함수: Key를 받아서 배열의 인덱스(0 ~ size-1)로 변환
    private int getBucketIndex(K key) {
        int hashCode = key.hashCode(); 
        // 음수 방지 및 배열 크기 내의 인덱스로 변환
        // ✨ hashCode 해시 알고리즘 - 대용량 데이터 처리할 때, 재 정의 필요 (충돌 없는 크기 조정) 
        return Math.abs(hashCode) % size; 👁‍🗨 버킷의 인덱스
    }

    public void put(K key, V value) {
        int index = getBucketIndex(key);
        LinkedList<Node> bucket = buckets[index]; // ✨ 해당 인덱스의 바구니(리스트) 가져오기

        // 4. 충돌 처리: 이미 같은 Key가 있는지 확인 (있으면 덮어쓰기)
        for (Node node : bucket) {
            if (node.key.equals(key)) {
                node.value = value; // Update
                return;
            }
        }

        // 5. 없으면 리스트에 추가 (✨ 충돌 시 뒤에 연결됨 -> Chaining)
        bucket.add(new Node(key, value));
    }

    public V get(K key) {
        int index = getBucketIndex(key);
        LinkedList<Node> bucket = buckets[index];

        // 해당 바구니(리스트)를 순회하며 Key 찾기
        for (Node node : bucket) {
            if (node.key.equals(key)) {
                return node.value; // O(1)에 가깝지만, 리스트가 길면 O(n)
            }
        }
        return null;
    }
}

public class Main {
    public static void main(String[] args) {
        MySimpleHashMap<String, Integer> map = new MySimpleHashMap<>(10);
        
        // "Lee"와 "Kim"의 해시값이 우연히 같다고 가정하면, 
        // 같은 Bucket(LinkedList)에 저장됩니다. (Collision 발생)
        map.put("Lee", 100); 
        map.put("Kim", 90); 
        
        System.out.println(map.get("Lee")); // 100
    }
}

 

• getBucketIndex(): 해시 알고리즘을 통해 배열의 방 번호를 찾는 과정
• LinkedList<Node>[]: 배열 안에 리스트. 이것이 해시 충돌을 해결하는 Chaining 방식
• bucket.add(): 같은 인덱스에 데이터가 쌓이면 리스트가 길어짐. 이 리스트가 너무 길어지면 조회 성능이 $O(1)$에서 $O(n)$으로 떨어지게 됨

 

 

6. equals()와 hashCode()의 관계

 

▶ 절대 깨지면 안 되는 규칙 (The Contract)

• 필수 규칙: 만약 두 객체가 논리적으로 같다면(a.equals(b) == true), 반드시 두 객체의 hashCode() 값도 같아야
• 참고 규칙: 두 객체의 hashCode() 값이 같다고 해서, 반드시 두 객체가 같은 것은 아니다. (a.equals(b)가 false일 수 있음. 이것이 바로 해시 충돌)

 

▶  get() 동작 원리 - HashMap이 데이터를 찾는 순서 (map.get(key))

ㄴ왜 hashCode()가 다르면 equals()가 같아도 소용없을까 ?

 

• 1단계 (Bucket 찾기): 찾으려는 Key의 hashCode()를 계산. 이 값을 이용해 **어떤 배열 인덱스(바구니)**로 갈지 결정
• 2단계 (객체 찾기): 해당 바구니에 도착하면, 그 안에 있는 데이터들을 하나씩 꺼내며 equals()로 비교. "너 내가 찾는 애 맞니?" 라고 물어보는 과정.
• 💥 여기서 문제 발생! : 만약 equals()만 구현하고 hashCode()를 구현하지 않으면, 1단계에서 아예 다른 바구니로 가버림. 2단계(equals 비교)는 시도조차 못 하고 null을 반환하게 되는 것.

 

 

▶  Java의 HashMap 같은 해시 기반 컬렉션이 올바르게 동작하기 위해 두 메서드는 반드시 함께 재정의

• equals만 재정의하고 hashCode는 재정의하지 않으면 어떻게 되나?
  • HashMap에서 데이터를 찾을 수 없게 됨
  • 같은 객체라고 생각하지만, 해시맵은 서로 다른 바구니(Bucket)에서 찾으려 하기 때문

import java.util.HashMap;
import java.util.Objects;

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // equals는 재정의: 이름과 나이가 같으면 같은 사람으로 취급
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    // 실수! hashCode()를 재정의하지 않음 
    // -> Object 클래스의 기본 hashCode(메모리 주소 기반)를 사용함
}

public class Main {
    public static void main(String[] args) {
        HashMap<Person, String> map = new HashMap<>();

        // 1. (홍길동, 30)을 Key로 저장
        map.put(new Person("홍길동", 30), "개발자");

        // 2. 똑같은 (홍길동, 30)을 Key로 조회 => 새로운 객체 생성 
        String job = map.get(new Person("홍길동", 30));

        // 결과는?
        System.out.println("직업: " + job); => 직업: null
    }
}

 

• 저장할 때: new Person("홍길동", 30)(객체 A)이 생성됩. hashCode를 재정의하지 않았으므로 메모리 주소(예: 100번지)를 기반으로 해시값을 만들어 1번 바구니에 넣음.
• 조회할 때: new Person("홍길동", 30)(객체 B)를 새로 만듬. 내용은 같지만 메모리 주소(예: 200번지)가 다름. 해시값이 달라져서 2번 바구니를 뒤짐.
• 결과: 2번 바구니는 비어있으므로(혹은 엉뚱한 데이터만 있으므로) null을 리턴

// Person 클래스 내부에 추가
@Override
public int hashCode() {
    // name과 age를 이용해서 해시값을 생성
    return Objects.hash(name, age);
}

• 객체 A와 객체 B는 메모리 주소가 달라도 내용(name, age)이 같으므로 같은 해시값
• get() 메서드는 같은 바구니로 찾아감.
• 바구니 안에서 equals()를 통해 "너 홍길동 맞네!" 하고 확인 후 "개발자"를 리턴.

 

 

7. ConcurrentHashMap의 "성능"과 "안전성" 보장 원리

 

1️⃣ 문제의 시작: HashMap은 왜 위험한가?

ㄴHashMap은 **Thread-safe(스레드 안전)**하지 않음.

• 상황: 스레드 A가 데이터를 넣는 도중에 스레드 B가 동시에 데이터를 넣으려 하면?
• 결과:
  • 데이터 유실: 두 스레드가 동시에 같은 인덱스에 값을 쓰면, 하나가 덮어씌워져 사라짐.
  • 구조 붕괴 (심각): 과거 자바 버전에서는 동시에 리사이징(배열 크기 확장)이 일어날 때, 내부 링크드 리스트가 꼬여서 무한 루프에 빠져 CPU가 100% 치솟는 버그.

 

2️⃣ 구식 해결책: Hashtable (무식한 잠금)

ㄴ초기 자바에는 Hashtable. (혹은 Collections.synchronizedMap 사용)

• 원리: 모든 메서드(get, put, remove)에 synchronized 키워드를 붙임.
• 비유: **"화장실이 하나뿐인 건물"**.
  • 누군가 화장실(Map)을 쓰고 있으면, 줄 서 있는 다른 사람들은(심지어 손만 씻으러 온 get 요청도) 문이 열릴 때까지 하염없이 대기.
• 단점: 안전하긴 하지만, 동시 접속자가 많으면 병목 현상(Bottleneck) 때문에 성능이 처참하게 느려짐.

 

3️⃣ 현대적 해결책: ConcurrentHashMap (똑똑한 잠금)

ㄴConcurrentHashMap은 **"전체를 잠그지 말고, 필요한 부분만 잠그자"**는 아이디어에서 출발.

ㄴ이것을 Lock Striping(락 스트라이핑) 혹은 **Fine-grained Locking(미세한 잠금)**.

 

[Java 8 이후의 동작 원리 ✨]

Java 8부터 ConcurrentHashMap은 성능을 극대화하기 위해 두 가지 핵심 기술을 섞어 사용

1. CAS (Compare And Swap): 락(Lock)을 걸지 않고 데이터를 안전하게 바꾸는 알고리즘
2. synchronized (Node Locking): 정말 필요한 "해당 버킷(Bucket)"만 잠그기

[동작 시나리오: put(key, value) 호출 시]

1. 빈 방(Bucket)에 넣을 때 (CAS 사용):
   • 데이터를 넣을 배열의 인덱스가 비어 있다면?
   • synchronized 락을 걸지 않음!
   • 대신 CAS 알고리즘을 사용.
   • CAS의 논리: "내 눈에 지금 여기가 비어 보이는데, 내가 넣는 순간에도 비어 있다면 넣고, 아니면(누가 선수 쳤으면) 다시 시도할게." -> 매우 빠름
2. 이미 누가 있을 때 (synchronized 사용):
   • 해당 인덱스에 이미 데이터(충돌)가 있다면?
   • 이때는 **해당 인덱스(Bucket)의 첫 번째 노드(Head)**만 꽉 잡음(synchronized).
   • 중요: Map 전체를 잠그는 게 아니라, 그 줄(Bucket)만 잠금. 다른 줄(Bucket)에 데이터를 넣거나 읽는 스레드는 전혀 방해받지 않음.
     • 비유: **"각 칸막이마다 잠금장치가 있는 공중화장실"**. 1번 칸에 누가 있어도, 2번 칸을 쓰는 데는 전혀 문제 없음.

4️⃣ 읽기 작업 (get)의 비밀

ㄴ그럼 get() 할 때도 락이 걸리나?

ㄴ"아님, ConcurrentHashMap의 get()은 락을 전혀 사용하지 않음(Lock-free)."

• 원리: 내부에 volatile이라는 키워드를 사용하여, 한 스레드가 변경한 내용을 다른 스레드가 즉시 볼 수 있도록(가시성 보장) 처리.
• 따라서 읽기 작업은 HashMap만큼 빠르면서도, 최신 데이터를 안전하게 가져옴.

 

5️⃣ 코드로 보는 차이점

// 실제 Java 8 ConcurrentHashMap의 putVal 메서드 단순화 버전
final V putVal(K key, V value) {
    int hash = spread(key.hashCode());
    
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
        // 1. 해당 버킷이 비어있는 경우
        if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // CAS(Compare And Swap) 시도: 락 없이 원자적으로 값 설정
            // casTabAt: "지금 비어있다면(null), 새 노드를 넣어라." 실패하면 다시 루프 돔
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break; 
        }
        // 2. 해당 버킷에 이미 데이터가 있는 경우 (충돌)
        else {
            // 그 버킷의 헤드(f)에만 synchronized를 건다! (Map 전체 락 X)
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 리스트 뒤에 추가하거나 값을 덮어쓰는 로직 수행
                    // ...
                }
            }
        }
    }
    return null;
}

특징	HashMap	Hashtable	ConcurrentHashMap
Thread-Safe	X (위험)	O (안전)	O (안전)
Lock 범위	없음	Map 전체 (모든 메서드)	데이터가 있는 Bucket만 (또는 CAS)
성능 (Write)	빠름	느림 (병목 발생)	매우 빠름 (동시 작업 가능)
성능 (Read)	빠름	느림 (Block됨)	빠름 (Lock-free)
null 허용	Key, Value 가능	불가	불가 (Key, Value 모두)