[자바의정석] Collections Framework

etlaou·2021년 7월 30일
Java
0

컬렉션 프레임웍

데이터 그룹을 저장하는 클래스를 표준화 한 설계

컬렉션 프레임워의 특징

  1. 다양한 클래스들을 지원한다.
  2. 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있기 때문에 사용법을 익히기 쉽다.
  3. 재사용성이 높은 코드를 작성할 수 있다는 장점이 있다.

핵심 인터페이스

List와 Set은 공통된 부분이 많기 때문에 공통 부분을 Collection이라는 인터페이스로 분리
Map 인터페이스는 이들과는 다른 형태이기 때문에 상속 계층도에 속하지 못한다.

📌 핵심 인터페이스 특징들을 살펴보자.

  • List: 순서가 있다. 데이터 중복을 허용
  • Set: 순서가 없다. 데이터 중복을 허용하지 않는다.
  • Map: 키와 값의 쌍으로 이루어진 데이터의 집합 (값은 중복이 허용되나, 키는 중복 불가)
  • Collection: List와 Set의 조상 인터페이스로 가장 기본적인 메서드(읽기, 추가, 삭제 등)들을 정의한다.

💡 List를 깊게 봐야 될 필요가 있다. 순서라는 특징때문에 어떤 기능을 구현할 때는 뭐가 더 효율적인지 생각해야 한다.

ArrayList

Object 배열을 이용해서 데이터를 순차적으로 저장하는 가장 많이 사용되는 컬랙션 프레임웍

  • ArrayList 사용예제

✍️ 위에 예제에서 list에서 하나씩 삭제하는 부분을 한번 볼 필요가 있다.

반복문에서 원래는 보통 증가하는 반복문을 작성하지만, 여기서는 감소한다. 왜 그럴까?
그 이유는 만약 0부터 시작해서 리스트의 길이만큼 반복한다고 가정하자. 리스트의 0번째 객체를 제거하면 1번째 객체의 인덱스가 0이 된다. 하지만 반복문은 0 → 1 → 2로 증가하기 때문에 자리 이동으로 인한 올바른 결과를 얻을 수가 없다.

  • 다음은 Vector의 용량과 크기에 관한 예제이다.

여기서 가장 중요한 부분은 용량보다 배열의 크기를 크게 지정할 경우, 불필요하게 용량이 2배가 된다는 것이다. 이는 효율성을 악화시키는 요소 중에 하나이다.

📌 추가로 설명하자면, ArrayList나 Vector같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야 할 때는 새로운 배열을 생성한 후 기존의 배열로 부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 효율성이 굉장히 떨어진다. → 충분한 용량의 인스턴스를 생성하자.

Linked List

"연결리스트"를 보기 전에 배열을 잠깐 봐보자.

배열은 가장 기본적인 형태의 자료구조
사용하기 쉽고 간단하며 데이터를 Read하는 속도가 가장 빠르다.
하지만 단점 역시 존재한다.

  • 배열의 단점
  1. 크기를 변경할 수 없다.
    → 크기를 변경할 수 없기 때문에 배열(변경할 크기의 배열)을 새로 생성해서 데이터를 복사
    → 데이터를 복사하는 연산을 추가로 해야 되기때문에 효율성이 떨어지고 메모리를 낭비한다
  2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
    → 순차적인 데이터를 추가하고 마지막부터 삭제하는 것은 빠르지만, 배열의 중간에 데이터를 추가하려면 빈자리를 만들기 위한 데이터를 복사해 이동해야 한다.

💡 이러한 배열의 단점을 보완한게 Linked List이다.

📌 연결리스트 : 불연속적으로 존재하는 데이터를 서로 연결한 리스트

  • 연결리스트에서 데이터 삭제

    삭제하고자 하는 요소의 이전 요소가 삭제할 요소의 다음 요소를 참조하게 하면 된다.
    → 단 하나의 참조만 변경하면 삭제가 가능하기 때문에 데이터를 복사하는 과정이 없기 때문에 처리속도가
    빠르다.

이중연결리스트

단방향인 링크드리스트에서 다음 요소가 아닌 이전 요소에 대한 접근을 쉽게 하기 위해 만들어진 리스트
→ 양방향 연결리스트

더블 써큘러 링크드 리스트

이중 연결리스트의 첫번째 요소와 마지막 요소를 서로 연결시킨 것

💡ArrayList VS LinkedList

[성능 비교]

  1. 순차적으로 추가/삭제하는 경우 → ArrayList

    순차적으로 삭제할 경우에는 중간에 요소를 삭제하고 복사하는 재배치 연산을 할 필요가 없기 때문에

  2. 중간 데이터를 추가/삭제하는 경우 → LinkedList

    중간 데이터를 추가/삭제하는 경우에는 연결리스트에서 각 요소의 참조를 변경만 해주면 되기 때문에 속도가 굉장히 빠르다.

  3. 배열의 n번째 요소 읽기 → ArrayList

    배열에서 인덱스 n의 주소 = 배열의 주소 + n * 데이터 타입의 크기
    ArrayList는 데이터가 연속적으로 메모리에 존재하기 때문에 위의 계산으로 데이터를 쉽게 읽을 수 있다.
    하지만 불연속적으로 위치한 LinkedList 경우에는 n번째 데이터부터 차례대로 읽어야하기 때문에 Access Time이 길다.

✏️ 정리

데이터 크기의 변경이 없다 → ArrayList
데이터 변경이 잦다 → LinkedList
이런 두 리스트의 장점을 조합해서 사용하면 좋은 효율을 얻을 수 있다.

Stack & Queue

  • Stack : 마지막에 저장되는 데이터를 가장 먼저 꺼내는 LIFO 구조
    → 순차적으로 데이터를 추가하고 삭제하는 연산을 하기 때문에 Stack은 ArrayList로 구현하면 좋다.
  • Queue : 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO 구조
    → 큐는 처음 저장한 데이터를 가장 먼저 꺼내기 때문에 저장된 데이터를 꺼낼때마다 삭제로 인한 데이터의 복사가 발생하므로 LinkedList로 Queue를 구현하는 것이 적합하다.

import java.util.*;

class StackQueueEx {
	public static void main(String[] args) {
		Stack st = new Stack();
		Queue q = new LinkedList();	 // Queue인터페이스의 구현체인 LinkedList를 사용
		
		st.push("0");
		st.push("1");
		st.push("2");

		q.offer("0");
		q.offer("1");
		q.offer("2");

		System.out.println("= Stack =");
		while(!st.empty()) {
			System.out.println(st.pop());
		}

		System.out.println("= Queue =");
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

PriorityQueue

스택이나 큐 같은 경우 저장한 순서에 따라 데이터를 넣고 뺏지만, 우선순위큐는 저장 순서와 관계없이 우선순위가 높은 것부터 꺼낸다.
✓ 추가로 null을 저장할 수 없다. null은 우선순위가 없기때문에

우선순위큐는 저장공간으로 배열을 사용하고, 각 요소를 Heap의 형태로 저장한다.

Deque

큐의 변형으로 양쪽 끝에서 데이터를 추가하고 삭제가 가능한 구조이다.

Iterator, Listiterator, Enumeration

→ 컬랙션에 저장된 요소를 접근하는데 사용되는 인터페이스

  1. Iterator (데이터의 접근하는 메서드)
    : 컬랙션에 저장된 요소들을 읽어오는 메서드
    Iterator를 사용해 컬랙션의 요소를 읽어오는 방법을 표준화했기 때문에 이처럼 코드를 재사용성을 높이는 것이 객체지향의 목적 중 하나
import java.util.*;

class IteratorEx1 {
	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		list.add("5");
		
        //이처럼 Iterator는 반복문에 주로 사용
		Iterator it = list.iterator(); 
		while(it.hasNext()) { //hashNext() 읽어올 데이터가 있는지 확인
			Object obj = it.next(); //다음 요소 Read
			System.out.println(obj);
		}
	} // main
}
  1. Listiterator
    : Iterator의 자손 인터페이스
    단방향으로 데이터 접근(hasNext(), next())하는 Iterator에 기능을 추가하여 양방향으로 데이터 접근이 가능하다. (hasPrevious(), previous())
    → 반드시 hasNext() 또는 hasPrevious()를 사용해 데이터가 있는지 확인하고 접근해야한다.
  2. Enumeration
    : Iterator의 구버전(→ Enumeration말고 Iterator 사용하기)

[Iterator 예제]

import java.util.*;

class MyVector2Test {
	public static void main(String args[]) {
		MyVector2 v = new MyVector2();
		v.add("0");
		v.add("1");
		v.add("2");
		v.add("3");
		v.add("4");
		// v = [0,1,2,3,4]
		System.out.println("»èÁ¦ Àü : " + v);
		Iterator it = v.iterator();
		it.next(); // read [0]
		it.remove(); // del [0]
		it.next(); // read [1]
		it.remove(); // del [1]
		//v = [2,3,4]
        	//📌 여기서 봐야될 부분은 remove를 하려면 
            	//반드시 next() 또는 previous()를 사용해 데이터를 읽어와야 한다는 것이다.
                //그렇지 않으면, IllegalStateException 발생!!
		System.out.println("»èÁ¦ ÈÄ : " + v);
	}
}

Arrays의 정렬과 검색

배열을 정렬할 때는 sort()를 사용하고, 검색할 때는 binarySearh()를 사용한다. 하지만 binarySearch를 사용할 때는 반드시 정렬이 되어있는 상태여야 하고, 정렬이 아닐 경우 올바른 값을 얻지 못한다.

  • Linear Search와 BinarySearch 비교

    선형탐색은 검색을 할 때 정렬을 할 필요는 없지만, 배열을 하나 하나씩 비교하기 때문에 시간이 오래 걸린다.
    이진탐색은 선형탐색에 비해 반씩 줄여가면서 검색하기 때문에 검색속도가 빠르다. 단 정렬된 상태일 경우

Arrays 비교 및 출력

  • 출력

    1차원 배열 : toString(arr)
    다차원 배열 : deepToString(arr)

  • 비교

    1차원 배열간 비교: equeals(arr1,arr2)
    다차원 배열간 비교: deepEqueals(arr1,arr2)

💡 만약 같은 데이터를 갖고 있는 서로 다른 arr1, arr2를 equals()로 비교하면 어떤 결과를 얻을까?
→ False를 return한다.
→ 왜냐하면 equals()로 비교할 경우 문자열을 비교하는 것이 아니라, 주소를 비교하는 것이기 때문에 같은 데이터를 저장한 배열일지라고 배열은 서로 다른 주소를 갖기 때문에 False를 얻는다.

HashSet

Set과 같이 중복을 허용하지 않는다. HashSet에 데이터를 저장할 때 이미 저장된 객체이면 False를 반환하여 추가를 하지 않는다. 또한 Set에 특성상 저장순서를 유지하지 않기 때문에 저장순서를 유지하려면 LinkedHashSet을 사용하면 된다.
→ HashSet을 이용하면 중복요소를 쉽게 제거할 수 있다.

import java.util.*;

class HashSetEx1 {
	public static void main(String[] args) {
		Object[] objArr = {"1",new Integer(1),"2","2","3","3","4","4","4"};
		Set set = new HashSet();

		for(int i=0; i < objArr.length; i++) {
			set.add(objArr[i]);	// HashSet에 objArr의 요소들을 저장한다.
		}
             // HashSet에 저장된 요소들을 출력한다.
		System.out.println(set); //[1,1,,2,3,4]
	}
}

1이 두 개인 이유는 하나는 정수 하나는 문자열이기 때문에 서로 다른 객체이므로 중복으로 간주하지 않는다.

import java.util.*;

class HashSetEx4 {
	public static void main(String[] args) {
		HashSet set = new HashSet();

		set.add(new String("abc"));
		set.add(new String("abc"));
		set.add(new Person2("David",10));
		set.add(new Person2("David",10));

		System.out.println(set);
	}
}

class Person2 {
	String name;
	int age;

	Person2(String name, int age) {
		this.name = name;
		this.age = age;
	}

	public boolean equals(Object obj) {
		if(obj instanceof Person2) {
			Person2 tmp = (Person2)obj;
			return name.equals(tmp.name) && age==tmp.age;
		}

		return false;
	}

	public int hashCode() {
		return (name+age).hashCode();
	}

	public String toString() {
		return name +":"+ age;
	}
}

📌 위 코드에 대한 설명은 한번 같이 봐야 될 것 같다.(p.635)

TreeSet

이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 클래스
이진 검색 트리의 성능을 향상시킨 레드-블랙 트리로 구현되어 있다.
Set이기 때문에 중복을 허용하지 않으며, 정렬된 위치에 저장하므로 저장순서를 유지하지 않는다.

  • 이진 검색 트리

    정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조

    1. 모든 노드는 최대 두개의 자식 노드
    2. 왼쪽 노드는 부모노드보다 작고, 오른쪽 노드는 부모노드 보다 크다.
    3. 저장순서를 유지하지 않기 때문에 노드의 추가/삭제에 시간이 걸린다.
    4. 검색과 정렬에 유리

  1. 왼쪽 → 부모 → 오른쪽 순서로 읽으면 정렬된 순서를 얻을 수 있기 때문에 검색에 유리하다.
  2. 데이터가 많아질수록 검색시간이 증가하지만, 데이터가 10배 증가하더라도 비교횟수가 4번 정도 밖에 증가안할 정도로 검색효율이 뛰어나다.
  3. 데이터를 순차적으로 저장하는 것이 아니라 데이터를 비교하며 위치를 찾아가며 저장하기 때문에, 링크드 리스트 보다 데이터 추가/삭제가 오래 걸린다.
  • TreeSet의 함수
    1. set.subSet(from, to) : 범위 내에서의 검색
    2. set.headSet(x) : x보다 작은 값
    3. set.tailSet(x) : x보다 크거나 같은 값

HashMap

Hash + Map
Map의 키와 값을 묶어 하나의 데이터로 저장한다는 특징과
Hash의 대용량 데이터를 검색하는 특징을 합친 것

Entry[] table;
class Entry {
	Object key;
    Object value;
}

✓ 이와 같이 MashMap은 Entry라는 내부 클래스를 정의하고, 다시 Entry 타입의 배열을 선언한 구조이다.
이는 키와 값이 무관한 값이 아니라 관련이 있는 값이기 때문에 각각의 배열로 선언한 것이 아닌 하나의 클래스로 정의하여, 데이터 무결성 측면에서 바람직한 객체지향적인 코드이다.

Key : 유일한 값
value: 중복 허용

📌 HashMap은 HashTable과 다르게 Key와 Value에 Null 값을 허용한다.

해싱과 해시함수

  • 해싱

    해시함수를 이용해서 데이터를 해시 테이블에 저장하고 검색하는 기법
    (해시함수: 데이터가 저장되어 있는 곳을 알려주기 때문에 데이터를 검색하는 함수이다.)
    해싱은 배열과 링크드 리스트의 조합의 자료구조로 되어있다.

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻고, 그 요소에 연결된 링크드 리스트에 저장한다.

📌[HashMap에 저장된 데이터를 찾는 과정]

  1. 검색하고자 하는 값의 키로 해시함수 호출
  2. 해시함수의 Output인 해시코드로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.
  3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.
  • 더 효율적인 HashMap의 구조

    링크드 리스트는 검색에 불리한 자료구조로 링크드 리스트에 크기가 커질수록 검색속도는 저하된다.

    하지만, 배열은 배열의 크기와 상관없이 검색하고자 하는 요소가 어디에 있는지 안다면 빠르게 검색할 수 있다.

    배열의 요소당 최소한의 데이터만 저장되어 있는 형태가 검색속도가 빠르다.
    → 그러기 위해서는 HashMap의 크기를 적절하게 지정하고, 중복된 해소코드를 최소화해야 한다.

TreeMap

이진 검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장하며, 검색과 정렬에 적합한 컬랙션 클래스이다.

  • HashMap과 TreeMap

    두 클래스 모두 검색에 적합한 클래스이지만, 대부분의 검색의 경우 HashMap이 더 속도가 빠르고 범위에서의 검색과 정렬이 필요한 경우에는 TreeMap이 우수하다.

Properties

HashTable을 상속받아 구현한 것으로, (String, String)의 형태로 저장하는 단순한 클래스이다.

주로 환경설정과 관련된 속성을 저장하는데 사용되며 데이터를 파일로부터 읽고 쓰는 기능을 제공한다.

Collections

  • 컬랙션 동기화

    멀티쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시에 접근하기 때문에 데이터 일관성을 유지하기 위한 객체 동기화가 필요하다.
    이를 위해 Collections 클래스의 동기화메서드(synchronized)를 사용해 동기화 처리가 가능하다.

  • 변경불가 컬랙션

    위에서 말했듯이 멀티쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 사용할 수 있기 때문에 데이터 손상을 방지를 할 필요가 있다. unmodifiable메서드를 사용하여 데이터를 보호하기 위해 컬랙션을 변경하지 못하도록 할 수 있다.

  • 싱글톤 컬랙션

    단 하나의 객체만을 저장하는 컬랙션을 생성하고 싶을 때 사용한다. 이렇게 생성된 컬랙션을 변경이 불가능하다.
    singleton()

  • 한 종류의 객체만 저장하는 컬랙션

    컬랙션에 대체로 하나의 종류의 객체만을 저장하며, 지정된 객체만을 저장하도록 제한을 두고 싶을 때 사용한다.
    checked()

profile
etlaou
To be Cloud DevOps Engineer
이전 포스트

Code Review를 해볼까?

다음 포스트

[자바의 정석] 지네릭스, 열거형, 애너테이션

0개의 댓글