[Java] Collection

bbbooo·2024년 2월 17일

Java

목록 보기

3/4

들어가며

수없이 사용하지만 사실 잘 모르는 부분이 많았다. List, Set의 차이도 중복 허용을 제외하면 전혀 알지 못했고 시간복잡도에 대해서도 크게 생각하지 않았었다. 따라서, 부족한 부분을 채우기 위해 이번 글에서는 Collection에 대해 학습한 내용을 정리하고자 한다.

Collection Framework

자바에서 여러 데이터를 모아놓기 위해서 등장했다. 여러 데이터를 모아놓으려면 배열을 사용하면 된다. 하지만 자바는 배열의 크기를 지정되어 있기 때문에 기존에 지정한 배열보다 더 많은 원소를 넣으려고 하면 예외가 발생한다.

이러한 경우를 예방하기 위해 자바는 여러 데이터 관리를 위해 컬렉션 프레임워크를 제공한다.
컬렉션 프레임워크에는 크게 List, Set, Map이 있다.

위처럼 Map을 제외하면 전부 Collection을 상속받아 구현되어 있으며 데이터요소를 제네릭을 통해 타입을 지정할 수 있도록 되어 있다.

List

List는 순서를 가지고 중복을 허용하는 배열이다. ArrayList, LinkedList, Vector가 List를 상속받아 구현된다.

ArrayList는 객체가 삽입될 때 인덱스를 부여받아 데이터를 저장한다.

따라서 데이터에 접근할 때는 성능이 좋으나 중간에 요소가 삽입, 삭제가 일어나면 중간에서 뒤에 요소들은 인덱스를 한 칸씩 밀어야 하므로 성능이 좋지 않다.

LinkedList는데이터와 주소로 이루어진 클래스들을 순서대로 쭉 이어 연결한다. 값을 검색하려면 처음부터 연결된 리스트를 전부 탐색하므로 성능이 떨어지나 노드 삽입, 삭제에서는 노드를 단순히 연결하거나 끊어내기만 하면 되므로 성능이 좋다.

Vector는 기본적으로 ArrayList와 비슷하나 멀티 스레드에서 동기화를 지원한다. 그런데 멀티스레드 환경이 아니고 싱글 스레드 환경에서도 동기화를 한다. 즉 스트링버퍼와 빌더의 차이처럼 단일 스레드에서의 성능에서 유리한 점은 없다.

Set

Set은 순서가 없으며 데이터의 중복을 허용하지 않는다. List처럼 각 데이터의 위치를 알려주는 힌트를 제공하지 않는다.

Java에서 List에는 get() 메소드가 있어 인덱스의 값에 바로 접근해서 가져오지만 Set에는 이 메소드가 존재하지 않는다.

또 인덱스가 없어 데이터를 순회하기가 어렵지만 Iterator를 지원하기 때문에 이를 통해 Set을 전부 순회하며 값을 찾을 수 있다.

Set에는 HashSet, LinkedHashSet, TreeSet, EnumSet이 존재한다.

HashSet은 가장 기본적인 Set으로 입력 순서를 보장하지 않고 순서도 보장하지 않는다. 일반적으로 데이터의 중복 여부를 체크하는데 사용되며 hash를 통해 데이터를 빠르게 찾을 수 있다.

LinkedHashSet는 Set이지만 특이하게 데이터의 저장순서를 보장한다. 중복은 허용하지 않으면서 순서의 보장이 필요할 때 사용한다.

TreeSet은 HashSet처럼 순서를 보장하지 않으며 중복도 허용하지 않는다. TreeSet은 이진 트리를 이용해 구현되므로 Set이 정렬되어 있다. 즉 특정 구간의 집합 요소를 탐색할 때 유리하다.

EnumSet은 java.util에서 제공하는 Enum 클래스와 함께 동작하는 구현체이다. null 값을 추가하는 것을 허용하지 않으며 HashSet 보다 훨씬 빠른 고성능 구현체이다.

Map

Map은 특이하게 Collection 인터페이스를 상속 받지 않는다. Map은 key, value로 이루어져 있으며 Key의 집합은 Set으로 이루어져 있다.

자바에서 Map의 keySet 메소드를 사용하면 Set 객체를 반환하는 것을 확인할 수 있다. 즉 Key의 중복을 허용하지 않으며 같은 키로 Map에 Value를 저장하면 덮어 씌워진다.

Map에는 HashMap과 HashTable, LinkedHashMap, TreeMap이 존재한다.

HashMap은 가장 대표적인 Map 컬렉션이다. 기본적으로 크기가 정해진 배열처럼 어느정도 메모리를 확보하고 키에 값을 저장하는데, 저장공간 보다 많은 값이 들어오면 저장공간을 거의 두배로 늘린다.

따라서 Map에 들어오는 값의 개수를 안다면 초기에 지정해주는 것이 좋다. 또한, null을 허용하며 멀티 스레드에서 동기화를 지원하지 않는다.

HashTable은 null을 허용하지 않으며 동기화를 지원한다. 따라서 멀티 스레드 환경에 적합하다.

TreeMap은 TreeSet과 비슷하게 키가 정렬되어 정렬된 범위를 탐색할 때 유리하다.

Hashmap의 동시성

HashMap의 동시성

HashMap은 여러 스레드가 동시에 접근할 때 문제가 발생할 수 있다. 예를 들어, 한 스레드가 맵에 데이터를 추가하거나 삭제하는 동안 다른 스레드가 동시에 맵에 접근하려고 하면, 예측하지 못한 결과가 발생하거나 심지어는 무한 루프에 빠질 수 있다. 이러한 상황을 race condition 이라고 부른다.

대처방안

이러한 동시성 문제를 해결하기 위한 방법으로는 여러 가지가 있다.

첫 번째 방법은 Collections.synchronizedMap() 메소드를 사용하여 동기화된 맵을 만드는 것이다. 이 메서드는 주어진 맵에 대한 동기화된 (Thread-Safe) 뷰를 반환한다.

Map m = Collections.synchronizedMap(new HashMap(...));

두 번째 방법은 ConcurrentHashMap을 사용하는 것이다. ConcurrentHashMap은 동시성 환경에서 높은 성능을 제공하며, 내부적으로 데이터를 여러 세그먼트로 나눠서 관리함으로써 동시에 여러 스레드가 데이터에 접근할 수 있도록 한다.

Map m = new ConcurrentHashMap();

세 번째 방법은 Hashtable을 사용하는 것이다. Hashtable은 자체적으로 동기화를 제공하지만, 모든 메소드에서 동기화를 수행하기 때문에 ConcurrentHashMap에 비해 성능이 떨어진다.

Map m = new Hashtable();

따라서, 동시성 환경에서는 동기화된 맵, ConcurrentHashMap, 또는 Hashtable을 사용하는 것이 더 안전하다. 그러나 이러한 방법 역시 완벽하지 않으며, 적절한 동기화 전략을 수립하고 적용하는 것이 중요하다.

✅ ConCurrentHashMap
Hashtable이 동기화를 지원하면서 발생되는 성능적인 단점과 HashMap이 동기화를 보장하지 않는 단점을 보완하기 위해 Multi-Thread 환경에서 사용할 수 있도록 자바8에 나온 클래스가 ConCurrentHashMap이다.

concurrent 패키지에 존재하는 컬렉션들은 락을 사용할 때 발생하는 성능 저하를 최소한으로 만들어두었으며, 여러 개의 락을 가지고 해시값을 이용해 이러한 락을 분할하여 사용하는 Lock Striping 기법을 사용하여 동시에 여러 스레드가 하나의 자원에 접근하더라도 동시성 이슈가 발생하지 않도록 도와줍니다.

하지만 HashMap과 다르게 key,value에 null을 허용하지 않는다. putIfAbsent 메소드를 가지고 있음.

✅ Lock Striping 기법
테이블 버킷을 독립적으로 잠그는 방식이다. 빈 버킷으로의 노드 삽입은 lock 을 사용하지 않고 단순히 CAS 만을 이용해 삽입한다. 그 외의 업데이트(삽입, 삭제 및 교체)는 lock(synchronized) 을 이용하지만 각 버킷의 첫 번째 노드를 기준으로 부분적인 잠금을 획득하여 스레드 경합을 최소화 하고 안전한 업데이트를 한다.

getOrDefault : key 값이 없다면 입력시 설정한 default 값을 반환
putIfAbsent : map에 key가 없으면 key, value를 넣고 map에 key가 있으면 건너뛴다.