[Java] Collection

 이 글에서는 java의 collection에 대해 알아볼 것이다.

 

Collection

 Collection은 object group을 나타내는 object이다. 편하게 data sturcture 집합이라고 이해하면 된다.

java collection hierarchy

 Java collection에는 위와 같은 많은 interface와 class가 있는데, 이들에 대해 알아볼 것이다.

 

List

 순서가 있으며, 데이터 중복이 허용된다. 

 

ArrayList

• index를 가지고 있어 조회 시 성능이 빠르다. O(1)이다.
• erase나 insert 시 해당 위치 앞/뒤에 있는 모든 element 위치를 조정해야 하므로 O(n)이다. 따라서 삽입/삭제 성능이 느리다.
• thread-safe하지 않다.
• object array로 구현되어 있다.

 

LinkedList

• 조회 시 앞에서부터 탐색하기 때문에 느리다. O(n)이다.
• erase나 insert 시 O(1)이다.
• thread-safe하지 않다.
• doubly linked list로 구현되어 있다.

 

Vector

• ArrayList와 동일하다.
• 조회 시 O(1), erase/insert 시 O(n)이다.
• synchronized method로 구성되어 있으며 thread-safe이다.

 

Stack

• First-In, Last-Out의 data sturcture이다.
• pop/push 시 제일 마지막에 있는 element만 조정되기 때문에 O(1)이다.
• Vector를 extend했기 때문에 thread-safe이다.

 

 

Queue

First-In, First-Out의 data structure이다.

 

PriorityQueue

• heap이다.
  
  • 따라서 pop에 O(1), insert에 O(logn)이다.
• priority가 제일 높은 것이 front에 오는 queue이다.
• thread-safe하지 않다.

 

ArrayDeque

• thread-safe하지 않다.
• insert, erase에 average O(1)이다.
  • 앞이나 뒤에 element를 추가해 memory가 부족할 경우 다른 memory로 옮긴다. 이 크기는 O(n)이지만 평균적으로 O(1)이 된다.

 

 

 

Set

데이터 중복을 허용하지 않는다. 따라서 null이 저장되는 경우 1개만 저장된다. 데이터가 저장된 순서와 출력된 순서가 다를 수 있다.

 

HashSet

• 데이터 중복을 허용하지 않는다.
• 순서가 없다.
• insert, erase, search 시 O(1)이다. next()는 O(h/n)이다.
• thread-safe하지 않다.

 

 위 그림은 Java Class 포스팅에서 사용했던 object의 같음 유무를 판단하는 로직이다. HashSet은 hashCode() method를 호출해 object의 equality를 판단한다.

• hashCode() 값이 다름 : 다른 object -> 저장함
• hashCode() 값이 같음 then
  • equals() 값이 다름 : 다른 object -> 저장함
  • equals() 같이 같음 : 같은 object -> 저장하지 않음

 

LinkedHashSet

• 순서가 있다. (들어온 순서대로 저장된다)
• insert, erase, search 시 O(1)이다. next()는 O(1)이다.
• thread-safe하지 않다.

 

TreeSet

• 순서가 없다.
• 정렬되어 있다.
• null을 허용하지 않는다.
• red-black tree로 구현되어 있다.
• insert, erase, search 시 O(logn)이다.
• thread-safe하지 않다.

 

 

 

Map

 <key, value>로 구성된 Entry Object를 저장한다.. key를 기준으로 값을 조회/삽입/삭제하기 때문에 key는 중복되지 않는다.

 

HashMap

 HashSet과 동일하게 hashCode() method와 equals() method를 이용해 Entry object의 equality를 판단한다.

• insert, erase, search 시 O(1)이다. next()는 O(h/n)이다.
• thread-safe하지 않다.

 

LinkedHashMap

• LinkedHashSet과 유사하다. next()는 O(1)이다.
• 순서가 있다. (들어온 순서대로 저장된다)
• insert, erase, search 시 O(1)이다.
• thread-safe하지 않다.

 

IdentityHashMap

• HashMap과 동일하지만 ==만을 이용해 key를 비교한다.
• insert, erase, search 시 O(1)이다.
• thread-safe하지 않다.

 

WeakHashMap

• HashMap과 동일하지만 key에 해당하는 object가 더 이상 사용되지 않는다면 erase하고 GC해버린다.
• insert, erase, search 시 O(1)이다.
• thread-safe하지 않다.

 

Hashtable

• insert, erase, search 시 O(1)이다.
• thread-safe하다.

 

Property

• insert, erase, search 시 O(1)이다.
• Hashtable을 extend했지만 Entry object의 key와 value를 string으로만 지정가능하다.
• Hashtable을 extend했기 때문에 thread-safe하다.

 

TreeMap

• TreeSet과 유사하게 key값으로 정렬되어 있다.
• red-black tree로 구현되어 있다.
• insert, erase, search 시 O(logn)이다.
• thread-safe하지 않다.

 

 

 

정리

	class 이름	중복 허용 여부	순서 여부	정렬 여부	thread-safe 여부	구현 방법
List	ArrayList	O	O	X	X	array
	LinkedList	O	O	X	X	doubly linked list
	Vector	O	O	X	O	array
	Stack	O	O	X	O	vector(array)
Queue	PriorityQueue	O	X	O	X	heap
	ArrayDeque	O	O	X	X	array
Set	HashSet	X	X	X	X	hash
	LinkedHashSet	X	O	X	X	doubly linked list + hash
	TreeSet	X	X	O	X	red-black tree
Map	HashMap	X	X	X	X	hash
	LinkedHashMap	X	O	X	X	doubly linked list + hash
	IdentityHashMap	X	X	X	X	hash
	WeakHashMap	X	X	X	X	hash
	Hashtable	X	X	X	O	hash
	Property	X	X	X	O	hash
	TreeMap	X	X	O	X	red-black tree

 

 시간 복잡도의 경우

• linked list를 쓰는 경우 삽입/삭제에 O(1), next에 O(1)이다.
• hash를 쓰는 경우 삽입/삭제에 O(1), next에 O(h/n)이다.
• tree를 쓰는 경우 삽입/삭제/조회에 O(logn)이다.
• array를 쓰는 경우 조회에 O(1), 삽입/삭제에 O(n)이다.
  • stack의 경우 last에만 삽입/삭제하므로 O(1)이다.

 

 

thread-safe하게 바꾸기

 Vector, Stack, Hashtable, Property는 thread-safe고, 나머지는 모두 thread-safe하지 않다. 그러나 ArrayList, HashSet, HashMap 등을 multi-thread에서 사용해야 할 수도 있다. 이 경우에는 모든 method를 synchronized method로 wrapping한  후 리턴하는 synchronizedList(), synchronizedMap(), synchronizedSet() method를 사용해 thread-safe하게 만들 수 있다.

 

concurrent collection

 바로 위에서 작성한 synchronized collection은 thread-safe이지만 병렬 처리를 못하기 때문에 느리다. ConcurrentHashMap, ConcurrentLinkedQueue 등의 thread-safe이면서 parallel 처리를 해 주는 collection도 존재한다.