ฅ^._.^ฅ

해시맵

해시맵(HashMap) 이란?

키(Key) - 값(Value) 쌍으로 데이터를 저장하는 데이터 구조

해시 함수(Hash Function) 를 사용하여 데이터를 특정 위치(Bucket) 에 저장

해시맵 사용 예제

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("apple", 5);
        map.put("banana", 10);
        map.put("cherry", 7);
        
        System.out.println(map.get("banana")); // 출력: 10
    }
}

➡︎ O(1) 시간 복잡도로 빠른 데이터 조회 가능

➡︎ 키-값 저장 방식으로 중복 키 허용 안됨

트리

트리(Tree) 란?

계층적 데이터 구조로, 부모-자식 관계를 가짐

검색, 정렬, 계층적 데이터 저장에 유리

이진 탐색 트리

Binary Search Tree, BST

각 노드의 왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰 값을 가짐 (왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)

O(logN) 시간 복잡도로 탐색 가능 (균형이 잡힌 경우)

예제

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right);
        return root;
    }
}

➡︎ 계층적 데이터 표현 가능, 정렬된 데이터 탐색에 유리: O(logN)

➡︎ 균형이 깨지면 성능이 O(N) 까지 저하될 수 있음

균형 트리

• AVL 트리: 삽입/삭제 시 균형 유지 ➔ 항상 O(logN) 보장
• 레드-블랙 트리: 균형을 어느 정도 유지하면서 삽입/삭제 성능 향상

레드-블랙 트리 기반 TreeMap

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<Integer, String> tree = new TreeMap<>();
        tree.put(2, "apple");
        tree.put(1, "banana");
        tree.put(3, "cherry");

        System.out.println(tree.firstKey()); // 출력: 1
    }
}

➡︎ TreeMap 은 정렬된 순서로 데이터 저장하며, O(logN) 탐색 속도 제공

해시맵 vs 트리

‼️ 빠른 검색이 필요하면 HashMap, 정렬된 데이터가 필요하면 Tree