[문법] 자바 해시를 사용한 데이터 형식(HashMap, HashSet)

서론

※ 과거에 기록한 내용에서 중요한 부분만 발췌하여 모두가 이해하기 쉽게 다시 서술한다.

• 자바의 데이터 형식
• Arrays, Collections 클래스

본론

- 자바의 데이터 형식

[남궁성의 자바]

1. List : 데이터의 중복을 허용하는 순서가 있는 데이터 집합
2. Set : 데이터의 중복을 허용하지 않고, 순서가 없는 데이터 집합, List와 Set은 상위에 공통 기능을 가지는 Collection 인터페이스를 가짐
3. Map : 키-벨류 쌍의 데이터 집합, 상위에 Collection 인터페이스가 없음

 

🚨 컬랙션에서 동기화란?

Arraylist와 Vector, HashTable과 HashMap은 동일한 기능을 제공하는 것처럼 보이나, 동기화 지원 여부라는 차이가 있다.

 

-> HashTable의 Put

synchronized 키워드가 있는 데 이는 병렬 프로그래밍 시 공유 자원에 대한 동시 접근을 안전하게 관리해준다.

 

-> HashMap의 Put

synchronized가 존재하지 않아, 동기화를 지원하지 않는다.

 

HashTable : 병렬 처리를 고려해야 하는 상황에서 사용, 동기화 기능으로 약간의 시간 지연 발생
HashMap : 병렬 처리를 고려하지 않는 상황

위 두 타입을 선택해야 하는 기준은 다음과 같다.

 

-> Vector의 add

 

-> ArrayList의 add

List와 Vector에서는 Vector가 동기화를 지원한다.

 

- List

리스트와 관련된 모든 것을 알아보자

 

1. 리스트로 만드는 메서드

public static void main(String[] args) {
    List<Integer> list1 = List.of(1, 2, 3);
    List<Integer> list2 = Arrays.asList(1, 2, 3);
}

요소들을 입력 받아, 리스트를 반환하는 메서드들이 존재한다. 각 메서드마다, 불변성에 차이가 있고 of는 정적 팩토리 메서드명을 따른다.

 

2. Iterator

자바는 데이터 형식마다 구조가 다르기 때문에 구체적인 타입에 관계없이 일관된 방법으로 요소들을 순회하기 위해 Iterator 인터페이스를 제공한다. 만약 for문으로 순회하면 리스트 타입을 사용하다, set 타입으로 바꾸면 순회하는 코드도 수정해야 하는데 Iterator 타입으로 추상화하여 코드의 변경을 막는다.

 

-> 예시

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>(List.of(1, 2, 3));
    Iterator<Integer> iterator = list.iterator();

    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    Set<Integer> set = new HashSet<>(List.of(1, 2, 3));
    Iterator<Integer> setIterator = set.iterator();

    while (setIterator.hasNext()) {
        System.out.println(setIterator.next());
    }
}

Iterator를 사용하면 데이터 집합이 리스트냐 Set이냐에 상관없이 내부 내용물이 Integer인 것에 초점에 맞춰 Iterator 타입으로 통일하여 순회할 수 있다. Iterator는 일회용이라서 한 번 사용 후 다시 만들어야 한다.

 

-> Map과 Iterator

Iterator는 Collection 타입에 제공되는데 Map은 Collection의 하위 타입이 아니라서 iterator를 사용할 수 없다.

 

Map에서 Iterator를 사용하려면, Set으로 만들어야 한다.

 

entryset은 맵의 모든 키-value 쌍을 Set으로 반환한다.

 

Set의 요소는 Map.Entry 인터페이스 타입이며 Map.Entry는 Map 컬랙션 내부의 키-벨류 쌍 각각을 표현한다.

 

{하나 : "one", 둘 : "two"}

예를들어 위 예제에서는 Map.Entry(하나, one), Map.Entry(둘, two)라고 볼 수 있다. Map에 add를 하면 Map.Entry 하나가 Map에 저장된다.

 

getKey()
getValue()
setValue()

Map.Entry는 이러한 메서드를 제공하여 하나의 Map.Entry의 키-벨류에 접근할 수 있다.

 

Set<String> set2 = map.keySet();
for (String s : set2) {
    System.out.println(s);
}

keyset은 맵의 모든 키를 Set으로 반환한다.

 

Collection<Integer> set3 = map.values();
for (Integer i : set3) {
    System.out.println(i);
}

values는 맵의 모든 벨류를 Collection 타입으로 반환한다. 둘 다 키와 벨류를 순회할 수 있다.

 

- Map

Map은 키-벨류 형태의 컬랙션으로 키는 중복될 수 없지만, 벨류는 중복이 가능하다. 보통 HashMap을 사용하며, HashTable은 HashMap에서 동기화 기능을 넣은 것 뿐이고, TreeMap은 Hash 테이블 구조가 아닌 트리 구조를 가진 Map이다. HashMap은 순서를 유지하지 않으며, LinkedHashMap은 순서를 유지한다.

 

=> HashMap

앞에 Hash가 붙은 데이터 타입들은 모두 해시 기법을 사용한 것으로, 데이터의 수가 많아도 검색 속도가 O(1)의 시간복잡도를 가진다.

 

-> 해시 함수란?

가변 크기의 입력을 고정 크기의 값으로 변환하는 함수이다. 해싱 기법에서는 해시 함수를 사용하여 데이터가 저장될 주소를 만들고 이를 해시 코드라 부르며, 해시 코드를 벨류가 저장될 주소로 사용한다. 해시맵은 이러한 방법으로 중복을 제거하고 데이터를 저장한다. 이는 밑에서 중복 제거로 유명한 set 데이터 형식에서 알아본다.

 

-> 해시테이블이란?

앞 단에는 배열을 둬서 빠르게 찾고, 각 요소에는 연결 리스트를 둬서 변경에 유리하게 한 데이터 구조이다. 배열의 인덱스에 접근하여 연결 리스트에서 데이터를 찾을 수 있다. HashMap은 해시 테이블 형태로 키를 해시 함수에 넣어 해시 코드를 만들고, 이를 배열에 데이터가 저장될 주소, 즉 배열의 인덱스로 사용한다.

 

- Set

정의 : 중복을 불허하고 순서를 보장하지 않고, 특정 요소가 집합에 있는지 여부를 확인하는데 최적화 된 자료구조

Set과 관련된 모든 것을 알아보자

 

1. HashSet

일반적으로 순서와 중복이 없는 Set이 필요하면 HashSet을 사용하면 된다. 순서를 유지하고자 하면 LinkedHashSet을 사용한다.

 

🚨 Set에 해시가 어떻게 사용될까?

Hash가 붙은 데이터 타입은 모두, 해싱 기법을 사용하며, 해시셋은 내부적으로 해시맵으로 동작한다. 해시셋은 해시맵의 장점을 채택한 Set 구조인데, 해시셋이 해시맵으로 어떻게 동작하나 알아보자

 

-> set에 요소 추가

set에 요소를 추가하면 추가한 요소를 키로, 더미 객체를 벨류로 저장한다. 따라서 해시맵의 요소 추가 방식을 이해하면 set이 중복을 제거하고 요소를 관리하는 방법을 이해할 수 있다.

 

키 : 저장하려는 요소값
벨류 : 더미객체

해시맵은 키-벨류 형태의 데이터 형식이라 해시테이블 형태로 표현되는 것이 이해되지만, 셋은 요소 하나만 저장하기에 벨류가 무엇일지 의문이 들 수 있다.

 

사실, 해시셋은 데이터 하나만 저장하지, 키-벨류가 아니기 때문에 벨류에 저장될 데이터가 없기에 더미객체를 벨류로 사용한다.

 

✅ Set은 더미 벨류를 저장하는 것인가?

키 : 해시 인덱스로 배열에 저장할 위치 찾는 용도와 Node에 K 값으로 저장
벨류 : Set 내부 Map에 Node에 V에 Dummy 저장

이제, 해시 자료구조를 이해했고, Set의 내부 구조도 봤다. Set이 벨류를 왜 더미값으로 저장하는지 잘 이해가 안 될 수 있는데, 사실 Set은 값을 저장하고 반환하는 목적의 자료구조가 아니다. 그저 해당 값을 포함하고 있는지 빠르게 확인하는 용도로 사용된다. 

 

따라서 조회해서 반환하는 get 함수가 없다. 그저 입력한 키를 해시 인덱스로 변환하여, 해당 인덱스에 값을 포함하고 있다는 것만 나타내고 정의처럼 값의 포함 여부를 빠르게 파악하는 것에 최적화 되어있을 뿐이다.

 

-> set의 중복 제거

해시맵은 hashCode와 equals 메서드로 저장 위치를 정하고 중복을 제거하는 데이터 형식이다.

 

1. hashCode로 앞단 배열의 주소를 구하고 저장될 주소로 선택
2. 만약 해당 주소에 이미 요소가 있다면 equals로 실제 동일 값을 가지는 지 검사

set이 이러한 동작 방식을 그대로 사용한다. 자바의 primitive 타입은 기본적으로 중복을 제거하지만,

 

class Person {
    private int age;
    private String name;

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

객체 타입은 동일성과 동등성을 구현하지 않으면 중복되는 데이터를 넣어도 중복이 제거되지 않는다.

 

만약, 위 상황에서 개발자가 같은 필드값을 가지는 객체를 set에 중복되지 않는 것을 기대했다면, 논리적인 오류로 볼 수 있다. 이를 이해해보자.

 

동일성만 구현했을 경우, 중복값이 존재한다. 즉, Set은 주소는 같아도 데이터가 같은지 검사하는 과정이 필요하다.

 

동등성만 구현했을 경우, 중복값이 존재하며, Set은 내용이 같아도 주소가 같은지 검사하는 과정이 필요하다. 사실, 주소 검사를 먼저한다.

 

둘 다 구현했을 경우 중복값이 사라지며, Set은 동등성과 동일성을 모두 구현해야 중복을 제거한다.

 

✅ 해시맵에 중복 확인

-> hashCode 메서드를 구현하는 이유

해시함수의 특징은 동일값을 입력하면 항상 동일 출력이 나오는 것이다. 해시 코드 재정의 형태를 보면 같은 나이와 이름을 가지면 매번 동일 출력이 나올 텐데, 이를 통해 동일한 값을 가지면 배열에서 동일한 인덱스를 가지도록 하여 중복이라고 하기 위함이다. hashCode를 재정의하지 않으면 중복이 제거되지 않는 이유는 동일 값이라도 해시코드가 다를 테니 다른 값이기 때문이다.

 

-> equals 메서드를 구현하는 이유

해시맵에 put을 하면 먼저 hashCode를 구하고 해당 주소에 간다.

 

그 후 만약 해당 주소에 요소가 있다면 같은 요소인지 검사를 하게 되는 데 이때 동등성을 사용한다.

 

equals가 재정의 된 것을 보면, 동일 값을 가지면 True를 반환하여 중복임을 알린다. 이렇게 동작하는 해시맵을 사용하여 해시셋은 중복을 제거한다.

 

equals를 재정의하지 않으면 중복을 제거하지 않는 이유는 재정의 전에는 객체의 힙 주소 비교를 하기 때문에 같은 필드 값을 가지고 있더라도 객체가 다르면 다른 객체로 보기 때문이다. 해시코드와 객체의 힙 주소는 다르며, 해시 코드는 해시맵에서 저장될 인덱스를 주소로 표현하는 것 뿐이고 실제 객체의 주소는 힙 영역의 주소이다.

 

🚨 해시셋이 해시맵을 사용하는 이유 정리

검색 시 O(1)의 빠른 접근 속도
해시코드를 사용한 빠르고 명확한 저장 방식

이러한 장점을 사용하기 위해 해시셋이 해시맵을 채택했다.

 

-> 정렬

set은 순서가 없기 때문에 정렬이 불가능하며,

 

정렬을 하려면 List로 변환해야 하지만, 이 또한 순서를 유지 하지 않기 때문에 순서가 필요한 경우 Set을 사용하면 안 된다.

 

2. LinkedHashSet

시간복잡도 : O(1)
용도 : 데이터 중복을 불허해야 하는데 삽입 순서를 유지해야 할 때 적합

Set의 정의를 따르는 HashSet과는 달리 순서를 보장하는 Set이다. HashSet에 연결리스트를 추가해서 요소들의 입력 순서를 유지한다.

 

✅ 순서를 보장한다.

Set 인터페이스를 쓰면 정의에 따라서 기본적으로 순서를 보장하지 않는다고 가정하고 사용해야 한다. 어떤 구현체가 초기화될지 모르기 때문이다. 여러 구현체 중 LinkedHashSet은 순서를 보장하는 Set이고 Set을 써야 하는데 순서를 보장해야 하면 LinkedHashSet을 써야한다.

 

HashSet은 배열과 링크드 리스트를 사용하여, 해시 충돌이 일어날 경우 동일 해시 인덱스에 다른 값을 동일 링크드 리스트에 저장하여 관리한다. 이는 단순히 충돌 확률이 적어서 필요한 메모리만 사용하기 위해 LinkedList를 사용하는 거다. LinkedHashSet은 동일 해시 인덱스 외에, 다른 해시 인덱스에 저장되는 값이라도 입력되는 순서에 따라서 링크드 리스트로 연결하여 관리한다.

즉, 동일 해시 인덱스 끼리 따로 링리로 관리하고 다른 해시 인덱스라도 모든 입력 값을 링리로 관리하여 순서를 보장한다.

 

-> 구현 방법

1, 2, 5, 8, 4, 9 해시 인덱스에 일반 값이 저장되는 것이 아니고 노드가 저장되며 각 노드들이 다른 해시 인덱스를 가지더라도 링크드 리스트로 연결된다. 따라서 first부터 따라가면 순서대로 요소에 접근할 수 있다. tail을 가진 이중 연결 리스트로 내부에 구현되어 있다. 따라서 조금 용량이 나가고 무겁지만 O(1)의 성능을 보인다.

 

3. TreeSet

구조 : 이진 탐색 트리 형태로 데이터를 저장한다.
순서 : 입력 순서가 아닌, 정렬 순서로 관리한다.
시간복잡도 : O(log N)
용도 : 데이터를 범위 검색, 정렬 할 경우가 많을 때 사용한다.

 

-> 탐색 트리 구조

Set은 순서가 없는 데이터 집합이라고 했는 데, 이진 탐색의 특성에 맞게 순서가 있고 정렬이 된 상태로 존재한다. 탐색 트리 구조란, 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장하는 구조로, 데이터를 빠르게 탐색할 수 있어서, 탐색 트리라고 불리며, 중위 순회 시 오름차순 정렬이 되기 때문에 정렬된 상태로 데이터를 관리할 수 있다. 자식이 최대 2개인 경우 이진 트리이므로 TreeSet은 이진 탐색 트리 구조를 가진다고 할 수 있다. 검색 시 트리의 절반씩 확인하므로 logn의 시간 복잡도이다.

 

장점 : 검색과 정렬 속도가 빠름
단점 : 추가 삭제 속도가 느림

이진탐색 특성에 따라, 검색과 정렬에 유리하지만, HashSet보다 데이터 추가, 삭제에 시간이 더 걸린다.

 

-> 이진 탐색 트리의 한계

데이터가 한 쪽으로 치우져진 경우 가장 큰 값을 찾기 위해선 5개의 값을 다 비교해야 해서 O(n)이 걸린다. 이를 트리 불균형 문제라고 한다.

 

- 이진 탐색 트리 개선

따라서, 이런 문제를 해결하기 위한 다양한 알고리즘이 존재한다. TreeSet은 레드-블럭 트리 구조를 가지며 이는 트리가 불균형하게 됐을 때 동적으로 균형을 맞춰준다. 가운데 6을 기준으로 다시 좌우 균형을 맞추게 된다. 따라서 자바의 TreeSet은 균형을 유지하고 최악의 경우에도 O(logN)의 성능을 보장한다.

 

✅ B-Tree (Balanced-Tree)

동적으로 트리 균형을 맞추는 알고리즘으로, 리프 노드의 데이터가 꽉 찼을 때, 동적으로 확인하여 페이지를 분할하는 구조이다. 노드 분할, 높이 조정이 모두 동적으로 일어난다.

동적으로 트리 균형을 맞추는 알고리즘은 다양하다.

-> 비교 기준

이진 탐색 트리는 부모보다 큰지, 작은지 비교하는 과정이 필요하여, TreeSet을 생성할 때 정렬 기준을 인자로 받는다. 만약 정렬 기준을 넣지 않으면 요소의 클래스에 Comparable 정렬 기준 클래스를 상속받고, 재정의한 compare 메서드로 비교 기준을 결정한다.

 

위 코드는 Person 클래스의 나이로 정렬 기준을 주며, TreeSet을 선언하는 법을 보여준다.

 

- 실습

HashSet : 순서를 보장하지 않고 뒤죽박죽
LinkedHashSet : 입력 순서 보장
TreeSet : 정렬 순서

 

- 최적화

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            
        }
        
        // 여기
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

자바에서는 최적화 기법으로 빠르고 안전하게 Set을 이용할 수 있게 해준다. 해시 자료구조는 배열 크기의 75%를 차지하면 해시 충돌이 발생할 확률이 높아지고, 중복 체크 때문에 데이터 추가 시간이 오래 걸리기 시작한다. 따라서 자바 내부적으로 75%가 넘어가면 배열의 크기를 2배 늘린다. 2배 늘린다고 끝이 아니라 모든 기존 요소를 2배 크기 배열을 기준으로 다시 해시 인덱스를 구해서 삽입한다. 알아서 리해싱도 해주고 크기도 늘려주기 때문에 실무에서는 HashSet을 가장 많이 사용한다.

 

- Arrays

Math 클래스가 수학 관련 메서드들을 모아 놓은 클래스라면, Arrays는 배열을 다루는 데 유용한 static 메서드들을 제공한다.

 

1. toString()

배열을 문자열로 반환하는 메서드로, 배열의 데이터 타입별로 오버로딩 되어있다. 다차원 배열 출력은 deepToString을 사용한다.

 

2. equals()

배열은 등가 비교 연산자를 제공하지 않는다. 각 요소를 하나 하나 비교하는 과정이 필요하고 이를 메서드로 제공한다. 내용을 비교하여 전부 같아야 True를 반환한다. 다차원 배열 출력은 deepEquals를 사용한다.

 

3. sort()

배열을 정렬하는 메서드를 제공한다. List는 인터페이스에 sort가 메서드 멤버로 존재하지만 배열은 클래스나 인터페이스가 아니라서 정렬 메서드가 따로 존재한다. 정렬 기준은 이 블로그를 참고하자.

 

4. 배열 채우기

fill 메서드와 setAll 메서드가 있고, setAll은 람다식으로 배열을 채운다.

 

5. 검색

이진탐색이니 정렬이 필요하고, 원하는 요소의 인덱스를 출력한다. 없으면 -6을 출력한다.

 

- Collections

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    Collections.addAll(list, 1, 2, 3, 4);
    Collections.fill(list, 9);
    Collections.rotate(list, 2); // 오른쪽으로 2칸 회전
    Collections.swap(list, 0, 2);
    Collections.shuffle(list); // 순서를 무작위로 섞음
    Collections.replaceAll(list, 2, 1); // 2를 1로 대체

    // 비교 기준 Comparable 재정의 필수
    Collections.max(list);

    List<Person> people = new ArrayList<>();
    Collections.max(people);
}

class Person implements Comparable{}

Collections은 컬랙션을 다루는 데 유용한 static 메서드들을 제공한다. 기본적으로 addAll, fill과 같은 Arrays와 동일한 기능을 하는 메서드를 내장하고 있다.

 

1. 동기화

List<Object> objects = Collections.synchronizedList(new ArrayList<>());

ArrayList의 경우 기본이 동기화를 하지 않으므로, 항상 동기화 하는 것이 아닌 필요할 경우만 동기화하는 기능을 제공한다. 리스트를 동기화하면 Vector를 사용하는 것과 같다.

 

2. 변경불가

List<Object> objects = Collections.unmodifiableList(new ArrayList<>());

컬랙션을 수정할 수 없게 읽기 전용으로 만들어준다. 리스트를 인자로 주고 받을 경우 반드시 읽기 전용으로 반환하는 게 좋다.

 

3. 한 종류의 객체만 저장

List<String> strings = Collections.checkedList(new ArrayList<>(), String.class);
Map<String, Integer> stringIntegerMap = Collections.checkedMap(new HashMap<>(), String.class, Integer.class);

컬랙션은 원래 타입을 지정하지 않으면 여러가지 타입을 다 받을 수 있는데, 컬랙션에서 타입을 지정하여 한 종류의 요소만 받는 컬랙션을 만드는 것이다.

 

제네릭 타입을 지정하는 것과 같은 효과를 보인다.

 

참고

동등성과 동일성

자바의 불변성