개발 학습 실습실

이 사이트의 실습은 자바스크립트를 켜야 움직입니다. 아래는 같은 내용을 글로 적은 것입니다.

공부 › Java › 컬렉션

Set과 Map의 종류

같은 값을 넣었는데 꺼내는 순서가 왜 다른가

Set은 같은 값을 한 번만 담는 컬렉션이고, Map은 키와 값을 짝지어 담는 컬렉션입니다. 둘 다 Hash, LinkedHash, Tree로 시작하는 세 가지 종류가 있고, 무엇을 고르느냐에 따라 꺼낼 때의 순서와 넣을 수 있는 값이 달라집니다.

실행으로 대조 · JDK 21에서 서른 가지 조합을 실행해 대조

이 실습에 나오는 개념

List, Set, Map
자바 컬렉션의 세 가지 기본 유형이다. List는 순서가 있고 중복을 허용하며 인덱스로 접근한다. Set은 중복을 허용하지 않는다. Map은 키와 값의 쌍을 저장하며 키는 중복될 수 없다. 데이터의 성격(순서 필요 여부, 중복 허용 여부, 키로 찾는지)에 따라 고른다.
해시 테이블과 HashMap
키를 해시 함수에 넣어 나온 값으로 저장 위치(버킷)를 정하는 자료구조다. 키만 알면 위치를 바로 계산할 수 있어 조회, 삽입, 삭제가 평균 O(1)이다. 자바의 HashMap이 이 구조이며, 순서를 보장하지 않고 스레드 안전하지 않다.
LinkedHashSet과 LinkedHashMap
넣은 순서를 기억하는 HashSet과 HashMap이다. 해시 테이블에 넣는 방식은 같지만, 항목들을 넣은 순서대로 잇는 연결을 함께 유지해서 순회하면 넣은 순서대로 나온다. 이미 있는 값이나 키를 다시 넣어도 처음 넣은 자리는 바뀌지 않는다. 넣고 찾는 속도는 HashMap과 같이 평균 O(1)이고, 연결을 유지하는 만큼 메모리를 조금 더 쓴다. 넣은 순서대로 보여 줘야 하는 목록에 쓴다.
TreeSet과 TreeMap
값(TreeMap은 키)을 항상 정렬된 상태로 유지하는 Set과 Map이다. 내부는 레드-블랙 트리이며, 넣을 때마다 compareTo(또는 생성자에 준 Comparator)로 비교해 자리를 정하므로 순회하면 작은 것부터 나온다. 넣기, 찾기, 지우기가 모두 O(log n)이라 HashMap보다 느리지만, 가장 작은 값이나 어떤 값 이상인 범위를 바로 구할 수 있다. Comparator를 주지 않았거나 준 Comparator가 null을 허용하지 않으면 null을 넣을 때 NullPointerException이 난다. Comparator를 주지 않고 Comparable을 구현하지 않은 객체를 넣으면 ClassCastException이 난다. 두 값이 같은지는 equals가 아니라 비교 결과가 0인지로 판단한다.
시간 복잡도(Big-O)
입력 크기 n이 커질 때 알고리즘의 연산 횟수가 얼마나 빠르게 늘어나는지를 나타내는 표기다. O(1)은 크기와 무관하게 일정, O(log n)은 크기가 두 배가 되어도 한 단계만 늘어남, O(n)은 크기에 비례, O(n²)은 크기의 제곱에 비례함을 뜻한다. 데이터가 많아질 때 어떤 방식이 버티는지 판단하는 기준이다.

이렇게 바꿔 보세요

처음 설정으로 실행하면

  1. Set<String> set = new HashSet<>(): 빈 HashSet을 만듭니다. HashSet은 값의 hashCode로 칸 번호를 계산해 그 칸에 넣어 둡니다. 넣은 순서는 따로 기억하지 않습니다.
  2. set.add("grape"): "grape"의 hashCode로 계산한 칸 번호는 11번입니다. 꺼낼 때는 칸 번호가 작은 것부터이므로 지금 순서는 grape입니다.
  3. set.add("apple"): "apple"의 hashCode로 계산한 칸 번호는 1번입니다. 꺼낼 때는 칸 번호가 작은 것부터이므로 지금 순서는 apple, grape입니다.
  4. set.add("date"): "date"의 hashCode로 계산한 칸 번호는 0번입니다. 꺼낼 때는 칸 번호가 작은 것부터이므로 지금 순서는 date, apple, grape입니다.
  5. set.add("apple"): 같은 값이 이미 들어 있습니다. Set은 같은 값을 두 번 담지 않으므로 넣지 않고 false를 돌려주며, 그 false가 출력됩니다. 크기는 그대로 3개입니다.
  6. set.add("fig"): "fig"의 hashCode로 계산한 칸 번호는 5번입니다. 꺼낼 때는 칸 번호가 작은 것부터이므로 지금 순서는 date, apple, fig, grape입니다.
  7. System.out.println(set): 들어 있는 값을 처음부터 차례로 꺼내(순회) 출력합니다. HashSet은 칸 번호가 작은 칸부터 꺼냅니다. 넣은 순서(grape, apple, date, fig)도, 정렬된 순서(apple, date, fig, grape)도 아닙니다. 출력은 [date, apple, fig, grape]입니다.
  8. System.out.println(set.size()): 다섯 번 넣었지만 같은 값 하나는 다시 들어가지 않았으므로 크기는 4입니다.

실행 결과

코드

Set<String> set = new HashSet<>();
set.add("grape");
set.add("apple");
set.add("date");
System.out.println(set.add("apple"));   // 이미 넣은 값을 또 넣는다
set.add("fig");

System.out.println(set);                   // 처음부터 차례로 꺼내 출력
System.out.println(set.size());

이 모형의 전제

서른 가지 조합의 출력, 크기, 중복을 넣었을 때 돌려주는 값, 예외의 종류를 이 PC의 JDK 21에서 같은 코드를 실행한 결과와 대조했습니다. HashSet과 HashMap의 칸 번호도 실제 객체의 내부 배열을 들여다본 값과 대조했습니다. 다만 Hash 종류의 순회 순서는 자바 명세가 보장하지 않습니다. 여기에 보이는 순서는 JDK 21에서 칸이 16개(원소 12개 이하)일 때의 것이며, 버전이나 원소 개수가 달라지면 바뀔 수 있습니다. record의 hashCode가 내는 구체적인 값도 명세가 정하지 않으며, JDK 21에서는 Task(int id)의 hashCode가 id와 같았습니다. TreeSet이 같은 값인지 판단하는 기준은 equals가 아니라 compareTo의 결과가 0인지입니다. 성능 차이(Hash 종류가 Tree 종류보다 빠름)는 측정하지 않았고 문서에 적힌 시간 복잡도를 따랐습니다.

앞 실습: HashMap 내부 · 다음 실습: 스택·큐·우선순위 큐

이 실습에 나오는 개념

이 실습에서 보는 것

설정

코드


      
    


    

      
그림

      

      

    


    

      

      

      

    


  


  

    

      
실행 비교

      

      

    

    

      
이렇게 바꿔 보세요