Java Collections Framework

Java에서 제공하는 Generic한 자료구조 프레임워크

List

public interface List<E> extends Collection<E> { ... }

대표적인 선형 자료구조

• 순서가 있는 데이터를 이용할 수 있도록 만들어진 인터페이스
• 배열 + 동적 크기 할당

ArrayList

public class ArrayList<E> 
	extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ... }

• Object[] 배열을 사용
• 흔히 사용하는 원시 타입 배열 Object[] arr = new Object[10];과 유사한 형태이다.
• 요소 접근( 검색 )에서는 탁월한 성능을 보인다.
• 중간의 요소가 삽입, 삭제가 일어나는 경우 한 칸씩 밀거나 당겨야 해서 비효율적이다.

LinkedList

public class LinkedList<E>
  extends AbstractSequentialList<E>
  implements List<E>, Deque<E>, Cloneable, java.io.Serializable { ... }

• 데이터와 주소로 이루어진 객체(Node)를 만들어 서로 연결하는 방식
• 이중 연결 리스트로 구현되어 있다.
• 검색시 처음 노드부터 찾아야 해서 오래 걸린다. ( 비효율적이다. )
• 중간의 요슬 삽입, 삭제할 경우 해당 노드를 연결하거나 끊는 과정만 해주면 되기 때문에 효율적이다.

Vector

public class Vector<E>
  extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ... }

• 기본적으로 ArrayList와 거의 같다.
• Collection Framework가 도입되기 전부터 지원하던 클래스였다.
• 항상 동기화( synchronized )를 지원한다.
  • 여러 쓰레드가 동시에 데이터에 접근하면 순차적으로 처리한다.
  • 멀티 쓰레드 환경에서는 안전하지만, 단일 쓰레드에서도 동기화를 처리해 약간 느리다.

Stack

public class Stack<E> extends Vector<E> { ... }

• Vector를 상속받은 클래스이다.
• LIFO( Last In First Out ) 후입선출 자료형이다.

Queue

public interface Queue<E> extends Collection<E> { ... }

• FIFO( First In First Out ) 선입선출 자료형이다.
• 단방향 삽입 삭제가 가능하다.

Deque ( Double Ended Queue )

public interface Deque<E> extends Queue<E> { ... }

• Queue를 상속받는 Interface다.
• 양방향 삽입 삭제가 가능하다.
• 비슷한 자료구조로는 Deck이 있다.

LinkedList

public class LinkedList<E> 
	extends AbstractSequentialList<E>
	implements List<E>, Deque<E>, Cloneable, java.io.Serializable { ... }

• List, Deque, Queue 3가지 용도로 사용할 수 있다.
• Deque또는 Queue를 LinkedList 처럼 Node 객체로 연결해서 관리하길 원하면 사용한다.
• 일반적인 큐를 사용하고 싶다면 LinkedList로 생성하여 Queue로 선언하면 된다.
  • Queue<T> queue = new LinkedList<>();
• Deque도 마찬가지다.
  • Deque<T> deque = new LinkedList<>();

ArrayDeque

public class ArrayDeque<E> 
	extends AbstratCollection<E>
	implements Deque<E>, Cloneable, Serializable { ... }

• ArrayList와 비슷하게 Object[]을 사용한다.
• Stack 구조로 사용하면 Stack Class보다 빠르고,
  Queue 구조로 사용하면 Queue Class보다 빠르다.
• 싱글 쓰레드 환경에서 Vector를 상속한 Stack Class보다 더 빠른 Stack을 구현할 수 있다.
  • Vector는 항상 동기화를 하기 때문에 Thread-Safe 하지만, 싱글 쓰레드 환경에선 느리다.
  • ArrayDeque를 활용하여 Stack을 구현하면 싱글 쓰레드 환경에서 보다 빠르다.

PriorityQueue

public class PriorityQueue<E> 
	extends AbstractQueue<E>
  implements java.io.Serializable { ... }

우선순위 큐

• 데이터 우선순위에 기반하여 우선순위가 높은 데이터가 먼저 나오는 Queue이다.
• 따로 정렬박식을 지정하지 않는다면 낮은 숫자가 높은 우선순위를 갖는다.
• 주어진 데이터들 중 최댓값, 혹은 최솟값을 꺼내올 때 매우 유용하게 사용할 수 있다.
• 사용자가 정의한 객체를 타입으로 쓸 경우 반드시 Comparator 또는 Comparable을 통해 정렬 방식을 구현해주어야 한다.

Set

public interface Set<E> extends Collection<E> { ... }

• 데이터를 중복해서 저장할 수 없다.
• 입력 순서대로의 저장 순서를 보장하지 않는다.

HashSet

public class HashSet<E>
  extends AbstractSet<E>
  implements Set<E>, Cloneable, java.io.Serializable { ... }

• 가장 기본적인 Set 컬렉션의 클래스
• 삽입, 삭제, 검색이 매우 빠르다.
  • Hash 알고리즘을 사용하여 검색 속도가 빠르다.
• 중복된 데이터 인지 가장 빠르게 알 수 있다.
  • add() 메서드를 사용하여 삽입을 시도할 경우, 중복된 데이터는 false를 반환한다.

LinkedHashSet

public class LinkedHashSet<E>
  extends HashSet<E>
  implements Set<E>, Cloneable, java.io.Serializable { ... }

• 중복은 허용하지 않지만 입력 순서대로의 저장 순서를 보장한다.
• LinkedList처럼 Node 객체를 사용하여 데이터를 저장한다.

TreeSet

public class TreeSet<E> 
  extends AbstractSet<E>
  implements NavigableSet<E>, Cloneable, java.io.Serializable { ... }

• SortedSet<E>를 상속한 NavigableSet<E>를 상속받는다.
• 이진 트리 구조( 정확히는 Red-Black Tree )를 띄고 있어서 특정 규칙에 의해 정렬된 형태의 집합을 사용하고 싶을때 사용한다.
• Compartor을 구현하여 정렬 방법을 지정할 수 있다.

Map

public interface Map<K, V> { ... }

• Key - Value로 이루어진 자료구조다.
• Set과 같이 순서를 보장하지 않는다.
• Key 값은 중복될 수 없지만, Value는 중복 될 수 있다.

HashMap

public class HashMap<K,V>
  extends AbstractMap<K,V>
  implements Map<K,V>, Cloneable, Serializable { ... }

• Entry<K, V>의 배열로 저장되며, 배열의 index는 내부 해쉬 함수를 통해 계산된다.
• 내부 Hash 값에 따라서 키 순서가 정해진다.
• Key와 Value에 null값을 허용한다.
• 비동기로 처리한다.

LinkedHashMap

public class LinkedHashMap<K,V>
  extends HashMap<K,V>
  implements Map<K,V> { ... }

• HashMap을 상속받으며, LinkedList로 저장된다.
• 입력 순서대로의 저장 순서를 보장한다.
• 비동기로 처리한다.

TreeMap

public class TreeMap<K,V>
  extends AbstractMap<K,V>
  implements NavigableMap<K,V>, Cloneable, java.io.Serializable { ... }

• 내부적으로 레드-블랙 트리( Red-Black Tree )로 저장된다.
• 키값이 기본적으로 오름차순으로 정렬되어 출력된다.
• 키값에 대한 Comparator를 구현하여 정렬 방법을 지정할 수 있다.

ConCurrentHashMap

public class ConcurrentHashMap<K,V> 
  extends AbstractMap<K,V>
  implements ConcurrentMap<K,V>, Serializable { ... }

• Multiple Lock
• Update 할 때만 동기적으로 처리한다.
  • 멀티 쓰레드 환경에서 동시성이 보장된다.
• Key와 Value에 null을 허용하지 않는다.

HashTable

public class Hashtable<K,V>
  extends Dictionary<K,V>
  implements Map<K,V>, Cloneable, java.io.Serializable { ... }

• Single Lock
• 모든 메서드를 동기적으로 처리한다.
  • JCF가 나오기 전에 만들어진 레거시 클래스로, 대부분의 메서드에 동기화가 걸려있다.
• Key와 Value에 null을 허용하지 않는다.

참고

Comparable Interface

public interface Comparable<T> {
  public int compareTo(T o);
}

• 정렬 수행 시 기본적으로 적용되는 정렬 기준이 되는 메서드를 정의하는 인터페이스
• Java에서 제공되는 정렬이 가능한 클래스들은 모두 Comparable 인터페이스를 구현한다.
  • public final class Integer extends Number implements Comparable<Integer> { ... }
• 구현 방법
  • 객체에 Comparable Interface를 상속받은 후, compareTo() 메서드를 오버라이드하여 구현
  • compareTo() 메서드 작성법
    • if( this < other ) { return -1; }
    • if( this == other ) { return 0; }
    • if( this > other ) { return 1; }
    • 음수 또는 0이면 객체의 자리가 그대로 유지되며, 양수인 경우 자리가 교체된다.
• 사용 방법
  • 배열 정렬의 경우: Arrays.sort(array);
  • List 정렬의 경우: Collections.sort(list);

Comparator Interface

@FunctionalInterface
public interface Comparator<T> { 
	int compare(T o1, T o2);
	boolean equals(Object obj);
}

Comparator<Point> myComparator = new Comparator<Point>() {
  @Override
  public int compare(Point p1, Point p2) { 
    if (p1.x > p2.x) {
      return 1; // x에 대해서는 오름차순
    }
    else if (p1.x == p2.x) {
      if (p1.y < p2.y) { // y에 대해서는 내림차순
        return 1;
      }
    }
    return -1;
  }
};

List<Point> pointList = new ArrayList<>();
pointList.add(new Point(x, y));
Collections.sort(pointList, myComparator);

• 정렬 가능한 클래스들의 기본 정렬 기준과 다르게 정렬하고 싶을 때 사용
• 주로 익명 클래스로 사용된다.
• 구현 방법
  • Comparator Interface를 상속받은후 compare() 메서드를 오버라이드하여 구현
  • compare() 메서드 작성법
    • if( p1 < p2 ) { return -1; }
    • if( p1 == p2 ) { return 0; }
    • if( p1 > p2 ) { return 1; }
    • 음수 또는 0이면 객체의 자리가 그대로 유지되며, 양수인 경우 자리가 교체된다.
    • Integer.compare(x, y) 와 동일한 개념이다.
• 사용 방법
  • Arrays.sort(array, myComparator);
  • Collections.sort(list, myComparator);
  • 두 번째 인자로 Comparator Interface를 받을 수 있다.
    • 우선 순위 큐( PriorityQueue ) 생성자의 두 번째 인자로 받을 수 있다.
    • PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

Red-Black Tree?

알고리즘 ) Red-Black Tree

일종의 자기 균형 이진 탐색 트리

• 삽입, 삭제 동안 트리의 모양이 균형 잡히도록 각 노드들은 Red or Black 색상을 가진다.
• 검색, 삽입, 삭제 시 Worst Case 모두 O(logN)이 보장된다.
  • 기존의 이진 탐색 트리는 균형이 무너질 경우 O(lonN)에서 O(N)까지 시간이 증가될 수 있다.

Single Lock? Multiple Lock?

검색해서 나오지 않는다…. 누군가 알려주면 감사합니다…

출저

• JAVA - 기술 면접 질문
• 자바 [JAVA] - 자바 컬렉션 프레임워크 (Java Collections Framework)
• 자바 HashMap vs Hashtable 차이점, 예제
• 알고리즘 ) Red-Black Tree
• [Java] Comparable와 Comparator의 차이와 사용법 - Heee's Development Blog