이 그림을 이제 하나씩 발전시키고자 한다.
Java collection API를 이해해두면 해결해야 하는 문제에서 정확한 해결책을 결정할 수 있다. 한번 시간내어 이를 정리해둘 필요가 있는데 중장기적으로 java의 모든 collection을 다뤄보려고 한다.
위의 다이어그램은 collection이라 하면 대표적인 자료구조들의 hierarchy를 그려본 것이다. 앞으로 이 그림에 다뤄야할 주제들이 추가되면서 그림이 더 풍성해지는 것을 목표로 한다.
처음엔 한번에 다 할 수 있을거라 생각했는데 다뤄야 하는 양이 많다보니 나누게 되었다.
용어 정리
Collection API를 설명하려면 extends 와 implements 를 구별해서 사용해야 한다.
영어로는 표현이 명확하지만 한글로 표현했을때 inheritance 라는 단어가 둘 다 사용되기 때문에 다소 명확하지 않을 수 있음으로 다음의 두 단어를 사용한다.
•
상속: 두 클래스, 두 인터페이스 간의 inheritance(상속)을 의미한다.
•
구현: 클래스와 인터페이스 간의 inheritance(상속)을 개발하는데 사용되는 키워드이다.
Collection
Collection interface in Java
Collection 에서 명시된 기능들
Collection은 interface이며, collection API의 root interface가 된다. (더 위에는 Iterable 이 있으며, 오로지 하나의 함수인 interator() 만 제공한다.)
이 API들은 Collection의 기능을 상속해야 한다.
처음 java를 공부했을 때 당연하단 듯이 사용했던 size() 도 이 collection에 포함된 것이다.
List, Queue, Set 3개의 component는 collection을 상속 받고 map은 collection 의 interface를 상속받지 않는다. (Map 은 collection이 아니라 그냥 Map 이다. 하지만 구현으로 넘어가면 연관이 없진 않다.)
List interface
•
Element가 순서로 정렬된 collection에 대한 interface 이다.
•
add(), remove(), get() 으로 대표되는 함수들이 있어 collection 에 저장, 삭제, index 기준으로 조회가 가능하다.
•
중복 저장이 가능하다.
•
List를 구현한 구현체는 대표적으로 ArrayList, vector, LinkedList 가 있다.
List의 자료구조 정의들
Set interface
내가 가장 좋아하는 자료구조이다. 데이터를 표현할 때 집합 개념으로 표현하면 오해의 소지를 줄일 수 있는데 그 집합 표현을 실현해준 자료구조이다.
•
가장 대표적인 특징으로 모든 element는 unique하다. (중복이 없다.)
•
순서를 유지하지 않는다.
◦
put() 의 순서와도 연관이 없다. 후에 HashMap 에 대해 깊히 다룰텐데 그때 왜 순서가 없는지 언급하겠다.
•
HashSet, LinkedHashSet, TreeSet 이 대표적인 규현체 이다.
SortedSet Interface
•
Iterator를 사용해 interate 할 수 있지만, index를 사용한 interate는 불가능하다.
•
TreeSet 이 sorted set을 구현하였다.
•
Java 1.6 부터 Collection → Set → SortedSet → NavigableSet 으로 중간에 NaviableSet 이 있다.
Queue interface
•
순서가 보장되어 element가 한 쪽에서 인입되면 반대 쪽에서 반환되는 FIFO 구조이다.
•
매우 의외지만 LinkedList 가 여기에 속해있다.
•
JDK에선 offer, add 가 insert를 담당한다.
◦
Queue에 용량(capacity)가 충분한지 확인하여 저장하는데, 용량이 부족하면 exception을 일으키느냐 아니냐의 차이이다.
◦
add 용량이 부족하면 IllegalStateException을 반환한다.
◦
offer 용량이 부족하면 저장이 안될뿐 exception을 반환하지 않는다.
•
poll 과 peek, remove 3개의 method가 FIFO의 out을 담당한다.
◦
remove 는 empty 인 상태에서 호출하면 NoSuchElementException 을 반환한다.
◦
poll 은 empty 상태일 때 null을 반환하고 객체가 있으면 반환 후 queue에서 삭제한다.
◦
peek 은 empty 상태일 때 null을 반환하고 head의 객체를 반환하지만 queue에서 삭제하지 않는다.
•
LinkedList, PriorityQueue, ArrayQueue, PriorityBlockingQueue, LinkedBlockingQueue 등이 여기 포함된다.
•
PriorityQueue 는 comparator 를 통해 순서가 결정된다.
Deque interface
•
Deque는 Double-ended queue를 표현한 것으로 deck 이라 발음한다.
•
Capacity의 제한을 둘 수도 있고, 두지 않을 수도 있다.
•
Deque에서 제공하는 API는 후에 자세히 다루고 아래 테이블로 이름만 언급한다.
First (head) | First (head) | Last (tail) | Last (tail) | |
throw exception | special value | throw exception | special value | |
저장 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
제거 | removeFirst() | pollFirst() | removeLast() | pollLast() |
값 읽기(삭제 없이) | getFirst() | peekFirst() | getLasT() | peekLast() |
Deque의 hierarchy, Deque 를 상속한다.
•
LinkedList와 ArrayDeque가 Deque 인터페이스를 구현했다.
Map interface
Map interface는 collection을 상속받은 것이 아니라 별도의 자료구조이다.
Key-value 쌍으로 저장하고 value의 위치는 key에 종속된다.
Map의 Hierarchy
HashMap, ConcurrentHashMap 같은 경우는 코드를 한줄 한줄 들여다 봤기 때문에 후에 매우 자세히 다룰 예정이다.
•
Key-value pair로 저장한다.
•
Key가 중복되는 경우는 없다.
•
HashSet은 HashMap 을 사용해 구현했다. value에 그냥 Object를 저장하는 방식으로 HashSet이 구현되어 있다.
•
HashMap, HashTable, LinkedHashMap(생성자 옵션을 사용하면 LRU 캐시로 사용할 수 있다), TreeMap 이 여기에 해당한다.
SortedMap interface
Map interface를 상속하여 natural order를 사용한 사례가 TreeMap 이다.
Key의 순서를 사용하면서 동시에 중복 없이 사용하고자 할때 사용했었다.
나의 사례로는 WGS84 좌표에서 중복을 제거할 때 사용했다. 왜냐하면 좌표의 순서도 중요하기 때문이다.
Collection interface에서 정의한 함수들
size()
int size();
Java
복사
size() 는 int를 반환한다. 따라서 범위를 넘어가면 overflow가 발생한다. 물론 overflow가 발생해도 이를 역추적하여 어떤 값인지 알아낼 수 있지만, int 범위 여부를 아는 것은 중요하다.
isEmpty()
boolean isEmpty();
Java
복사
Collection이 비어있다면 true, 아니면 false를 반환한다.
contains(o)
boolean contains(Object o);
Java
복사
매개변수로 주어진 element가 있다면 true를 반환한다.
하지만, 이에 대해서는 hashCode, equals에 대한 정확한 이해가 필요하다.
이 글에서 해당 내용을 다뤘지만, HashMap 에 대한 포스팅을 할 때 자세하게 다룰 예정이다.
iterator()
Iterator<E> iterator();
Java
복사
Iterator 객체를 반환한다. 순서를 보장하진 못한다. 물론 구현에 따라 예외는 있다.
toArray()
Object[] toArray();
Java
복사
이 함수의 좋은점은 array가 safe 하다. 보통 JDK에서 safe를 언급한다면 그건 thread와 연관이 있다.
즉, 원본에 상관 없이 새로 복사가 되기 때문에 배열안의 element를 수정해도 원본에 영향을 주지 않는다.
JDK 주석을 보면 iterator() 의 영향을 받는듯 하다. iterator에서 순서를 보장한다면 보장된 순서가 반영되어 collection에 저장된 모든 element의 배열을 반환한다.
Runtime에서 array가 object 이므로 type을 지정하고 싶다면 아래 method를 사용해야 한다.
toArray(T[] a)
<T> T[] toArray(T[] a);
Java
복사
•
매개변수로 데이터를 저장할 적당한 크기의 배열을 할당한다.
•
다른 기능은 위 함수를 계승하지만, 차이점은 반환 type을 compile time에 결정할 수 있다.
removeIf
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
Java
복사
Collection interface에 있는 default 함수를 하나 가져오고 싶은데 적당한 것이 이 함수인것 같다.
•
Predicate 로 명시한 조건이 만족되는 element를 찾아 제거한다.
•
제거가 되면 true, 조건에 만족하는 element가 없으면 false를 반환한다.
이후 함수들은 다뤄야 할 범위가 매우 많다고 판단하여 다음 시리즈에서 다룰 예정이다.
다뤄야 할 대상들
JDK의 중요한 자료구조를 모두 다룰 계획이다.
가장 깊게 그리고 먼저 다뤄야 할 대상은 HashMap, ArrayList, LinkedList, PriorityQueue 가 될 것이다.
경험상 이 자료구조 들을 이해하면 다른 자료구조들은 이해하기 쉬웠기 때문이다.
필자가 비트연산을 좋아하게 된 이유는 HashMap 의 구현 때문이다.
HashMap 때문에 kernel의 어셈블리까지 열어봤었다.
하지만, grow, modCount 등의 개념을 다루기 위해 가장 이해가 쉽고, 설명도 쉬운 ArrayList 를 다루고 그 다음에 HashMap 을 다루도록 하겠다.
자료 출처
JDK 11 주석 & 코드
