Dive Data Structure with Java Collection

BEOKS 2022. 3. 10. 16:12

2022. 3. 10. 16:12

Overview

이 장에서는 여러 Data Structure의 개념과 자바에서는 실제로 어떻게 구현되어 있는지 알아보도록 한다.

Linear Data Structure

Array

논리적 저장순서와 물리적 저장순서가 일치한다. 즉 메모리에서 연속적으로 데이터가 기록되는 자료구조이다. 이 특성 덕에, 특정 아이템을 인덱스를 알면 O(1)안에 접근이 가능하지만(random access), 아이템 삭제나 추가를 진행할 때, 연속성을 유지해야 하기 때문에 최대 O(n)의 시간복잡도가 발생한다.

보통 자바에서는 []를 통해서 Array를 생성하며, 아래와 같이 스택 영역에 Array의 레퍼런스를 저장하고 힙 영역의 메모리에 연속적으로 데이터를 할당하고 있다. 이 때, 메모리의 크기는 고정적이다. 또한 Array에서는 같은 클래스의 인스턴스를 가지도록 하며, 관련이 없는 클래스가 할당될 경우 IllegalArgumentException이 발생한다.

ArrayList in Java

위와 같이 []를 이용한 일반적인 Array는 선언과 동시에 배열의 크기가 정해진다. 따라서 만약 초기 선언된 크기보다 더 많은 데이터를 넣고 싶다면 문제가 발생한다. 이를 해결하기 위해서 Java에서는 배열의 크기를 변경할 수 있는 ArrayList 클래스가 존재한다.

ArrayList는 Array를 사용하며 만약 사용하던 Array의 capacity(용량)가 부족해지면 적절한 크기로 늘린 새로운 Array를 만들고 기존의 데이터를 복사한다. 다른 블로그에서는 대부분 2배로 Array를 늘린다고 되어 있지만, 실제로는 아래와 같이 ArraysSupport.newLength을 사용하여 최적화된 크기로 늘린다.

Tip : Vector vs ArrayList결론부터 말하자면 Vector는 synchronized되어 있으며, ArrayList는 asynchronized되어 있다. 즉, Vector는 하나의 스레드만 접근이 가능하며 ArrayList는 여러 스레드가 동시에 접근이 가능하다. synchronized되어 있다는 것은 이를 위한 코드가 추가적으로 작성되어 있다는 뜻이기에, 일반적으로 ArrayList가 더 빠른 성능을 가지고 있다. 따라서 Thread-safe한 환경에서는 ArrayList를 사용하고 그렇지 않은 환경에서는 Vector나 Collection.synchronizedList를 사용하는 것이 옳다.
자바에서 Vector클래스를 들어본적이 있는가? 아마 대부분 들어본적이 없을 것이다. Vector는 자바의 초창기에 지금의 ArrayList기능을 위한 레거시 클래스이다. 그러나 현재는 List 인터페이스를 구현하기 위해서 Collection 프레임워크에 맞게 재구성되어있기 때문에 사용할 수 있다. 그렇다면 Vector 와 ArrayList의 차이점은 무엇일까?

Linked List

Linked List의 경우 Array와 달리 메모리에 연속적으로 저장되지 않으며, 각 아이템은 자기 다음의 아이템의 위치만을 가지고 있는 구조이다. 이를 통해서 메모리에 연속적으로 저장하지 않아도 리스트의 요구사항을 만족할 수 있어 삽입과 삭제에 O(1)의 시간복잡도가 요구된다. 그러나 원하는 부분에서 삽입과 삭제를 진행하기 위한 search 과정에서 최악의 경우 O(n)의 시간복잡도가 발생할 수 있기 때문에, 전체적인 시간복잡도는 O(n)이 될 수 있다.

Doubly-Linked List in Java

Doubly-linked list implementation of the Listand Dequeinterfaces. Implements all optional list operations, and permits all elements (including null). All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index. [2]

자바에서 어떻게 구현되어 있는지 살펴보자. 자바에서 사용하는 LinkeList는 기본적으로 Doubly-LinkeList이다. 이는 하나의 원소가 자기 다음의 원소 주소만 저장하는 것이 아니라 반대로 자기 이전의 주소 또한 저장하는 것이다. 이렇게 사용하는 이유는 효율성을 위해서이다. 예를 들어, 찾고자 하는 원소의 인덱스가 리스트의 마지막에 가깝다면, 처음에 가까이 있는 원소보다 시간이 많이 소요될 것이다. 자바에서는 이런 불균형을 방지하기 위해서 마지막에서부터 원소를 탐색을 시작할 수 있도록 하기 위해서 Doubly-Linked List를 사용하고 있다.

Stack

선형 자료구조의 일종으로 마지막으로 삽입된 원소가 처음 나오는 구조(LIFO, Last In First Out)를 가지고 있다. 대표적으로 사용자가 어떤 액션을 취하고 되돌아가기 위해 ctrl+z를 누르는데 이 때, 사용자의 액션이 저장되는 자료구조가 스택이다. 또한, 프로그램에서 스택은 함수의 호출 구조를 저장하는데 사용된다. 예를 들어, 사용자의 정보를 다운로드 하는 함수가 아래와 같이 수행된다고 하자. 그럼 getUserInfo → parse → download 순으로 메서드가 호출되고 이 순서대로 스택에 호출 정보가 저장된다. 그리고 메서드 처리가 완료될때마다, download → parse → getUserInfo 순으로 값이 반환된다. 이렇듯, 스택은 마지막으로 처리한 과정부터 역으로 진행이 필요한 프로세스에 사용되는 기본적인 자료구조이다.

function getUserInfo(){
	return parse(donwload())
}

Stack in Java

자바에서는 Stack 클래스를 이용해서 stack 자료구조를 구현하고 있다. 그 특성은 위에서 말한 Stack의 특성과 동일하며 재미있는 점은 아래와 같이 Vector를 super 클래스로 삼고 있다. Vector는 synchronized ArrayList라고 생각하면 된다(자세한 내용은 위의 “Tip : Vector vs ArrayList”를 참고). 따라서 Stack 또한 하나의 스레드만 접근가능한 synchronized가 적용되어 있어 Thread-safe하다.

//Stack's super class
java.lang.Object
	java.util.AbstractCollection<E>
		java.util.AbstractList<E>
			java.util.Vector<E>
				java.util.Stack<E>

Queue

Stack은 LIFO 구조라고 하였다. 그렇다면 반대로 처음 삽입된 원소가 마지막으로 나오는 (FIFO, First In First Out)구조도 필요하지 않을까? 그럴 때 사용되는 것이 Queue이다. 큐는 CS에서 사용하는 세마포어, 버퍼링 등 다양한 프로세스를 구현하기 위해서 사용된다.

Queue in Java

Stack과 달리 자바에서는 Queue를 위한 클래스가 따로 존재하지 않는다. 대신, LinkedList, PrioirtyQueue 등 Queue 인터페이스가 구현된 다른 클래스를 적절히 선택하는 것을 권장하고 있다.

Queue<String> queue= new LinkedList<String>()
Queue<String> queue= new PrioirtyQueue<String>()

예를 들어, 일반적인 순서를 가지는 큐를 구현하고 싶으면 LinkedList를 구현하면 되고, 데이터를 삽입할 때마다 정렬되는 큐를 만들고 싶다면 PrioirtyQueue를 사용하면 된다. 이외 에도, AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, 등등, 다양한 클래스를 자신의 적절한 환경에 사용할 수 있다.

Tree

지금까지 다룬, Array,List, Stack, Queue는 데이터를 순서대로 표현할 수 있는 선형 자료구조다. 이와 달리 Tree는 나뭇가지가 뻗어 나가듯 데이터가 나뉘어지는 비선형 구조를 가지고 있다.

Binary Tree

이진 트리는 각각의 노드가 최대 2개의 자식노드를 가질 수 있는 재귀적인 자료구조이다. 이진트리는 깊이에 따라 레벨이 정해져 있다. 루트노드가 레벨 0이며 깊이가 내려갈 수록 레벨이 증가한다. 또한 최고레벨을 가르켜 해당 트리의 height라고 한다.

Perfect Binary Tree(포화 이진 트리)

모든 레벨이 채워져있는 이진 트리

Complete Binary Tree(완전 이진 트리)

트리의 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 채워져있는 트리이다. 여러 알고리즘에서 자주 사용되는 트리 구조

Full Binary Tree(정 이진 트리)

모든 노드가 0 또는 2개의 자식 노드만을 가지고 있는 트리이다.

Binary Tree in Java(Array vs Recursive Class)

자바에서는 이진 트리를 위한 특정한 클래스가 존재하지 않는다. 대신, 이진트리는 Array를 이용해서 간단하게 구현할 수 있다. 루트노드는 1번째 노드라고 규정하고 노드의 내용을 1번째 인덱스에 저장 했을 때, n번째 노드의 왼쪽 자식노드는 n2 인덱스에 저장하며 오른쪽 자신 노드는 n2+1 인덱스에 저장하도록 하면 Array에 이진트리의 정보를 저장할 수 있다.

아래와 같이 Array 이외에도 노드가 노드를 참조하는 재귀적인 클래스를 생성하여 이진트리를 구현할 수 있다.

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

이제 Array로 작성한 이진 트리와 클래스를 사용한 이진트리의 장단점을 구별해보자. 첫 번째로, 노드의 데이터를 가져올 때 Array는 인덱스를 통해서 상수시간내에 접근이 가능하지만, 클래스에서는 O(logn)의 검색시간이 발생한다. 따라서 삽입, 삭제, 업데이트 시에도 클래스로 구현한 이진트리에서 더 많은 시간이 소요된다. 두 번째로, 메모리 관점에서 바라볼때 클래스는 내용 이외에 자식노드의 인스턴스까지 참조해야 하기 때문에, Array에 비해서 많은 메모리가 필요하다. 그러나, 완전 이진트리가 아닌 이진트리의 경우 Array는 저장해야할 내용보다 많은 메모리가 필요하지만 클래스는 저장해야만 하는 노드를 구현하기 때문에 메모리를 절감할 수 있다.

Binary Search Tree

이진 트리를 사용해서 데이터를 검색하기 효율적인 자료구조를 만들 수 있다. 아래와 같은 규칙을 정렬된 데이터를 트리 형식으로 구현해보자.

규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

그리고 루트노드 부터 임의의 저장된 숫자를 검색한다고 했을 때, 마주치는 노드를 기준으로 왼쪽 자식노드로 검색할 지, 오른쪽 자식노드로 검색할 지 비교를 통해 결정할 수 있다. 트리가 완전 이진트리로 균형 잡혀 생성된 경우, 검색을 할 때마다, 비교해야 할 데이터가 절반씩 줄어들기 때문에 O(logN)=O(height)의 시간복잡도가 발생하여 큰 데이터 일 수록 매우 빠르게 검색할 수 있다.

그러나 만약 이진 탐색 트리가 왼쪽이나 오른쪽을 치우쳐 있을 경우, Worst Case 가 발생하며, 검색하는데 O(n)의 시간복잡도가 필요하다.

Red Black Tree

앞서 말했듯, 위와 같은 Binary Tree는 Worst Case의 경우 O(n)의 시간복잡도가 발생한다. 이런 경우를 대비하기 위해서 자료구조에는 Binary Tree가 균형잡인 트리로 유지하기 위한 Red Balck Tree가 존재한다. (구현하기 위한 알고리즘은 복잡하므로 생략한다.)

Red Balck Tree in Java

대표적으로 TreeMap이 Red Black Tree 구조를 사용하여 구현되어 있다. Map에서는 키의 유무 또는 위치를 검색하는게 중요한다. 이 때, 키를 저장하는 자료구조가 Red Black Tree이다.

Binary Heap

Complete Binary Tree 구조이며, 부모 노드의 값이 자식노드보다 항상 크다면 Max Heap, 부모 노드의 값이 자식노드보다 항상 작다면 Min Heap이라고 부른다. 이 자료구조는 저장된 데이터에서 최댓값이나 최솟값을 검색할 때 항상 O(1)의 시간복잡도를 보장하기에 최대,최소를 자주 찾는 프로세스에서 사용된다. 최대값을 pop할 경우 다시 저장된 데이터중 최댓값이나 최솟값이 루트노드에 존재해야 하기 때문에, heapify(맨 마지막 노드를 루트 노드에 대체시킨 후, 자식 노드와 비교하면서 데이터의 자리를 재위치 시키는 과정)를 진행하기에 O(logn)의 시간복잡도가 발생한다.

Binary Heap in Java

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

자바에서는 Heap을 구현하기 위해서 PriorityQueue 클래스를 사용한다. PriorityQueue는 Array를 이용해서 Complete Binary Tree를 구현하고 있으며, null을 포함한 non-Comparable한 데이터의 추가를 금지하고 있다. 또한, 동기성이 보장되고 있지 않아 여러 사용자가 동시에 접근하는 것은 안전하지 않으므로 이 경우, thread-safety가 보장된 PriorityBlockingQueue를 권장하고 있다.

Hash Table

Array에 데이터를 저장할 때 단순히 순서대로 저장하는 것이 아니라, 저장할 값을 기준으로 인덱스를 결정하여 저장하는 자료구조를 뜻한다. 이 때, 저장할 값을 기준으로 인덱스를 생성하는 방법을 hash method 또는 hash functiond이라고 하며 생성된 인덱스를 hashcode라고 한다. hash function이 좋지 못할 경우 서로 다른 값에서 동일한 인덱스가 생성될 수 있는데, 이 경우 동일한 인덱스에 여러개의 데이터가 존재할 수 있다. 이를 collision이라고 칭한다. hash function이 어떻게 작성되느냐에 따라, collision의 정도가 결정되는데, 항상 collision이 발생하지 않는것이 꼭 좋은 자료구조는 아니다. 오히려 적절한 collision이 발생하는 것이 좋은 성능의 Hash Table을 만들 수 있다.

HashTable in Java

자바에서는 HashTable을 사용할 때 기본적으로 키값과 저장할 내용, 두 가지를 입력한다. 키로 삽입되는 인스턴스는 Null이 아니며 hashCode()메서드가 구현되어 있어야 한다(HashMap은 Null값도 허용한다). 자바 개발자들은 Hashtable은 최근에 Java Collection에 포함된 대부분의 클래스와 달리 thread-safety가 보장되기 때문에 single programming에서 사용하는 경우 오버헤드가 발생하므로 thread-safety가 필요없는 경우 HashMap을 사용하는 것을 권장하고 있다. 또한 Hashtable은 레거시 클래스에 가깝기 때문에, thread-safety하고 고도의 동시성을 구현하기 위해서는 [ConcurrentHashMap](<https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html>) 을 사용하는 것을 권장하고 있다.[5]

Entry

이제 본격적인 구조에 대해서 알아보자. 해쉬 테이블의 데이터는 아래처럼 Entry 메서드에 저장된다. Entry는 Hashtable의 이너 클래스로, 이론적으론 하나의 버킷을 의미한다. [6]

private transient Entry<?,?>[] table;

내부 구조를 보면 알겠지만 LinkedList와 비슷한 구조를 가지고있다. 여기서 알 수 있는 점은, 같은 hashCode() 결과를 가져, 하나의 Entry에 포함된 원소들의 경우 검색하는데 선형적 시간복잡도가 걸린다는 것이다.

/**
 * Hashtable bucket collision list entry
 */
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
....

2. Put

이번엔 새로운 데이터를 추가하는 코드를 살펴보자. 우선 윈소의 값이 null인지 확인하고, 기존의 테이블의 길이와 hashCode()를 통해서 인덱스를 결정한다. 그리고 인덱스에 해당하는 엔트리를 가져와 링크드리스트를 탐색하듯 반복문을 진행하고 같은 키를 가지는 경우 기존의 원소값을 업데이트 한다. 같은 키가 없다면 addEntry를 통해서 새로운 값을 추가한다.

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

Hashtable에서는 loadFactor라는 값이 있는데 기존의 테이블을 얼마나 채우는 것을 허용하는지 결정하는 변수이다. 보통 메모리와 처리시간을 고려하여 0.75로 정해져 있다. threshold는 loadFactor값에 현재의 엔트리 용량을 곱한 결과로 지금 테이블 용량에서 최대로 채울수 있는 엔트리의 길이를 의미한다. 그래서 테이블에 새로운 값을 추가할 때, 테이블의 갯수가 threshold를 넘을 경우 rehash()메서드를 호출하여 테이블의 크기가 두 배인 변수를 만들어 기존의 값을 전부 복사한다. 여기서 배울 수 있는 점은, 만약 Hashtable의 크기를 처음에 결정할 수 있다면, rehash()메서드의 호출을 줄이기 위해서 처음부터 크기를 알맞게 할당해야 한다는 것이다. 그 다음 과정은 새로운 엔트리를 생성하여 값을 추가하는 것이다.

private void addEntry(int hash, K key, V value, int index) {
        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        modCount++;
    }

3. get

Hashtable에서 put을 이해했다면 get은 매우 간단하다. hashCode를 통해서 인덱스를 구한 후, 이에 해당하는 엔트리를 가져와 LinkedList를 검색하듯 get을 진행하고 만약 찾지 못했다면 null을 반환한다.

public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

HashMap vs Hashtable in Java

Java Docs를 포함한 대부분의 포스트에서는 HashMap과 Hashtable의 차이를 Thread-safety와 키, 원소의 Null 허용 여부에 두고 있다. 그러나 내부 구조에서는 매우 큰 차이가 존재하는데 바로 Resolve Conflict관점에서 Hashtable은 Seperate Chaining방식에서 Linked List만을 사용하지만 Tree와 Linked List를 공용으로 사용한다. Linked List는 탐색을 위해서 선형적 시간복잡도가 발생하는데 만약 하나의 버킷에 많은 양의 링크드 리스트가 존재한다면 탐색시간이 크게 늘어난다. 따라서 크기가 8이상의 버킷에 대해선 Red-Black-Tree방식으로 자료구조를 변경하여 탐색에 O(logN)의 시간복잡도를 제공하도록 한다.[7]

Graph

그래프는 정점(Vertex,Node)와 두 개의 정점을 잇는 간선(Edge)의 집합이다. Edge그래프는 Edge의 종류에 따라 Undirected Graph와 Directed graph로 나뉘게 되는데, Undirected의 경우 Edge에 방향이 없고, Directed의 경우 하나의 노드에서 다른 노드를 가르키는 방향성이 존재한다. 이 때, Undirected Graph에서 정점 간 연결된 Edge의 갯수를 Degree라고 하며 Directed Graph에서는 방향성에 따라 Outdegree, Indegree 두 가지로 나누어 갯수를 센다. 또한 만약 Edge에 가중치가 존재하는 경우 Weight Graph라고 칭한다.

그래프는 보통 이해관계를 표현할 때 주로 사용된다. 예를 들어 장소와 장소의 관계를 연결된 도로나 다리로 표현하거나 사람과 사람간의 채무 관계 등을 표시할 때 사용된다. 이런 이해관계를 그래프 자료구조로 저장함으로써 장소간 최단거리를 구하는 등의 알고리즘을 구현할 수 있다.

트리 또한 그래프의 종류 중 하나이며, 트리는 그래프와 달리 사이클이 생성되지 않는 특징을 가지고 있다.

Implementation

그래프를 구현하는 방법에는 크게 두 가지가 존재한다.

Adjacent Matrix

인접 매트릭스의 경우 정점의 갯수만큼의 행과 열을 가진 배열을 만들고 row,col을 정점의 번호로 가정했을 때, A와 B를 잇는 간선이 존재하는 경우 matirx[A][B]에 간선의 여부 및 가중치의 값을 기록하여 그래프를 구현하는 방법이다.

Adjacent List

인접 리스트의 경우, 정점의 갯수만큼 Array를 생성한 다음 각 원소에는 LinkedList를 구현하여 정점 A와 B가 이어져 있는 경우 matrix[A].push(B)를 통해서 간선의 유무, 방향성을 표시한다. 이 때 가중치 그래프인 경우 가르키는 정점과 함께 가중치 값을 삽입하기도 한다(matrix[A].push([B,W])).

Search

그래프는 비정형 데이터이므로 인덱스를 통한 순차적 검색을 지원하지 않는다. 대신, Recursive based Class Tree처럼 정점과의 관계인 간선을 하나씩 이어나가면서 데이터를 탐색하는 방법이 있다. 여기에는 크게 깊이를 우선으로 탐색하냐, 너비를 우선으로 탐색하냐에 탐색법이 나뉘게 된다.

DFS (Depth First Search)

DFS는 임의의 한 정점에서 다른 정점으로 나아가는 것을 반복하는 것이다. 예를 들자면, A 정점이 B,C와 연결되고 B 정점이 D,E와 연결된다면 A→B→D 순서로 연결된 간선 중 순서가 빠른 간선으로 계속 전진하는 것이다. 만약 더 이상 전진할 간선이 없다면 이전의 정점으로 돌아가 남아있는 간선으로 탐색을 다시 진행한다. 이 구조는 Stack을 이용한 미로찾기와 같은 구조인데, 역시 DFS에서는 Stack을 이용하여 이를 구현하다.

BFS(Breath First Search)

BFS는 너비 우선 탐색으로, 주위에 있는 간선을 먼저 탐색하는 것이다. 위와 같은 예를 들때, BFS로 탐색하면 A→B→C→D→E 순서로 탐색하게 된다. 주위에 있는 정점을 모두 탐색했을 때, 이 후 탐색한 순서대로 또 다시 해당 정점에서 주위 탐색을 진행한다. “먼저 탐색한 정점이 또 먼저 탐색을 시작”하므로 FIFO 형태의 자료구조가 필요하므로 BFS에서는 Queue를 사용한다.

Reference

저작자표시

'Computer Science > Data Structure' 카테고리의 다른 글

2017 카카오페스티벌 예선 문제 1 - 카카오프렌즈 컬러링북 풀이 (0)	2020.01.18
자료구조1 - Selection Sort(선택정렬) & Bineary search(이진탐색) (0)	2020.01.18
자료구조 3 - Transposing Sparse Matrix ( 희소행렬 대칭이동) (0)	2020.01.18

그럼에도 불구하고