자바 컬렉션 프레임워크

자바에서 컬렉션 프레임워크란 일정 타입의 데이터들이 모여 쉽게 가공할 수 있도록 지원하는 자료구조들의 기본 틀을 이야기합니다. 틀이라고 하니까 생각나는 것이 있나요? 인터페이스를 떠올렸다면 아주 이해가 쉬울 것 같습니다.

자바의 JDK는 프로그램 개발에 필요한 기초적인 자료구조들을 거의 대부분 컬렉션으로 만들어서 제공하기 때문에, 아주 중요합니다. 컬렉션은 제네릭이라는 기법으로 구현됩니다.

즉, 데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것입니다.

컬렉션은 고정 크기의 배열이 가지는 단점을 극복하고, 요소<E>라고 불리는 객체들의 삽입, 삭제, 검색 기능을 갖춘 가변 크기의 컨테이너 입니다. 

컬렉션의 특징

1. 제네릭으로 구현된다. 컬렉션의 클래스나 인터페이스에는 <E>, <T>와 같은 '타입 매개 변수'가 포함되고, 타입 매개변수는 컬렉션을 구성하는 요소를 일반화시킨 타입입니다.

즉, 컬렉션이 다룰 수 있는 원소의 타입을 여러 종류로 변신할 수 있도록 일반화 시킨 것입니다. 

Stack<E>  -->   Stack<Integer>

              -->   Stack<String>

2. 컬렉션의 요소는 객체만 가능하다. 일반 자료형은 불가능.

프레임워크는 기본틀이다,,, 틀,,구조 --> 아! 인터페이스~!

컬렉션 프레임워크를 구성하는 대표적인 인터페이스로는 set, list, queue가 있고 약간의 뿌리가 다른 map이 있습니다.

1. List컬렉션 클래스 

List인터페이스를 구현한 모든 List컬렉션 클래스는 다음과 같은 특징을 가집니다. 

- 요소의 저장 순서가 유지됩니다. 

- 같은 요소의 중복 저장을 허용합니다. 

대표적인 list컬렉션

ArrayList<E>

Object[]배열을 사용하면서 내부 구현을 통해 동적으로 관리를 한다.

요소접근이 탁월합니다.

삽입 삭제가 비교적 성능이 좋지 않습니다.

하지만 내부적으로 친숙한 배열을 이용하기 때문에, 인덱스를 사용해 배열 요소에 빠르게 접근가능하기 때문에 가장 많이 사용 됩니다.

하지만 배열은 크기를 변경할 수 없는 객체이므로, 크기를 늘리기 위해서는 새로운 배열을 생성하고 기존의 요소들을 옮겨야 하는 복잡한 과정을 거칩니다. 물론 ArrayList를 사용하면 이 작업은 자동으로 이루어지지만, 요소의 추가 및 삭제 작업에 걸리는 시간이 매우 길다는 단점이 극복되지는 않습니다.

LinkedList<E>

데이터와 주소로 이루어진 클래스(노드)를 연결하여 이루어짐 각 노드는 이전의 노드와 다음 노드를 연결한다.(이중연결리스트) 

요소검색이 굉장히 어려움 처음부터 찾고자 하는 값까지 가야함.

중간 삽입 삭제는 최고

ArrayList클래스가 배열을 이용하여 요소를 저장함으로써 발생하는 단점, 요소의 추가 및 삭제가 어려움을 극복하기 위해 고안 됨. 

내부적으로 연결리스트를 이용하여 요소를 저장한다. 저장된 요소가 순차적으로 저장되는 배열과 달리 저장된 요소가 비 순차적으로 분포되며, 이러한 요소들 사이를 링크로 연결한다. 

장점 - 요소의 저장과 삭제 작업이 굉장히 빠름.

단점 - 이전 요소로 접근하기가 매우 어려움

따라서 이중 연결리스트를 많이 사용함

Stack<E>

후입선출

 

2. 큐 컬렉션 클래스 

LinkedList 큐를 노드로 관리

이 컬렉션 클래스는 list와 deque queue세가지 용도로 쓸 수 있다.

 

3. 셋 : 집합

데이터의 중복 저장 불가 

입력순서 != 저장순서

 

 

우리가 가장 익숙하게 사용하는 자료구조는 배열입니다. 다만, 자바 컬렉션 프레임워크에서 지원하는 리스트 인터페이스를 구현한 리스트 클래스들은 개발자가 데이터들을 좀 더 쉽게 다루기 위해 메소드들을 구현한 것입니다. 

배열과 리스트 클래스의 [공통점] 

1. 동일한 특성의 데이터들을 묶는다. 

2. 반복문 내의 변수(i)를 이용하여 모든 데이터에 접근할 수 있다.

[차이점]

배열

1. 정적 할당 -> 초기 할당 크기를 변경할 수 없습니다. 

2. 메모리에 연속적으로 나열되어 할당합니다. 

3. 데이터 사이에 빈 공간을 허용한다. (특정 위치에 데이터를 삭제하더라도 최적화되지 않음)

[장점]

1. 데이터의 크기가 정적이므로 메모리 관리가 용이하다 

2. 메모리에 연속적으로 나열되어있기 때문에 접근 속도가 빠름 

[단점] 

1. 배열의 크기를 변경 불가 -> 너무 크게 잡으면 낭비, 너무 작게 잡으면 부족해서 데이터를 모두 수용하지 못함

2. 빈공간을 허용하지 않고자 한다면 모든 데이터들이 이동해야 하기 때문에 속도가 느림

 

리스트 

1. 동적 할당 -> 리스트의 길이를 가변적으로 사용할 수 있습니다. 삽입 삭제의 경우의수에 따라 크기가 부족하면 증축, 너무 많이 남으면  감축해서 메모리 관리한다. 

2. 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되지 않고 각 데이터들은 주소로 연결되어 있다.)

3. 데이터 사이에 빈공간을 허용하지 않음 빈공간이 생기면 반드시 밀거나 당겨서 메모리 용량을 최적화 시킴

[장점] 

1. 데이터의 개수에 따라서 메모리를 동적으로 조정하기 때문에 메모리 관리가 편하다.(자동으로 바뀜)

2. 빈공간을 허용하지 않기에 데이터를 관리하기에도 편하다 

3. 주소로 연결되어 있기 때문에 연결된 주소만 바꾸어주면 삽입 삭제가 편하다 (ArrayList제외)

[단점]

1. 주소를 기반으로 구성되어 있고 메모리에 순차적으로 할당하는 것이 아니라 검색능력이 떨어진다.(물리적 주소가 순차적이지 않음)

 

List 

저장 순서 유지, 중복 허용

vector(동기화 되어 있음)는 ArrayList(동기화 안 되어 있음)와 거의 비슷한데, 전자는 옛날이고, 후자는 전자를 개선한 것입니다. 

ArryaList, LinkedList가 핵심이다. 

 

배열의 장점

배열은 구조가 간단하고, 데이터를 읽는 데 걸리는 시간(접근시간)이 짧다.

배열의 단점

크기를 변경할 수 없다. -> 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사한 후 참조변수를 변경해야 합니다.

비 순차적인 데이터의 추가, 삭제에 시간이 많이 걸립니다.(중간 데이터 삽입 및 삭제)

- 데이터를 추가하거나 삭제하기 위해 다른 데이터를 옮겨야 합니다. 

- 그러나 순차적인 데이터의 추가나 삭제는 빠릅니다.

 

링크드리스트 - 배열의 단점을 보완

배열과 달리 불연속적으로 존재하는 데이터를 연결

데이터의 삭제 : 단 한번의 참조변경(다음 노드를 가리키는 next값 변경)만으로 가능하다.

데이터의 추가 : 한 번의 Node객체 생성과 두 번의 참조변경만으로 가능

단점 : 데이터의 접근성이 안 좋음. 특정 데이터에 접근하기 위해서는 그 사이에 있는 데이터를 건너 뛸 수 없고, 반드시 지나가야 합니다.  -> 이를 보완하기 위해 만든 것이 이중 연결리스트입니다. (이전과 다음주소를 저장합니다.) 하지만 여전히 배열보다는 접근성이 좋지 않음-> 이를 또 보완한 것이 이중 원형 연결리스트입니다. (양 끝 마지막 null을 반대편 노드로 연결합니다.)

성능비교

컬렉션	접근시간	추가 / 삭제	비 고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름 비효율적인 메모리 사용(단점인 배열의 복사를 최소화 시키기 위해 배열의 크기를 크게 잡음)
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어진다.

 

Set

저장 순서 유지X, 중복 불가 

HashSet, TreeSet이 핵심이다.

HashSet은 Set인터페이스의 구현 클래스입니다. 그렇기에 set의 성질을 그대로 상속받습니다. set은 객체를 중복해서 저장할 수 없고, 하나의 null값만 저장할 수 있습니다. 또한 저장 순서가 유지 되지 않습니다. 만약 요소의 저장순서를 유지해야 한다면 linkedhashset을 사용합니다. 가장 큰 장점은 중복을 자동으로 제거해준다는 점

set은 비선형 구조이기 떄문에 순서가 없으며, 인덱스도 존재하지 않습니다. 따라서 값을 삭제할 때에는 내가 추가 혹은 삭제하고자 하는 값이 set 내부에 있는지 검색 한 뒤 추가나 삭제를 해야 하므로 속도가 list구조에 비해 느립니다.

해시맵은 해시테이블을 사용하여 저장하지만, 해시셋은 주머니에 객체가 담겨있다고 생각하면 편합니다. 그래서 contains메소드로 값이 있는지만 확인한다. hashcode()를 호출해서 비교하는 것도 이와 같음

중복을 걸러내는 과정 hashcode -> equals. 다른 값에 대해 같은 해시코드 존재가능 -> 같은 해시코드는 equals로 구분

hashset은 객체를 저장하기 전에 먼저 저장하고자 하는 객체의 hashCode()메소드를 호출해서 코드를 얻어낸 다음 저장되어 있는 객체들의 해시코드와 비교한 뒤, 같은 해시코드가 있다면 다시 equals()메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않습니다.

 

Treeset은 set인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고, 저장 순서가 유지 되지 않습니다. 하지만 hashset과 달리 이진 탐색 트리의 구조를 가지고 있습니다. 추가와 삭제에는 시간이 조금 더 걸리지만, 검색과 정렬에는 유리합니다.  정렬방법은 기본적인 정렬 메커니즘을(오름차순) 사용해도 되고, 매개변수로 comparator를 입력받아서 정렬방법을 임의로 지정할 수도 있습니다.

treeset또한 레드블랙트리로 구현되어 있습니다.

 

Map

저장 순서 유지X, 키(K)는 중복 불가, 값(V)은 중복 허용

HashMap(동기화 안되어 있음), TreeMap이 핵심이다.

 

hashmap(new)과 hashtable(old)

hashmap

hashmap은 map인터페이스를 구현한 대표적인 클래스입니다. map인터페이스를 상속하고 있기에 map의 성질을 그대로 가지고 있습니다. map은 키와 값으로 구성된 entry객체를 저장하는 구조를 가지고 있습니다. 여기서 키와 값은 모두 독립적인 객체입니다. 값value는 중복 저장될 수 있지만, 키key는 중복 저장될 수 없습니다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고, 새로운 값으로 덮어씌워집니다. 해싱함수를 사용해 데이터를 검색하고 접근합니다. 해싱함수의 기본적인 원리는 다음과 같습니다.

 

순서를 유지하려면, 링크드 해쉬맵 클래스를 사용하면 된다.

해싱이란? 

어떤 키값을 해쉬함수에 넣으면 해시함수가 해쉬코드(저장위치)를 알려준다. 해시함수를 사용하여 데이터를 저장하고 데이터를 읽어온다. 해시함수를 통해 키와 값이 저장되는 위치를 결정하므로, 사용자는 그 위치를 알 수 없고, 삽입되는 순서와 들어있는 위치 또한 관계 없습니다.(저장 순서를 유지하지 않습니다. hashmap은 해시테이블 상에서 해시함수의 반환값인 해시 코드를 통해 접근하는 것. 해시함수에 대해서 알 필요는 없고, 과정만 알면 됨. treemap은 저장되는 데이터를 정렬하기 때문에 이 또한 저장한 순서가 유지되지 않음. 유지된다는 것은 arrayList같은 것 ) 

해시함수로 해시테이블에 데이터를 저장 검색합니다.

해시테이블은 배열(빠른 접근성)과 링크드 리스트(변경의 용이성)가 조합된 형태. 각 리스트의 장점이 결합된 형태

1. 키로 해시함수를 호출해서 해시코드를 얻는다. 

2. 해시코드(해시함수의 반환값)에 대응하는 링크드리스트를 배열에서 찾는다. 

3. 링크드 리스트에서 키와 일치하는 데이터를 찾는다. 

해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야 한다.

서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다.

map 인터페이스 내부에 entry인터페이스가 정의되어 있다.

 

treemap

이진트리를 기반으로 한 map인터페이스를 구현한 클래스입니다. 같은 트리구조로 이루어진 treeset과의 차이점은 treeset은 값만 저장한다면, treemap은 키와 값이 저장된 Entry형태로 저장을 합니다. Treemap은 객체를 저장하면 자동으로 정렬이 되는데, 키값을 기준으로 오름차순으로 정렬이 되며, 키값이 숫자인 경우는 값으로, 키값이 문자열일때는 유니코드를 기준으로 정렬합니다. 부모키보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 정렬이 됩니다. treemap은 정렬을 하고 값을 저장하기 때문에 hashmap에 비해서 추가나 삭제에 대한 성능이 떨어집니다. 하지만 정렬된 상태로 map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위검색이 필요한 경우에는 treemap을 사용하는 것이 효율적입니다.

treemap은 이진 탐색 트리의 문제점을 보완한 레드블랙트리로 이루어져 있습니다. 일반적으로 이진탐색트리는 트리의 레벨, 즉 트리의 높이 만큼의 시간이 필요한데, 만약 트리가 한쪽으로 편향된 상태로 구성되어 있다면, 본래의 성질을 잃고 시간복잡도가 증가하게 됩니다. 이러한 점을 보완한 것이 레드블랙트리로 한쪽으로 치우지지 않도록 균형을 맞추어 줍니다. 자세한 구현은 컬렉션을 이해하는데 중요하지 않다고 생각합니다. 그냥 기본적인 이진 탐색트리를 좀더 효율적으로 편향되지 않고 균형이 잘 잡히도록 저장한다고 생각하세요.

 

 

iterator(new), enumeration(old) -> 이름만 다를 뿐 기능은 동일하다

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

컬렉션에 저장된 요소들을 읽어오는 방법을 표준화 한것.

boolean hasNext() : 읽어 올 요소가 남아있는지 확인한다. 읽으면 true, 없으면 false를 반환

Object next() : 다음 요소를 읽어 온다. next()를 호출하기 전에 hasNext()를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전하다.

 

listiterator : iterator의 접근성을 향상시킨 것(단방향 -> 양방향) 

next(), previous()