[Java] HashMap, HashSet 이란? - (1) collections란?

얼마 전, Hash에 대한 글들을 작성하며 Java에서 Hash를 사용하는 HashMap, HashSet 이라는 자료구조를 알게 되었다.

 

여러 블로그와 사이트를 돌아보며 공부한 기록을 남긴다.

 

---

 

collections 란?

'HashMap, HashSet에 대해 작성한다며 웬 갑자기 collections?' 라고 생각할 수 있지만,

collection 자료구조 중 하나인 Set에 대해 이해하기 위해서는 collections라는 녀석에 대해 알아야 한다.

 

collection 자료구조?

위에서 잠깐 언급된 collection 자료구조란 무엇일까?

 

collection이란 객체이며, 배열처럼 여러 원소를 담을 수 있는 자료구조다.

 

그래서 'collection', 한국어로는 '무리'를 뜻한다.

 

collections 란?

영문 Wikipedia의 Java Collections Framework 글을 보면 collections에 대해 아래처럼 소개하고 있다.

 

"The Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures"

 

즉, 재사용이 가능한 collection 자료구조를 구현하는 클래스 및 인터페이스의 집합이다.

 

Java의 colleciton 자료구조 유형

자바에서는 크게 네 가지 collection 자료구조 유형이 있다.

 

첫 번째로, 순서가 있는 목록인 List형.

두 번째로, 순서가 중요하지 않은 목록인 Set형.

세 번째로, 먼저 들어온 것이 먼저 나가는(FIFO) Queue형.

네 번째로, Key-Value 형태로 저장되는 Map형.

 

배열처럼 여러 원소를 저장하지만, 배열과는 다르게 위의 네 가지 유형의 자료구조는 정적 메모리 할당이 아닌 동적 메모리 할당을 하게 된다.

 

즉, 배열의 경우에는 new int[4]처럼 미리 선언을 통해 데이터를 저장할 공간을 만들고 선언한 메모리 공간만큼만 사용 가능하지만,

collection 자료구조는 메모리 공간이 계속 추가될 수 있다.

 

그래서 자바의 Garbage Collection의 관리 대상이 되기도 한다.

 

 

한 눈에 보는 collections

영문판 위키에는 collections에 대해 한 눈에 알 수 있도록 아래와 같은 그림들을 제공한다.

 

java.util.Collection class and interface hierarchy

Java's java.util.Map class and interface hierarchy

 

화살표가 마구 엉켜있어 조금은 헷갈릴 수도 있지만, 자세히 보다보면 정말 한 눈에 딱 들어오는 그림이다.

 

특이하게도 Map은 collection과 다른 그림으로 표현되었는데, Map은 collection과는 다르게 데이터를 다루기 때문이다.

 

그래도 더 쉬운 그림을 찾는 사람들을 위해 다른 그림들을 추가로 남긴다.

 

출처) https://www.crocus.co.kr/1553

출처) https://withwani.tistory.com/150

 

collections 주요 메서드

위 그림들에서 알 수 있듯이, collections는 결국 인터페이스이다.

인터페이스를 구현하는 구현체들은 인터페이스에 있는 메서드들을 모두 구현해야 한다.

 

Java 공식 문서에서 아래와 같은 collections 메서드들을 찾을 수 있다.

 

출처) https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html

 

참고로 <?> 와 같은 표현은 Generics라는 것인데, 해당 메서드를 호출한 객체를 반환한다.

 

 

List 인터페이스

Set이나 Map에 대해서는 이후 글에서 다루기 때문에 List 인터페이스에 대해 간단하게 알아보자.

 

collections의 다른 인터페이스들과 List 인터페이스의 가장 큰 차이는 배열처럼 순서가 있고 중복을 허용한다는 것이다.

 

위 그림들에서 볼 수 있듯이, ArrayList, LinkedList, Vector, Stack이 순서가 있는 Collection으로 많이 사용된다.

 

여기서 ArrayList와 Vector는 거의 동일하지만, ArrayList는 Thread Safe하지 않고, Vector는 Thread Safe하다.

 

Thread Safe ?

Thread Safe 하지 않다는 것은,

하나의 객체에 여러 사람이 접근해서 값을 변경하려고 하면 문제가 발생할 수 있다는 뜻이다.

 

동기화(Synchronized)와 같은 용어이다.

 

ArrayList

Vector 클래스를 개선한 것으로, 기능적으로는 동일하다.

 

내부적으로 Object 배열을 이용하는데, 배열과 거의 같다고 봐도 된다.

 

출처) https://history1994.tistory.com/19

 

배열처럼 인덱스는 0부터 시작하여 1씩 증가하며 데이터는 순서대로 저장된다.

 

하지만 만약 배열의 공간이 꽉 찬다면,

기존 배열의 크기가 더 늘어나는 것이 아니라, 크기가 늘어난 새로운 배열을 생성하고 그곳에 기존의 데이터를 복사한다.

 

즉, 동적인 배열이라고 생각하면 되고, 이러한 특성은 속도에 악영향을 미치기도 하는데,

 

이러한 배열 형태의 자료구조는 구조가 단순하고, 데이터를 읽는 속도가 빠르지만,

크기 변경이 어렵고(새로운 배열 생성), 비순차적 데이터에 대해 삭제나 추가를 할 때 시간이 많이 걸린다.

 

가장 마지막 인덱스에 있는 데이터의 삭제/추가는 빠르지만, 중간 인덱스에 위치한 데이터를 삭제/추가 하려면

삭제를 위해 또다시 새로운 배열을 생성하고 복사 과정을 거치거나, 중간에 데이터를 추가하기 위해 빈 공간을 만들어야 하기 때문이다.

 

LinkedList

출처) https://history1994.tistory.com/19

 

위에서 알아본 ArrayList의 단점을 극복하기 위한 자료구조이다.

 

다만, 배열은 연속적으로 데이터가 존재하여 주소가 일정하게 증가하지만,

LinkedList는 주소가 불연속적이고 뒤죽 박죽인 연결 형태로 되어있기 때문에 데이터를 읽는 속도가 느릴 수 있다.

 

하지만 삭제/추가 작업에 대해서는 연결을 끊거나 이어주기만 하면 돼서 배열보다 빠르고 쉽다.

 

Stack

출처) https://history1994.tistory.com/19

 

너무나 유명한 자료구조다.

 

위에서부터 순차적으로 데이터가 추가/삭제 되는 LIFO(Last In First Out) 특성을 갖고 있기 때문에 ArrayList 형태의 Vector 기반이다.

 

Queue

출처) https://history1994.tistory.com/19

 

Queue는 사실 List, Set, Map 과 같은 인터페이스지만,

이 글과 추후 작성할 글에서 자세히 다루지는 않기 때문에 여기서 잠깐 언급하려고 한다.

 

그리고 Queue는 LinkedList와도 밀접한 연관이 있는데,

처음에 들어온 데이터가 처음으로 나가는 FIFO(First In First Out) 특성을 갖고 있기 때문에 LinkedList 형태로 구현되어 있다.

 

ArrayList 형태로 구현하게 되면, 처음에 들어온 데이터를 POP 할 때마다 새로운 배열을 생성해줘야 하기 때문이다.

 

 

Sorted 인터페이스

위 그림들에서 Set과 Map 인터페이스 아래 부분에 보면 Sorted- 가 붙은

SortedSet / SortedMap 인터페이스 / 추상 클래스를 볼 수 있다.

 

그리고 이 녀석들은 각각 TreeSet과 TreeMap이라는 구현체를 만들어내는데,

이 둘은 Set과 Map의 기능을 갖고 있으면서 추가적으로 정렬 기능이 있는 것이 특징이다.

 

즉, 정렬 기능이 없는 Set/Map 인터페이스의 구현체는 HashSet, HashMap 이고,

정렬 기능이 있는 Set/Map 인터페이스의 구현체는 TreeSet, TreeMap 이라고 보면 된다.

 

보통 HashSet, HashMap을 생성하여 사용하다가 정렬 기능이 필요할 때, 아래처럼 TreeSet, TreeMap으로 변환하여 사용한다.

 

// HashSet -> TreeSet

Set<String> set = new HashSet<String>();
// 코드 진행
Set<String> treeSet = new TreeSet<String>();
treeSet.addAll(set);


// HashMap -> TreeMap

Map<String, Integer> map = new HashMap<String, Integer>();
// 코드 진행
Map<String, Integer> treeMap = new TreeMap<String, Integer>();
treeMap.putAll(map);

 

TreeSet

데이터들을 넣을 때마다 자동으로 오름차순으로 정렬된다.

 

TreeMap

Key를 기준으로 오름차순으로 정렬된다.

 

Comparator

TreeSet, TreeMap 모두 String이나 기본 데이터 타입과 같은 단순한 타입에는 기본적으로 오름차순(Ascending) 정렬이 되지만,

개발자가 직접 정렬 방식을 지정할 수도 있다.

 

이때 정렬 방식을 지정해주기 위해 사용하는 것이 Comparator 인터페이스이다.

 

방법은 아래와 같다.

 

class CustomComparator<T> implements Comparator<T> {
    public int compare(T param1, T param2) {
        // 비교 방법 구현
    }
}

 

먼저 위 코드처럼 Comparator 인터페이스를 구현한 본인만의 Comparator 클래스를 생성한 뒤,

원하는 비교 방법으로 compare() 메서드를 구현한다.

 

// CustomComparator로 TreeSet 생성
TreeSet<String> treeSet = new TreeSet<String>(new CustomComparator<String>());

// CustomComparator로 TreeMap 생성
TreeMap<String, String> treeMap = new TreeMap<String, String>(new CustomComparator<String>());

 

그 뒤, 위처럼 본인이 만든 Comparator 인터페이스 구현체를 사용하여 TreeSet, TreeMap을 생성하면 된다.

 

---

 

글이 또 엄청 길어졌다..

 

다음 글에서는 Set, Map에 대해 알아본다.

 

 

끝!