JCF와 스레드 - JCF 기초

 

Java를 통해 개발을 하다 보면 반드시 한 번쯤은 사용하게 될 라이브러리가 있다. ArratList, HashSet, ... 등이 있는데, 이들은 JCF라고 부르는 Java에서 제공하는 데이터 구조와 알고리즘의 표준 라이브러리이다. 

 

JCF에 대해 자세히 알아보자.

 

| JCF(Java Collection Framework) 란? 

Java에서 제공하는 데이터 구조와 알고리즘의 표준 라이브러리 

• 데이터 저장, 검색, 정렬, 조작 등의 작업을 효율적으로 수행할 수 있도록 설계된 컬렉션 클래스와 인터페이스의 집합 

 

JCF 계층 구조 ❘ 출처 : Java Collections Framework 종류 총정리 - Inpa Dev

 

JCF는 크게 Collection 인터페이스와 Map 인터페이스로 나뉜다. 

• Map 인터페이스 컬렉션들은 2개의 데이터를 묶어 한쌍으로 다루기 때문에 Collection 인터페이스와 따로 분리되어 있다. 
• 대부분 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현할 인터페이스의 이름이 클래스 이름에 포함되는 특징이 있다. 
• 예외로는 Vector, Stack, Hashtable, Properties 같은 것들인데, 이들은 Collection 프레임워크가 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임워크의 명명법을 따르지 않는다고 한다. (참고로, Vector나 Hashtable과 같은 기존의 컬렉션 클래스들은 호환을 위해 남겨진 것이기 때문에, 가급적 사용하지 않는 것이 좋다고 한다.) 

 

| List와 ArrayList

Java 프로그래밍을 하다보면 반드시 사용하게 되는 컬렉션 인터페이스와 클래스이다. 

• 위에서 언급을 한 것 처럼 List는 인터페이스이고, ArrayList는 클래스이다. 
• List : JCF의 인터페이스이다. 
  • 순서가 유지되고, 중복된 요소를 허용한다. 
  • ArrayList, LinkedList, Vector, Stack 등을 사용할 수 있다. 
  • 구현체를 숨기고 유연한 코드 작성을 위해 인터페이스 타입으로 변수를 선언하는 것이 좋다. 
• ArrayList : List 인터페이스의 구현체로, 배열 기반의 동적리스트이다. 
  • 내부적으로 배열을 사용하여 요소를 저장한다. 
  • 요소의 추가/삭제는 배열 크기 조정을 동반할 수 있어 다소 느릴 수 있다. 
  • 요소 접근이 빠르다. 
  • 비동기적으로 동작하기 때문에 멀티스레드 환경에서 안전하지 않다. 

+) ArrayList는 내부적으로 배열을 사용하면서 어떻게 동적으로 사이즈가 늘어날까? 

배열이라고 하면 가장 먼저 드는 생각은 고정적인 크기이다. 하지만, ArrayList는 동적리스트이다. 

어떻게?! 동적으로 조정이 되는 것일까? 

 

ArrayList는 생성 시 기본적으로 크기 10의 배열을 만든다. 

• 생성자에서 초기 용량(capacity)을 지정할 수도 있다. 

 

요소를 추가하면서 현재 배열에 공간이 남아있다면 배열의 기존 위치에 데이터를 추가한다.

 

만약, 공간이 부족하다면? 동적 크기 조정 과정이 수행된다. 

• ArrayList는 공간이 부족할 때 기존 배열 크기의 1.5배로 크기를 늘린다. 
• 새로운 크기의 배열을 생성하고 새로 생성한 배열에 기존의 데이터를 복사한다. 

 

 

| ArrayList vs LinkedList 

LinkedList에 대해 먼저 알아보자. 

 

LinkedList는 각 Node가 데이터와 포인터를 가지고 한 줄로 연결되어있는 자료 구조이다.

• 데이터를 담고 있는 Node들이 연결되어 있고,
• Node의 포인터가 이전 Node와 다음 Node와의 연결을 담당한다, 

Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 

 

 

그럼, 언제 ArrayList를 사용하고, 언제 LinkedList를 사용할까? 

• ArrayList는 접근 시간이 빠르지만, 삽입 및 삭제가 느리다. 
• LinkedList는 접근 시간이 느리지만, 삽입 및 삭제가 빠르다는 특징이 있다. 

따라서, 리스트의 시작 부분이나 끝 부분에서 삽입과 삭제가 빈번한 Queue의 경우 LinkedList를 사용하고 그렇지 않으면 ArrayList를 사용한다고 한다. (여기서 JCF의 계층 구조를 자세히 보면 LinkedList는 List와 Queue 2개와 연결되어있다는 것을 볼 수 있다.) 

 

 

| Vector vs ArrayList

Vector는 Java에서 이제는 잘 사용되지 않는 자료구조이다. 단지, 호환성을 위해 남겨둔다고 한다. 

 

Vector도 동적 배열(초기 용량을 설정할 수 있으며, 데이터가 추가되면 자동으로 크기를 늘린다. - 기존 크기의 2배)이다.

ArrayList와 다른 점은 가장 크게 Thread-Safe하다는 것이다. 

• 위에서 ArrayList는 Thread-Safe하지 않다고 했다. 

 

예전에는 Vector가 Thread-Safe해서 많이 사용했다고 하는데, 현재는 잘 사용되지 않는다. 

• Vector의 비효율적인 동기화 방식 때문이다. 
  • Vector는 모든 메서드에서 synchronized 키워드를 사용한다.
  • 대부분의 경우, 프로그램은 단일 스레드에서 동작하거나, 특정 메서드에 대한 동기화만 필요하다.
  • 하지만, Vector는 모든 메서드에서 동기화를 적용하기 때문에 불필요한 동기화가 발생한다. 
• CopyOnWriteArrayList와 같은 클래스가 등장하면서 동기화가 필요한 상황에서 더 효율적인 대안이 생겼다. 
  • CopyOnWriteArrayList : 쓰기 작업(추가, 수정, 삭제)이 발생할 때 내부 배열을 복사한다. 
  • 복사된 배열에서 작업이 수행된 뒤, 기존 배열을 대체 한다. 
  • 이로 인해 쓰기 작업이 비싸지만, 읽기 작업이 매우 빠르고 안전하다고 한다. 
  • 모든 읽기 작업에서 동기화를 하지 않아도 안전하며, 읽기 작업은 기존 배열을 그대로 사용하며, 쓰기 작업은 새 배열을 복사해서 처리하기 때문에 읽기-쓰기 충돌도 방지한다. 

 

| Stack vs Queue 

DFS, BFS 문제를 풀다보면 많이 사용하고, 많이 비교되는 자료 구조이다. 

 

Stack에 대해 먼저 살펴보면 다음과 같다. 

• Stack은 LIFO 방식이며, 가장 나중에 삽입된 데이터가 가장 먼저 꺼내지는 구조이다. 
• Java에서의 Stack은 Vector를 상속받은 레거시 클래스로 제공된다.
  • 이는, Vector의 단점이 Stack에도 남아있다는 것이다.
  • 따라서, Stack 보다는 ArrayDeque를 사용한다. 

 

Queue는 FIFO 방식의 자료구조이며, 주로 LinkedList로 구현한다. 

• Queue를 사용하게 될때 Priority Queue(Queue의 구현체)도 접하게 될 텐데, Priority Queue는 데이터 구조를 기반으로 데이터를 일렬로 늘어놓은 다음 가장 우선순위가 높은 데이터를 먼저 꺼내오는 방식이다. 

 

| Set

Set 자료 구조는 중복된 요소를 저장하지 않고, 요소의 저장 순서를 유지하지 않는 특징이 있다. 

• HashSet, LinkedHashSet, TreeSet 클래스를 통해 구현한다. 

 

Set의 가장 큰 특징은 중복된 요소를 저장하지 않는다는 것이다. 어떻게 중복된 요소를 거를 수 있는 것일까? 

• 객체를 저장하기 전에 객체의 hashCode()를 호출해서 해시 코드를 얻어낸다. 
• hashCode()는 객체의 주소를 가져와서 두 객체가 같은 객체인지 확인하는 역할을 한다. (객체 고유의 주솟값 같은 것)
• 저장되어 있는 객체들이 해시 코드와 비교한 뒤 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교한다. (조금 더 알아보고 싶다면 다음의 글을 참고해보자)
• 이때, true가 나온다면, 동일한 객체로 판단하고 중복 저장을 하지 않는다. 

 

| Map 

Map은 Key와 Value를 쌍으로 저장하는 자료구조로, Key는 중복될 수 없고 Value는 중복이 가능하다. 

• Key를 통해 Value에 바로 접근이 가능하기 때문에 탐색에 대한 시간 복잡도가 상수가 나온다. 
• 하지만, 일반적으로 데이터의 순서를 보장하지는 않는다. 
• HashTable, HashMap, TreeMap 등의 구현체가 있다. 

 

이 중에서 나는 HashMap을 가장 많이 사용해 본 것 같다. 따라서, HashMap에 대해서 알아보고자 한다. 

• HashMap : Hash 함수를 사용하여 데이터의 Key 값을 특정 인덱스로 변환하고, 빈 공간 내에 해당 인덱스의 위치에 저장한다. 
• 변환된 인덱스를 Hash 값이라고 하는데, Hash 값을 사용하면 저장된 값을 불러올 때 인덱스 값을 참조해서 부르기 때문에 연산속도가 매우 빠르다. 
• HashMap은 내부적으로 배열(table)과 각 버킷(bucket)에 연결된 Linked List 또는 Balanced Tree로 구성된다. 
  • 각 버킷은 해시 값을 기반으로 키-값 쌍을 저장하는 위치이다. 

 

+) Hash 충돌 

Hash 함수는 임의의 입력 데이터를 고정된 크기의 해시 값으로 변환한다. 하지만 서로 다른 키가 같은 해시 값을 가질 수 있다.

 

이때, 해시 충돌이 발생했다고 한다. 

 

해시 충돌이 발생하면 어떻게 해결할까? 해시 충돌은 해시 체이닝을 통해 해결한다고 한다. 

• 해시 체이닝 : 충돌이 발생하면 충돌이 발생한 버킷에서 연결된 리스트에 새로운 요소를 추가한다. 

 

위의 해시 체이닝 때문에, 최악의 경우에는 모든 키가 동일한 버킷에 저장되어 시간복잡도가 O(N)이 나올 수 있다고 한다.