Java의 자료구조 Collection Framwork란?

Collection Framwork라는 것은

쉽게 말하면 자료 구조(Data Structure)와 알고리즘(Algorithm)을 구조화한 클래스로 여러 데이터를 쉽고 효과적으로 처리할 수 있도록 자바 인터페이스(Interface)를 구현한 형태로 작성된 클래스이다.
JAVA software를 배포하는 Oracle에서는 Collection Framwork의 구성 목록을 다음과 같이 정의하고 있다.

• 컬렉션 인터페이스(Collection interfaces)
• 범용 구현(General-purpose implementations)
• 레거시 구현(Legacy implementations)
• 특수 목적 구현(Special-purpose implementations)
• 동시 구현(Concurrent implementations)
• 래퍼 구현(Wrapper implementations)
• 편리한 구현(Convenience implementations)
• 추상적인 구현(Abstract implementations)
• 알고리즘(Algorithms)
• 인프라(Infrastructure)
• 배열 유틸리티(Array Utilities)

하지만 외워야할 정도의 것은 아니고 이런게 있다고 파악하고 넘어가면 될 것 같다.
그러면 이 Collection Framwork를 사용하며 생기는 이점은 무엇일까?
Oracle에서 제시하는 이점은 다음과 같다.

• 프로그래밍 노력 감소
• 프로그램 속도와 품질 향상
• 관련되지 않은 API 간의 상호 운용성을 허용한다.
• 새로운 API를 배우고 사용하기 위한 노력을 줄인다.
• 새 API를 설계하려는 노력을 줄인다.
• 소프트웨어 재사용을 촉진한다.

Oracle이 제시하는 이점에는 적혀있지 않지만 컬렉션 프레임워크를 사용해서 얻는 가장 큰 이점은 바로 크기가 고정적인 배열의 문제점을 해결할 수 있다는 것이다.
그리고 자바에서 편하게 사용하라고 만들어 둔 것을 굳이 사용하지 않고 어렵게 구현할 필요가 없다. 공식 홈페이지 내에서도 쓰라고 선전하고 있는 만큼 쓰는 것이 효율적이고 정신건강에 좋다. 그리고 신입 개발자 면접에서도 나오는 중요한 자바 기초이다.

Collection Framwork 구조와 제너릭

모든 컬렉션 프레임 워크는 제너릭(Generic) 기반으로 구현된 클래스이다. 컬렉션 프레임 워크를 사용할 때 그 안에 들어가는 자료의 타입을 미리 지정하지 않고 필요할 때 지정하는 방식을 사용할 수 있는데 이것이 제너릭을 구현했기때문에 가능하다.
제너릭이란 클래스 내부에서 지정하는 것이 아닌 외부에서 사용자에 의해 지정되는 것을 의미한다. 자바의 기본 배열은 특정 변수를 선언하고 그 변수 값만 저장할 수 있지만 제너릭은 하나의 참조 자료형이 아닌 여러 참조 자료형을 사용할 수 있게 해준다.

	// 기본 배열
    String[] strings = {"s", "t", "r", "i", "n", "g"};
    
    // Collection Framwork-List를 이용한 배열
    List<T> objects = new ArrayList<>();
    
    // String 타입 저장
    objects.add("string")
    
    // List에 클래스 저장
    Car car = new Car("기아", "k5");
    object.add(car);
    

다만, 제너릭은 오직 참조 타입만 사용이 가능하다. int와 같은 기본형 타입을 쓰기위해서는 Wrapper Class 타입으로 처리해줄 필요가 있다. int는 Integer, char는 Character 이런 식으로다.

Collection Framwork의 구조는 아래의 이미지와 같다.
구조상에 차이가 있는 Map은 따로 정의되어있고 Collection 인터페이스 아래에 Set, List, Queue의 세가지 인터페이스가 있고 다시 그 아래에 다수의 자식 클래스가 존재한다. 그중 실제 많이 쓰이는 것은 Set, List, Map이다.

List🧾

List는 객체를 일렬로 늘어놓은 구조를 가지며 객체를 인덱스로 관리하기 때문에 인덱스로 객체를 검색, 삭제할 수 있고 중복된 데이터를 저장할 수 있다.

ArrayList

크기가 가변적으로 변하는 선형리스트이다. 일반적인 배열과 같은 순차리스트이며 인덱스로 내부의 객체를 관리한다는점등이 유사하지만 한번 생성되면 크기가 변하지 않는 배열과는 달리 ArrayList는 객체들이 추가되어 저장 용량(capacity)을 초과하면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다는 특징을 가지고있다. 멀티스레드 환경을 고려하지 않아서 Thread safe하지 않다.

Vector

ArrayList와 동일한 내부구조를 가지고 있다. ArrayList와 마찬가지로 Vector내부에 값이 추가되면 자동으로 크기가 조절되며 그다음 객체들은 한 자리씩 뒤로 이동된다. 한 가지 차이점은 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없다. 하나의 스레드가 실행을 완료해야만 다른 스레드들이 실행할 수 있기 때문에 멀티 스레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있다.

• ArrayList와 비교했을 때
  스레드가 1개일때도 동기화를 하기 때문에 성능이 떨어진다. ArrayList보다 속도가 떨어지는 편이다.

Stack

'쌓다'라는 사전적 의미와 비슷하게 데이터를 하나씩 쌓는 느낌으로 먼저 들어간 자료가 나중에 나오는 LIFO(Last In First Out)의 구조이다. Vector 클래스를 확장한 하위 클래스이며 재귀적(Recursion) 함수를 호출 할 때 사용된다.

• Stack의 단점
  Stack의 내부를 보면 Vector에서 확장한 부분과 메소드에 synchronized 키워드가 붙어있다. 이것은 두 가지의 큰 단점을 야기한다.
  1) synchronized 키워드로 Thread-safe의 특징을 가질 수 있으나, 멀티스레드 환경이 아닐 때에도 lock을 거는 작업때문에 많은 오버헤드가 발생한다.
  2) Stack은 LIFO 구조를 이용해야 하는데 Vector 클래스를 확장했기 때문에 중간에 데이터의 삽입과 삭제가 가능하다.

Queue

Queue(큐)는 데이터를 일시적으로 쌓아두기 위한 자료구조이며 FIFO(First In First Out)의 형태를 가진다. FIFO의 형태로 인해 (1) 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행하고 (2) 다른 한 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행한다.
마구 입력이 되었으나 처리를 하지 못할 때 버퍼(큐)를 만들어 대기 시킨다.

	Queue<Integer> queue = new LinkedList<>();

자바에서 Queue를 선언할 때에는 LinkedList를 활용해서 생성해야 한다.

LinkedList

데이터를 담고 있는 노드가 노드간에 연결 방식인 포인터를 이용해 한 줄로 연결되어 있는 자료구조이다. 그래서 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없다. 하지만 인덱스가 없어서 특정 요소에 접근할 때에는 순차 탐색이 필요하므로 탐색속도가 떨어지는 단점이 있다.
또, 이 클래스는 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있다.

• ArrayList와 비교했을 때
  ArrayList에 비해 배열에서 자주 삽입, 삭제가 이루어지는 경우 용이하지만 검색이 비효율적이라서 느리다.

Set

List와는 다르게 객체(데이터)를 중복해서 저장할 수 없다. 그리고 데이터를 인덱스로 관리하지 않기때문에 저장 순서가 보장되지 않는다.
List와 다른 특징으로 데이터에 접근하기 위해서는 iterator() 메서드로 생성하고 데이터를 가져와야 한다.

HashSet

Set 인터페이스의 구현 클래스이다. 중복된 값을 허용하지 않지만 null을 값으로 허용한다. 그렇기때문에 중복검사를 할 수 있다.
HashSet의 중복 검사는 객체를 저장하기 전에 먼저 객체의 hashCode()메소드를 호출해서 해시 코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교하여 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교해 true가 나오면 동일 객체로 인식해 저장하지 않는다.

TreeSet

HashSet과 마찬가지로 Set 인터페이스를 구현한 클래스로 Set의 성질을 그대로 가지고 있다. 하지만 HashSet과는 다르게 이진 탐색 트리(BinarySearchTree)구조로 이루어져있어 추가와 삭제에는 시간이 조금 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조이다.
TreeSet은 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리(Red-Black Tree)로 구현되어 있다. 일반적인 이진탐색트리는 편향된 데이터가 들어 올 경우 한쪽으로 크게 치우쳐진 트리가 되어 비효율적인 퍼포먼스를 내는 단점이 있다. 이를 보완하기 위해 레드-블랙 트리는 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 균형을 맞추어 준다.

LinkedHashSet

HashSet과 동일한 구조이지만 반복자를 사용하면 요소가 삽입된 순서대로 반환되는 차이가 있다.
순서를 보장할 수 없는 단점을 보완하기 위해서 노드 클래스에 이전 노드를 가리키는 변수인 prev와 다음 노드를 가리키는 next 변수를 두고, LinkedList 클래스에서는 연결 된 노드들의 첫 번째 노드를 가리키는 head와 마지막 노드를 가리키는 tail 변수를 두어 노드들을 상호 연결을 해주듯 같은 원리로 구현기능을 추가한 것이다.

Map

Map은 키와 값을 하나의 쌍으로 저장하는 방식(key-value)을 사용한다. 주민등록번호로와 비슷하다고 할 수 있는데 이름(value)과 주민번호(key) 두 개의 쌍으로 이루어져 이름 없이 주민번호가 있을 수 없고 주민번호 없이 이름이 있을 수 없는 것과 같다. 그리고 이름은 중복이 가능하지만 주민번호는 중복이 있을 수 없는 것도 유사하다.
Map은 List와 달리 Index를 사용하지 않아서 저장 순서를 유지하지 않는 대신 특정 값을 찾을 때 key를 이용한다.
Map은 put() 메소드를 이용해서 데이터를 삽입하는데 이미 존재하는 Key값과 동일한 Key값을 put하면 새로운 Key값으로 갱신된다. 즉 새로운 Value 값을 갱신하게 된다.

HashMap

Map인터페이스에 속해있는 컬렉션으로 Null Key와 Null Value를 모두 허용한다. 객체의 해시코드를 이용해서 해시테이블을 탐색, 값을 가져오는 동작을 하는 것이 특징이다.
사용법이 거의 동일한 컬렉션으로 HashTable이 있다.

• HashTable과의 차이
  HashMap은 해시 코드를 이용해서 빠르지만 Thread-Safe하지 않은 성질을 가지고 있는 반면 HashTable은 Thread-Safe하다는 이점이 있다.
  그리고 HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 HashTable에 비해 해시 충돌(hash collision)이 덜 발생할 수 있어 상대으로 성능상 이점이 있다. 보조 해시 함수를 제외하더라도 HashTable 구현에는 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있다.

HashTable

HashMap 클래스와 같은 동작을 하는 클래스이다. 하지만 HashMap과는 다르게 동기화가 이루어지고 Null 입력이 불가능하다. 기존 코드와의 호환성을 위해서만 남아있기때문에 사용을 권장하지 않는다.

TreeMap

TreeMap은 TreeSet과 마찬가지로 레드-블랙 트리(Red-Black Tree)의 자료구조를 이용하고있다. 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 성능이 떨어지지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋다.

참고 Blog, Web

https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html (Framwork 정의)
https://coding-factory.tistory.com/602 (Queue)
https://coding-factory.tistory.com/553 (Vector)
https://devlog-wjdrbs96.tistory.com/244 (Stack의 단점)
https://coding-factory.tistory.com/555(Hash, Tree set)
https://st-lab.tistory.com/258 (LinkedHashSet)
https://onsil-thegreenhouse.github.io/programming/java/2018/02/22/java_tutorial_1-24/ (Map예시)
https://hbase.tistory.com/m/134 (HashMap, HashTable 차이)