Collection 유형 파헤치기

Violet_Evgadn·2023년 4월 25일

Java

목록 보기

8/13

※ 이전에 설명했던 Collection 공통 함수 이외 Class에만 존재하는 특별한 함수들만 기입했다

List

List Interface란?

List는 "중복을 허용하며 순서가 존재하는 Collection"을 의미한다.

List는 순서가 존재하는 Collection이기 때문에 Collection 중에는 유일하게 Index가 존재하며, 객체에 접근할 때 Index로 접근할 수도 있다.

List는 Collection에 객체 그 자체를 저장하는 것이 아닌 객체 주솟값을 저장한다.

따라서 동일한 객체가 다른 Index에 들어가 있다 하더라도 Collection에는 같은 주솟값이 저장되어 있으므로 1개 Index의 데이터에 변형을 가할 경우 다른 Index의 데이터에도 영향을 끼칠 수 있다.

예시를 통해 알아보자.

class Point{
	int x;
}

public class DemoApplication {
	public static void main(String[] args) {

		ArrayList<Point> list = new ArrayList<>();

		Point p = new Point();
		p.x = 0;
		for (long i = 0; i < 4; i++) {
			list.add(p);
		}
		list.get(0).x = 3;
		System.out.println(list.get(1).x);
	}
}

ArrayList 0 ~ 3 Index에는 동일한 Point 객체가 저장되어 있다.

이 List에서 0 Index 객체를 추출한 이후 x 값을 바꾸고 1 Index 값의 x값을 출력해 보자.

3이 출력되었음을 알 수 있다.

Index자체는 0과 1로써 다르지만 Collection은 객체의 "주솟값"을 저장하기 때문에 결국 0 Index의 객체와 1 Index의 객체는 동일한 객체를 가리키고 있다. 이 때문에 0 Index 객체를 수정하면 0 Index에 저장된 주솟값을 가진 객체의 데이터가 수정되고, 똑같은 주솟값을 가진 1 Index 객체 또한 3을 출력하는 것이다.

이제 List의 대표적인 클래스 ArrayList, LinkedList, Stack, 그리고 약간은 생소한 Vector에 대해 알아보자.

참고

ArrayList를 선언할 때 List<T> list = new ArrayList<>();처럼 객체 Type을 Interface로 사용할 수도 있다.

하지만 이 경우 ArrayList의 모든 기능을 사용하지는 못하고 List Interface에 있는 함수들만 사용 가능하다.

이런 특징은 Set에서 더욱 두드러지는데, TreeSet에서만 활용할 수 있는 기능들은 Set<T> set = new TreeSet<>();로 지정할 경우 사용하지 못한다.

따라서 꼭 필요한 상황이 아니라면 사용하는 Collection Class로 객체 Type을 지정하는 것을 추천한다.

Vector

Vector<T> vector = new Vector<>();

가장 생소한 Vector에 대해 먼저 설명하는 이유는 현재는 거의 사장된 클래스이기 때문에 굳이 기억할 필요가 없기 때문이다.

현재 Vector 클래스는 기존에 존재하던 코드의 호환성을 위해 남겨져 있을 뿐 최근에는 Vector가 아닌 ArrayList 클래스 사용을 추천한다.

그렇다면 Vector와 ArrayList에는 어떤 차이가 존재하며 왜 ArrayList 사용을 추천할까?

결과부터 말하자면 Vector는 동기화 처리를 해주는 Class이고 ArrayList는 동기화 처리를 해주지 않는 Class이다.

동기화란 여러 Thread에서 1개 객체에 동시 접근하려고 할 때 동시에 데이터에 접근하는 것을 막아 한 번에 1개 Thread만 데이터를 수정하도록 하는 것이다.

Vector는 Thread 개수와 관계 없이 무조건 동기화 처리가 진행된다. 이 때문에 만약 Thread가 많은 상황에서 코드를 실행할 경우 Thread-safe(여러 User가 1개 객체를 동시에 변경해서 생기는 문제에 대하여 안전함)하다.

문제는 Vector는 Single Thread 환경일 때도 동기화 처리를 한다는 것이다.

Single Thread 상황에서는 스레드가 하나이기 때문에 굳이 동기화 처리를 수행할 필요가 없다. 하지만 Vector는 싱글 스레드 환경에서도 동기화 처리를 수행하며, 동기화 처리에도 자원과 시간이 소모되기 때문에 성능이 나빠지는 것이다.

또한 Vector 내부에는 스레드를 위한 로직도 포함되어 있으므로 코드가 무거워진다.

ArrayList는 반대로 동기화 처리를 수행하지 않는다. 따라서 Thread-safe 하지 않은 Class라고 할 수 있다.

하지만 자바에서는 동기화가 필요한 경우 "synchronized" 예약어로 쉽게 해결할 수 있다. 따라서 동기화가 필요한 메서드에만 synchronized 예약어를 사용한다면 Vector를 사용할 때보다 효율적인 코드 작성 및 자원 활용이 가능해지므로 Vector 사용 이점이 거의 없기 때문에 ArrayList 사용을 추천한다.

ArrayList

ArrayList<T> list = new ArrayList<>();

List 계열 뿐 아니라 Collection 클래스 중 가장 많이 활용되는 것이 ArrayList이다.

위에 말했듯 ArrayList는 이전에 지정된 저장 용량보다 많은 객체들이 들어오면 자동으로 저장 용량을 늘리므로 데이터 저장 시 Index를 벗어난다는 에러가 발생하는 것을 걱정할 필요가 없다.

또한 데이터를 삭제할 경우 배열은 Index 값이 Null(혹은 0)이 될 뿐 Index는 유지되는 반면에 ArrayList는 아예 해당 메모리를 삭제된 것으로 취급하여 삭제한 데이터 다음 Index부터 마지막 index까지 모두 앞으로 1씩 당긴다.

이 때문에 ArrayList가 배열보다 데이터의 추가/삭제가 용이하고 직관적인 Class이다.

물론 ArrayList는 데이터를 추가/삭제할 경우 데이터들의 Index들이 뒤로 밀리거나 앞으로 당겨지며 Overhead가 발생하여 성능 저하가 발생할 수 있다. 또한 공간이 부족해 자동으로 저장 용량을 늘릴 때도 어느 정도의 Overhead가 발생할 수 있다.

get(Integer index) : Index에 존재하는 데이터를 반환

LinkedList

LinkedList<T> list = new LinkedList<>();

자료 구조를 공부했을 때 배웠던 LinkedList와 동일하다.

각 Node는 이전 Node와 다음 Node의 포인터 값을 가지고 있어 저장한 포인터 값을 통해 다음 Node로 이동하는 방식으로 데이터를 조회한다.

LinkedList의 장단점을 모두 가지고 있는데, 추가/삭제에는 좋은 성능을 보이나 조회에는 ArrayList보다 안 좋은 성능을 보인다는 것이다.

하지만 LinkedList의 "삭제"에 좋은 성능을 보인다는 점에는 애매한 부분이 존재한다.

데이터의 삭제가 일어나기 위해선 먼저 해당 데이터를 가진 Node를 "조회"해야 한다. 즉 조회 이후에 삭제 과정이 발생한다는 것이다.

삭제 과정 자체만을 보면 LinkedList는 포인터 연결만 다시 해주면 되는 반면에 ArrayList는 다음 Index의 데이터부터 마지막 데이터까지 Index를 하나씩 당겨줘야 하므로 LinkedList가 속도면에서 훨씬 빠를 것이다.

하지만 데이터가 많을 경우 LinkedList의 조회 시간이 ArrayList의 조회 시간보다 길 것이고, 이는 삭제 과정의 속도 우위를 상쇄시켜버릴 수도 있다.

또한 데이터 추가 과정도 데이터가 중간에 삽입되는 경우가 많다면 LinkedList가 빠르겠지만, 데이터가 순차적으로 추가된다고 가정되는 상황에는 ArrayList가 훨씬 빠르다.

따라서 조회가 많이 일어날 경우 ArrayList, 추가/삭제가 모두 빈번히 일어나는 경우는 LinkedList, 조회와 추가/삭제 모두 빈번히 일어날 때는 ArrayList 사용을 추천한다.

LinkedList는 실제로는 Index를 가지고 있지 않지만 Index 값만큼 Pointer 이동을 수행하면 되므로 마치 Index를 가진 것처럼 활용할 수 있다.

LinkedList는 자체적으로 사용되는 것보다는 Queue를 만들기 위한 중간 다리 역할로 더 많이 활용된다.

get(Integer index) : Index에 존재하는 데이터를 반환

Stack

Stack<T> stack = new Stack<>();

자료구조에서 배웠던 Stack과 동일하다.

LIFO(Last In First Out; 마지막에 들어간 것이 먼저 나옴. 후입선출) 구조를 가진 Collection이다.

pop() : 마지막으로 Stack에 삽입된 Data를 Stack에서 삭제한 뒤 반환한다.
peek() : 마지막으로 삽입된 Data를 Stack에서 출력한다
- pop과는 다르게 Stack에서 삭제하지는 않는다.
push(T data) : Data를 Stack에 추가한다.
search(T data) : Data를 Stack에서 찾는다.
- 데이터가 Stack에 존재하지 않으면 -1, 존재할 경우 데이터의 Index를 반환

Set

Set Interface란?

데이터의 중복을 허용하지 않는 Collection이다.

"순서가 없는 Collection이다"라는 설명도 많은데 LinkedHashSet이나 TreeSet 같은 순서가 지정 된 Set들이 있어 이 정의는 애매한 것 같다.

Set은 Index가 없고 Map처럼 데이터에 접근할 Key값도 없기 때문에 Iterator(반복자)를 통해서만 데이터에 접근할 수 있다.

Set에는 대표적으로 HashSet, LinkedHashSet, TreeSet이 존재한다.

그렇다면 Set 계열은 어떻게 데이터의 중복을 확인할까?

Set은 두 객체의 hashCode() 값을 먼저 비교하고 이 값이 동일할 경우 equals() 메서드를 수행한다. 만약 equals() 메서드 또한 True를 반환하면 동등한 객체로 생각하여 데이터를 저장하지 않는 것이다.

HashSet

HashSet<T> set = new HashSet<>();

순서를 알 수는 없으나 접근속도가 매우 빠르다.

이는 임의 데이터에 접근할 때의 접근 속도가 빠르다는 것인데, 이유는 Set은 Iterator를 활용하기 때문이다.

물론 Index를 알고 있다는 가정하에 1개 데이터에 접근할 때는 List 계열이 더욱 빠르겠지만 모든 데이터 중 원하는 데이터를 찾을 때는 Iterator를 활용해 검색하는 HashSet이 훨씬 빠르다.

(참고로 Iterator와 Index를 통한 접근 속도의 차이 때문에 for(int i =0;i<s.size();i++) 방식보다 for(Point p:pointList) 방식을 선호하는 것이다.)

LinkedHashSet

LinkedHashSet<T> set = new LinkedHashSet<>();

순서가 아예 존재하지 않는 HashSet과는 다르게 Set에 추가된 순서로 데이터에 접근 가능하다.(ArrayList와 유사)

하지만 Set의 특징은 그대로 가지고 있기 때문에 Index를 통한 접근은 불가하다.

TreeSet

TreeSet<T> set = new TreeSet<>();                               // 오름차순 정렬
Set<T> reverseTree = new TreeSet<>(Collections.reverseOrder()); // 내림차순 정렬

TreeSet은 HashSet과는 다르게 이진 탐색 트리(BinarySearch Tree), 정확히 말해선 Red-Black Tree로 구현되어 있다.

Red-Black Tree로 구현되어 있다는 의미는 곧 "정렬이 되어있다"라는 의미이다.

기본적으로 TreeSet을 선언할 경우 "오름차순 정렬"로 Set을 생성하고, "Collections.reverseOrder()"를 new TreeSet의 Parameter로 전달해줌으로써 내림차순 정렬 또한 가능하다

TreeSet은 여러 가지 메서드를 통해서 정렬 방법을 지정할 수 있다.

descendingSet() : 내림차순으로 정렬된 NavigableSet 반환
descendingIterator( ) : 내림차순으로 정렬된 Iterator 반환

또한 기준 값을 지정하여 기준 값 범위 내 데이터들, 혹은 기준 값에 대한 특정 조건의 값들을 추출해 낼 수도 있다.

headSet(T toElement, boolean inclusive)
- toElement 보다 낮은 객체 들을 NavigableSet으로 반환
- inclusive : true - 기준 객체 포함(이하), false - 기준 객체 포함 X(미만)
tailSet(T fromElement, boolean inclusive)
- fromElement보다 높은 객체들을 NavigableSet으로 반환
- inclusive : true - 기준 객체 포함(이상), false - 기준 객체 포함 X(초과)
subSet(T fromElemenet, boolean fromInclusive, T * toElement, boolean toInclusive)
- fromElement보다 높고 toElement보다 낮은 객체들을 NavigableSet으로 반환
- inclusive : true - 기준 객체 포함, false - 기준 객체 포함 X

ceiling(T fromElement) : 기준 값 이상인 값 중 최소값
higher(T fromElement) : 기준 값 초과인 값 중 최소값
floor(T toElement) : 기준값 이하인 값 중 최댓값
lower(T toElement) : 기준값 미만인 값 중 최댓값
first() : 첫 번째 값(Default : 최솟값)
last() : 마지막 값(Default : 최댓값)
pollFirst() : 첫 번째 값을 반환하고 Set에서 값 지움
pollLast() : 마지막 값을 반환하고 Set에서 값 지움

Set 데이터 접근 방법

1. iterator를 활용한 접근

HashSet<Integer> set = new HashSet<>();
for(int i =0;i<10;i++) set.add(10-i);

Iterator iterator = set.iterator();

while(iterator.hasNext()) System.out.print(iterator.next()+" ");

2. for each문을 통한 접근

사실 for each문도 iterator를 활용한 기능이기 때문에 1번과 같은 방식이라고 말할 수 있다.

하지만 ArrayList 등을 활용하면서 iterator보단 for each문을 더 많이 활용해봤으니 아마 2번 방식이 더욱 익숙하지 않을까 싶다.

HashSet<Integer> set = new HashSet<>();
for(int i =0;i<10;i++) set.add(i);

for(Integer integer:set) System.out.print(integer+" ");

3개 Set 순서 확인

HashSet<Integer> hashSet = new HashSet<>();
TreeSet<Integer> treeSet = new TreeSet<>();
LinkedList<Integer> linkedList = new LinkedList<>();

StringBuilder hash = new StringBuilder();
StringBuilder tree = new StringBuilder();
StringBuilder link = new StringBuilder();

for(int i =1;i<6;i++) {
    hashSet.add(i);
    hashSet.add(-i);
    treeSet.add(i);
    treeSet.add(-i);
    linkedList.add(i);
    linkedList.add(-i);
}

for(Integer i : hashSet) {
    hash.append(i).append(" ");
}
for(Integer i : treeSet) {
    tree.append(i).append(" ");
}
for(Integer i : linkedList) {
    link.append(i).append(" ");
}

System.out.println(hash);
System.out.println(tree);
System.out.println(link);

먼저 각 Set에 "1, -1, 2, -2, 3, -3, 4, -4, 5, -5" 순으로 데이터를 주입했음을 코드에서 읽을 수 있다.

이제 아래 사진에서 결과를 확인해 보자.

먼저 HashSet이다. 도대체 어째서 -x가 x보다 먼저 나왔는지 알 수가 없다. 분명 x보다 -x를 나중에 주입했는데 말이다.

우리는 이를 통해 "HashSet은 순서가 딱히 존재하지 않는다"라는 사실을 확인할 수 있다.

TreeSet을 확인해 보자. TreeSet은 Red-Black Tree를 활용하므로 순서가 정렬되어 있어야 한다. 실제로 출력문을 확인해 보면 "-5, -4,..., 3, 4, 5"로 오름차순 정렬되어 있는 것을 확인할 수 있다. 즉 "TreeSet은 값의 크기순으로 정렬된 Set이다"라는 사실을 확인할 수 있다.

마지막으로 LinkedHashSet이다. LinkedHashSet은 "1, -1,..., 5, -5"가 출력됨을 알 수 있다. 이는 LinkedHashSet에 데이터를 주입한 순서와 동일하다. 즉, "LinkedHashSet"은 Set에 데이터를 주입한 순서대로 정렬된다라는 것을 알 수 있다

Map Interface

Map이란?

Key-Value 형식으로 데이터를 저장하는 Collection이다.

Map의 모든 데이터는 Key-Value 쌍으로 되어 있는데 Key 없이 value만 저장하거나 Value 없이 Key만 저장할 수는 없다.

Map에 저장된 1개의 Key-Value 쌍은 "Entry 객체"라고 불린다.

Map에 저장된 모든 Entry 객체들은 entrySet() 메서드를 통해 추출할 수 있다.

Map에서 Key값은 모두 고유하고 Value 값은 중복되어도 상관없다.

만약 기존에 저장된 Key값과 동일한 Key를 가진 Key-Value 쌍 데이터가 저장된다면 최근에 주입된 Key-Value 쌍의 Value가 Map에 저장된다.

Map에는 여러 종류가 있는데, 가장 대표적인 것은 HashMap과 TreeMap이다.

추가로 Hashtable이 존재하긴 하지만 List Interface의 Vector와 비슷한 존재이다.

Key값으로는 String 형이 사용되는 경우가 많은데, String은 문자열이 같을 경우 동등 객체가 될 수 있도록 hashCode()와 equlas() 메서드가 이미 재정의되어 있기 때문이다.

Hashtable

Hashtable<K, V> hashtable = new Hashtable<>();

Map에서 동기화를 지원하는 Class이다.(Thread-safe. List에서 동기화를 지원하는 것은 Vector Class이다.)

Vector와 똑같은 단점을 가지고 있기 때문에 현재는 거의 활용되지 않는 Class라고 할 수 있다.

물론 다른 Map Class와는 달리 Key나 Value에 Null 값이 들어갈 수 없다는 특징을 가지고 있어 이 특징을 활용하고 싶다면 Hashtable을 활용할 수는 있을 것이다.

하지만 굳이 Hashtable을 활용하기보다는 Validator를 활용하거나 데이터를 주입하기 전 값이 null인지 확인하고 주입하는 것이 더욱 안전한 방법이라고 생각하기에 개인적으로는 큰 활용도는 없을 것 같다.

HashMap

HashMap<K, V> map = new HashMap<>();

HashMap은 Hashing이라는 기술을 사용하여 Key값에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블 주소를 계산하여 항목에 접근한다.

HashMap은 HashSet과 동일하게 값을 주입하는 순서나 값의 크기와 관계없이 순서 없이 데이터를 저장한다.

put(K key, V value) : HashMap에 Key-Value 데이터를 추가한다
get(K key) : HashMap에 Key에 해당하는 Value값을 검색한
remove(K key) : key 값을 가진 Key-Value 데이터를 삭제한다.
containsKey(K key) : key 값을 가진 Key-Value 데이터가 있으면 true, 없으면 false를 반환한다.
containsValue(V value) : value 값을 가진 Key-Value 데이터가 있으면 true, 없으면 false를 반환한다.
keySet() : 저장된 모든 Key값들을 Set 형식으로 반환한다.
values() : 저장된 모든 Value값들을 Collection 형식으로 반환한다.

TreeMap

TreeMap<K, V> treeMap = new TreeMap<>();

TreeMap 또한 TreeSet과 동일하게 기존 이진 검색 트리의 성능을 향상한 Red-Black Tree를 기반으로 한 Map Class이다.

TreeSet과 동일하게 TreeMap도 Entry 객체(Key-Value 쌍 데이터)를 저장하며 정렬을 수행하는데, 이때 "Key값"을 기준으로 정렬을 수행한다.

정렬되는 숫자는 "숫자 > 알파벳 대문자 > 알파벳 소문자 > 한글"순이라고 나와 있는데, 그냥 사전 순이라고 생각하면 편하다.

당연히 Key값을 기준으로 정렬을 해야 할 필요가 있다면 HashMap 보다는 TreeMap을 사용하는 것이 더 유리할 것이며, 정렬이 이미 되어 있기 때문에 검색할 때도 HashMap보다는 TreeMap이 더욱 빠르다.

(물론 데이터를 주입할 때는 정렬 과정을 거쳐야 하는 TreeMap보다는 HashMap이 빠를 것이다)

TreeMap과 HashMap과의 차이는 데이터를 주입할 때 Key값을 사용하여 정렬한다는 것일 뿐 나머지는 동일하다.

put(K key, V value) : HashMap에 Key-Value 데이터를 추가한다
get(K key) : HashMap에 Key에 해당하는 Value값을 검색한
remove(K key) : key 값을 가진 Key-Value 데이터를 삭제한다.
containsKey(K key) : key 값을 가진 Key-Value 데이터가 있으면 true, 없으면 false를 반환한다.
containsValue(V value) : value 값을 가진 Key-Value 데이터가 있으면 true, 없으면 false를 반환한다.
keySet() : 저장된 모든 Key값들을 Set 형식으로 반환한다.
values() : 저장된 모든 Value값들을 Collection 형식으로 반환한다.

Map 모든 데이터 출력하기

1. keySet()을 통한 데이터 접근

HashMap<String, String> hashMap = new HashMap<>();

for(int i = 0; i < 10; i++){
    hashMap.put("key" + i, "value" + i);
}

for(String s: hashMap.keySet()){
    System.out.print(s+","+hashMap.get(s)+" ");
}

2. entrySet()을 통한 데이터 접근

이전에 말했듯 Map에서 Key-Value 데이터 쌍은 "Entry"라는 객체로 저장된다고 하였다.

따라서 entrySet()을 통해 저장된 모든 Entry 객체를 얻을 수 있다면 Map에 저장된 모든 데이터 또한 얻을 수 있을 것이다.

이때 entrySet() 메서드는 Entry 객체들을 "Set" 담아 반환함을 기억하자.

HashMap<String, String> hashMap = new HashMap<>();

for(int i = 0; i < 10; i++){
    hashMap.put("key" + i, "value" + i);
}
for(Map.Entry<String,String> entry:hashMap.entrySet()){
    System.out.print(entry.getKey() + "," + entry.getValue()+" ");
}

3. Iterator를 통한 접근

keySet()은 Key값들을 Set에 담아 반환했고 entrySet()은 Entry 객체들을 Set에 담아 반환했다.

Set은 Collection이므로 당연히 Iterator 또한 추출할 수 있을 것이다.

하지만 이 방법은 정말 많이 돌아가는 방법이기에 방법까지는 기록하지 않겠다.

HashMap과 TreeMap 비교하기

HashMap<Integer, String> hashMap = new HashMap<>();
TreeMap<Integer, String> treeMap = new TreeMap<>();

for(int i = 0; i < 5; i++) {
    int random = (int)(Math.random()*100);
    hashMap.put(random, "value" + i);
    treeMap.put(random, "value" + i);
}

StringBuilder hash = new StringBuilder();
StringBuilder tree = new StringBuilder();

for(Map.Entry<Integer, String> entry : hashMap.entrySet()) {
    hash.append(entry.getKey() + ","+ entry.getValue() + "   ");
}

for(Map.Entry<Integer, String> entry : treeMap.entrySet()) {
    tree.append(entry.getKey() + ","+ entry.getValue() + " ");
}

System.out.println("HashMap : "+hash);
System.out.println("TreeMap : "+tree);

위 코드에서 Key값에 0 ~ 100 사이 난수를, Value에는 "'value'+index값"을 세팅하여 Key-Value 데이터를 HashMap과 TreeMap에 저장했음을 볼 수 있다.

보다시피 TreeMap은 Key값을 기준으로 오름차순 정렬되어 있다.

하지만 HashMap 같은 경우 Key값을 기준으로 오름차순 정렬되어 있지도 않으며, Value값 기준으로 정렬되어 있지도 않고, 심지어 데이터를 주입한 순서(Index순)로 정렬되어 있지도 않다.

이를 통해 TreeMap은 Key값을 기준으로 정렬하여 값을 저장하지만 HashMap은 정렬하지 않고 랜덤 하게 값을 저장함을 알 수 있다.

Collection Interface를 상속하는 Queue는 Queue Interface 그 자체를 많이 활용하기보다는 Queue를 상속하는 Deque나 PriorityQueue에 많이 활용된다고 생각한다.

따라서 Deque나 PriorityQueue를 설명할 때 Queue를 짧게 설명하고 넘어가겠다.

Violet_Evgadn

혹시 틀린 내용이 있다면 언제든 말씀해주세요!

이전 포스트

Collection이란?

다음 포스트