전체 Collections의 구조는 다음과 같습니다.

 

List

  • 순서가 있는 데이터를 처리하기 위한 자료구조입니다.
  • 인덱스로 위치를 지정하여 값을 처리할 수 있습니다.
  • 중복을 허용한다는 성질이 있습니다.

그 전에, 자바엔 Vector라는 자료구조가 리스트에 있는데, 왜 사용되지 않는걸까요?

Vector의 문제점

  • Vector의 문제점은 모든 작업이 Synchronized 되어있다는 점입니다.
  • Vector 인스턴스가 동기화되는 것이 아니라 작업이 동기화되는 것이기 때문에 동시성을 보장하지 않습니다.
  • 한 쓰레드가 Vector을 for문으로 반복하고, 다른 쓰레드가 Vector의 데이터를 수정한다면 ConcurrentModificationException 예외가 발생합니다.
  • 즉, 서로 다른 두 작업이 동시에 수행될 수 있는 문제가 있습니다. 동시에 수행될 수 있다면 차라리 ArrayList를 쓰거나 Collections.synchronizedList() 메서드로 감싸주는 것이 더 좋습니다.
    • Collections.synchronizedList()는 각 메소드에서 mutex로 동기화를 처리하여 한 메서드가 실행중일 때 다른 메서드가 접근할 수 없습니다.

1. ArrayList

  • 데이터를 배열에 저장합니다.
  • 리스트가 꽉 차게 되면 배열을 늘려줍니다.
    • 배열의 크기는 이전 배열 크기의 1.5배로 늘어납니다.
    • oldCapacity >> 1 ⇒ oldCapacity * 0.5
    private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}
  • 따로 동시성이 처리되지는 않습니다.

2. LinkedList

  • List 뿐만 아니라 Queue를 구현합니다.
  • add() 메서드 호출시 마지막 노드에 추가 노드를 삽입한다.
    • 노드의 경우는, 양방향 노드입니다. prev, next를 저장합니다.
    public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

get() 메서드 호출시 ArrayList의 경우는 배열의 index로 접근하지만, LinkedList의 경우는 첫번째에서부터 n번 이동하여 데이터를 가져옵니다. 이로 인해 조회 속도가 ArrayList에 비해선 느릴 수 있습니다.

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

참고로, LinkedList는 동시성에 대해선 따로 처리되지 않습니다.

 

Set

  • 중복이 없는 집합 객체를 만들 때 유용합니다.
  • 순서가 없어서 인덱스로 위치를 지정하여 값을 처리할 수 없습니다.

1. HashSet

  • 내부적으로 HashMap을 가지고 있습니다.
  • 데이터를 추가할 때 HashMap의 put() 메서드를 사용합니다.
    • PRESENT는 빈 Object입니다. (더미 값)
    private transient HashMap<E,Object> map;

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
  • 값을 가지고 있는지 유무 체크 또한 Map의 메서드를 사용합니다.
  • public boolean contains(Object o) { return map.containsKey(o); }

2. TreeSet

  • 내부적으로 NavigableMap을 가지고 있습니다. 기본으로 사용하는 구현체는 TreeMap입니다.
  • 데이터를 추가하거나 데이터에 값을 가지고 있는지 유무는 HashSet과 마찬가지로 Map의 메서드를 사용합니다.
  • TreeMap의 성질로 인해 데이터가 정렬되어 있습니다. 이로 인해 compareTo 메서드를 잘 재정의 해두어야 합니다.
    • Key를 기준으로 오름차순, 내림차순으로 정렬된 Map입니다.
  • NavigableMap

3. LinkedHashSet

  • 값이 들어간 순서대로 출력 가능합니다.

 

Map

  • 키-값 형태의 데이터를 저장합니다.

1. HashMap

해시를 기준으로 키-값을 저장합니다. 데이터 저장 로직인 putVal() 메서드의 코드를 하나하나 분석해 보겠습니다.

Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

초기 테이블 설정이 되어있지 않은 경우 테이블을 설정합니다. resize() 메서드는 테이블 크기를 초기화하거나 2배로 재조정하며 초기 테이블이 설정되어 있지 않은 경우 입력된 초기 크기로 설정하거나 초기값을 16으로 설정합니다.

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }

기존에 동일한 해시값으로 데이터가 들어오지 않았다면 newNode() 메서드로 새로운 노드를 만들어서 넣어줍니다. 존재한다면 두 분기점이 존재합니다. equals()와 hashcode가 모두 같은 경우는 같은 데이터가 들어온 것으로 간주합니다. 타입이 TreeNode인 경우는 테이블이 아닌 트리구조인 형태이며, TreeNode가 아닌 경우, 체이닝으로 되어있으므로 다음 링크로 이동해 나가면서 같은 데이터가 있는지 찾고, 없다면 맨 뒤에 데이터를 넣어줍니다.

 

단, 여기서 TREEIFY_THRESHOLD - 1 이상인 경우 테이블 구조에서 트리구조로 변경합니다. TREEIFY_THRESHOLD는 8이므로, 동일한 해쉬값인 데이터가 8개 들어오는 순간 트리구조로 변환할 것 같지만, 그렇지 않습니다.

final void treeifyBin(Node<K,V>[] tab, int hash) {
	  int n, index; Node<K,V> e;
	  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
	      resize();
	  else if ((e = tab[index = (n - 1) & hash]) != null) {
	      TreeNode<K,V> hd = null, tl = null;
	      do {
	          TreeNode<K,V> p = replacementTreeNode(e, null);
	          if (tl == null)
	              hd = p;
	          else {
	              p.prev = tl;
	              tl.next = p;
	          }
	          tl = p;
	      } while ((e = e.next) != null);
	      if ((tab[index] = hd) != null)
	          hd.treeify(tab);
	  }
}

사실상, 테이블의 크기가 MIN_TREEIFY_CAPACITY(64) 아래인 경우에는 resize() 메서드를 호출하여 테이블의 크기를 늘려주기만 하고, 기존에 있는 데이터를 다시 테이블에 넣어주기만 합니다. 크기가 64 이상인 경우에만 트리구조로 변경시켜 줍니다. 왜 이런 구조가 되었을까요?

 

왜냐하면 트리를 사용하는건 최대한 뒤로 미루어야 하기 때문입니다. 해시 테이블의 경우는 이론상 O(1)의 시간이 걸리나, 트리를 사용한 탐색의 경우 O(log n)의 시간이 걸리기 때문입니다. 일반적으로 작은 테이블 크기의 경우 확장을 통해 해시 충돌을 해결할 가능성이 높습니다.

 

그렇다면 왜 트리를 사용하게 될까요? 이 부분은 개인적인 생각입니다. 해시 충돌이 잦은 경우를 생각해 봅시다. 충분하게 테이블 크기를 늘렸음에도 불구하고 해시 충돌이 매우 잦게 일어나게 되면 테이블에 데이터가 균일하게 들어가지 않고, 하나의 버킷에 데이터가 몰리는 현상이 일어나게 됩니다. 이러한 경우 결국 해시 테이블을 사용했지만 검색 속도가 O(n)에 가깝게 될겁니다. 따라서 트리를 사용하게 되면 O(log n)의 시간이 걸리니 오히려 트리가 더 빠르게 동작할 수도 있을 것 같습니다.

if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

마지막으로, 이미 존재한 경우에 대해서 처리하고 저장된 데이터의 수가 임계치보다 커진다면 크기를 더 확장시켜 줍니다.

 

2. TreeMap

  • 정렬된 키값 순으로 데이터가 조회됩니다.
  • Red-Black Tree를 사용합니다. 적절한 위치에 데이터를 삽입한 다음 Red-Black 후처리를 진행합니다. Red-Black Tree에 대해선 추후에 다시 다룰 예정입니다.
private void fixAfterInsertion(Entry<K,V>x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
x= parentOf(parentOf(x));
            } else {
                if (x== rightOf(parentOf(x))) {
x= parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
x= parentOf(parentOf(x));
            } else {
                if (x== leftOf(parentOf(x))) {
x= parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}
  • 자세한건 Red-Black Tree를 검색해봅시다.

 

3. LinkedHashMap

  • 값이 들어간 순서대로 데이터가 저장됩니다.
  • 내부에 Head, Tail을 따로 두어 Map이 변경될때마다 같이 조절하여 저장 순서를 유지합니다. 구현 로직은 HashMap의 메서드들을확장해서 사용합니다.

put 메서드 기준으로 살펴보겠습니다. HashMap의 putVal메서드에서 사용하는 newNode 메서드를 재정의해서 사용합니다.

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
		LinkedHashMap.Entry<K,V> p =
		    new LinkedHashMap.Entry<>(hash, key, value, e);
		linkNodeLast(p);
		return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

 

linkNodeLast(p)라는 메서드가 살짝 낀걸 볼 수 있습니다. 이 친구는 무엇을 하는 역할일까요? Tail의 링크에 p를 연결시켜주고 Tail을 p로 설정해주는걸 알 수 있습니다. 따라서 Head에서 시작해서 링크를 따라 Tail로 이동하면 데이터를 넣은 순서대로 조회가 가능합니다.

다음은 LinkedkeySet의 forEach 메서드의 구현 코드입니다.

public final void forEach(Consumer<? super K> action) {
    if (action == null)
        throw new NullPointerException();
    int mc = modCount;
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        action.accept(e.key);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

 

실제로 head에서 시작해서 null이 될 때 까지(tail의 after은 null입니다.) 이동하면서 action을 실행시켜 주는걸 볼 수 있습니다.

 

참고

 

Collections Framework Overview

Collections Framework Overview Introduction The Java platform includes a collections framework. A collection is an object that represents a group of objects (such as the classic Vector class). A collections framework is a unified architecture for represent

docs.oracle.com

 

'Language > Java' 카테고리의 다른 글

동시성 테스트와 CountdownLatch  (0) 2022.12.08
Java의 동시성 제어  (0) 2022.11.10
Final 키워드만 써도 성능 향상이 된다고?  (2) 2022.10.31
JVM의 동작원리  (0) 2022.10.22
lambda 예외 핸들링  (0) 2022.10.02

+ Recent posts

티스토리툴바