bdfgdfg
자바의 컬렉션(Collection) 본문
자바에는 컬렉션 클래스가 존재한다.
간단히 말하면 자료구조를 모아놓은 클래스들.
구현된 자료구조 클래스들(파랑색)은 각각의 인터페이스를 상속받아 구현되어 있따.
주로 Hash가 붙은것들은 해시테이블로 구현되어있고, Tree,Sorted가 붙은것은 완전이진탐색트리(레드-블랙트리)로 구현되어 있다.
-> 키(Key)가 필요한 Map 인터페이스를 상속받는 Hash 클래스는 키가 사용자 정의 클래스라면 hashcode를 구현해야하며, SortedMap은 comparator를 구현해주어야 한다.
이러한 자료구조 컬렉션 클래스들은 이미 구현된걸 가져다 쓰는 편리함도 있고, 공통된 인터페이스를 구현하였기에(Collection,Map) 가독성도 높다는 장점이 있다.
List인터페이스
List인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다.
Set인터페이스
Set인터페이스는 중복을 허용하지않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다.
Map인터페이스
Map인터페이스는 키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는데 사용된다.
키는 중복을 허용하지 않고, 값은 중복을 허용하며 순서는 유지되지 않는다.
-> 기존에 저장된 키와 중복된 키를 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다.
ArrayList
ArrayList는 List 인터페이스를 구현한 데이터의 저장순서가 유지되고 중복을 허용하는 특징을 가진다.
-> 간단하게 여러 인터페이스기능이 구현된 동적 배열이라고 보면 된다.
ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일.(가능하면 ArrayList로 쓴다)
물론 어느정도 차이는 있는데 Vector의 경우 동기화 처리가 되어 Thread-Safe하며, Capacity를 넘어서 새로운 버퍼를 생성할 때 기존 Capacity의 2배정도 크기를 만든다면 ArrayList는 1.5배 크기로 만든다고 한다.
크게 어렵지 않기에 주의점 및 특징 여러가지 작성.
1. capacity는 어느정도 크기를 잡아놓는게 좋다.
-> Capacity를 넘어서 데이터를 삽입하면 새롭게 버퍼를 만들고 기존의 버퍼 내용을 복사한 후 기존 버퍼는 Garbage가 된다.
-> 특이하게 Vector는 내부 Capacity를 가져올 수 있는데 ArrayList는 그런 메소드가 존재하지 않더라.
-> 그렇기에 ArrayList를 사용하기전에 미리 ensureCapacity메소드를 호출해 내부 capacity 사이즈를 증가시키던가, 생성자 매개변수에 정수형 값을 넣어서 capacity값을 정해주자.
2. 처음,중간 삽입/삭제는 느리다.
-> 배열에서 중간 삽입/삭제를 할경우 그 뒤에 있는 데이터를 그만큼 밀거나 당겨야 하므로.
-> 당연하지만 끝의 삽입/삭제는 하나의 인덱스에 해당하는 데이터만 제거하면 되므로 빠르다.
3. 배열은 캐싱효과덕에 전체 데이터를 읽는경우엔 속도가 빠른편
LinkedList
연결리스트이며 양방향(이중) 연결리스트이다.
연결리스트는 다음(그리고 이전) 노드를 가리키는 포인터(참조)변수와 내부 데이터를 가지는 노드들이 한줄로 연결되어있는 자료구조.
연결리스트 자체는 첫 요소(Element)를 가리키는 Head포인터(참조)만을 가지기에 내부적으로 인덱싱(혹은 메소드)을 지원하더라도 순차적으로 접근하는 방법밖에 없다.
-> 구조마다 다르지만 마지막 요소를 가리키는 Tail 포인터(참조)도 있음.
이것도 어렵지 않기에 주의점 및 특징만 작성.
1. 내부 구현이 배열로 되어있는 ArrayList보다 처음,중간 삽입/삭제가 빠르다.
-> 연결리스트의 데이터 삽입이란 결국 데이터를 담은 노드를 들어갈 위치에서 노드를 가리키는 포인터(참조)값만 바꾸면 되기에.
-> 물론 중간에 삽입/삭제를 순차적으로 탐색을 해서 진행해야한다면 크게 차이는 없을 듯.
2. 전체 데이터를 읽는 속도와 인덱스에 해당하는 요소에 접근하는 시간은 ArrayList가 빠르다.
-> 전체 데이터를 읽는 것은 캐싱관련과 관련이 있고, 배열은 메모리가 연속적으로 이어지기에 인덱스가 n인 요소를 읽어오는데는 O(1)시간 밖에 걸리지 않는다. LinkedList는 무조건 순차적인 탐색.
즉 자주 삽입/삭제가 일어나지 않는다면 ArrayList를 쓰는게 좋고, 자주 일어난다면 LinkedList를 쓰는게 좋다.
Stack & Queue
Stack은 후입선출(LIFO, Last In First Out), Queue는 선입선출(FIFO, First In First Out)구조를 가지는 자료구조.
stack의 경우에는 마지막에 들어간 데이터가 먼저 pop되는 구조이므로, 내부 구현은 배열로 되어있다.
다만 queue의 경우에는 먼저 들어간 데이터가 먼저 나오므로 내부 구현은 LinkedList로 하는게 적합하다.
Iterator, ListIterator, Enumeration
Iterator, ListIterator, Enumeration은 모두 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스.
-> Enumberation은 Iterator의 구버전이며 ListIterator는 Iterator의 기능을 향상 시킨 것.
디자인 패턴에는 Iterator패턴이 존재한다. 모든 컬렉션들이 내부 구현방식이 다르기에 같은 인터페이스로 컬렉션의 저장된 요소에 접근하기 위함.
Iterator는 Collection인터페이스에 정의된 메소드이므로 그 자손인 List,Set에도 구현이 되어있다.
Iterator의 주요 메소드는 hasNext, next, remove.
ArrayList의 Iterator 각 메소드의 내부구현을 보면
hasNext메소드는 현재 읽어 올 요소(cursor)가 있는지 확인 후 true or false를 반환.
next는 다음 요소를 읽어오며 cursor를 1증가시키며 다음 요소의 값을 반환한다.
그리고 remove. 내부 구현도를 보면 lastRet이라는 것은 위 next메소드에서 다음요소를 반환할 때
lastRet이라는 멤버변수에 기존의 cursor가 가리킨 값을 임시변수(i)에 저장한 후 반환 때 그 값을 저장시킨다.
그렇다는 말은 결국 remove 메소드는 적어도 한번의 next를 호출해야 해당 메소드가 예외를 던지지않고 정상작동한다는 의미.
LinkedList의 내부 구현도는 당연히 ArrayList와 다르지만 의미론적으로 크게 다르지 않으므로 설명x
Map 인터페이스를 보자. 해당 인터페이스를 구현한 컬렉션 클래스는 키와 값의 쌍으로 저장하고 있기에
Iterator를 직접적으로 호출할 수 없고, 그 대신 keySet()이나 entrySet()과 같은 메소드를 통해 키와 값을 각각 따로 SET의 형태로 얻어 온 후에 다시 Iterator()를 호출해야 Iterator를 얻어올 수 있다.
-> Map 컬렉션 클래스 -> keySet() or entrySet() -> Iterator()
import java.io.FileInputStream;
import java.util.*;
import java.time.*;
import java.time.temporal.ChronoUnit;
import java.time.temporal.TemporalAdjusters;
public class Hello {
public static void main(String[] args)
{
Map map = new HashMap();
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
//key-value 쌍들의 Iterator반환 (해당 key-value쌍의 클래스는 HashMap의 내부 클래스인 Node)
Iterator it = map.entrySet().iterator();
// key들의 Iterator 반환
Iterator it2 = map.keySet().iterator();
while(it.hasNext())
{
System.out.println(it.next());
}
while(it2.hasNext())
{
System.out.println(it2.next());
}
}
}
ListIterator 인터페이스는 Iterator를 상속받아 기능을 추가한 것으로, 단방향 접근만 가능한 Iterator와 달리 양방향 접근이 가능하다.
-> List인터페이스를 구현한 컬렉션 클래스인 ArrayList,LinkedList등만 가능하다.
Comparator와 Comparable
Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메소드를 정의한다.
compare와 compareTo 모두 int형 값을 반환한다.
두 객체가 같으면 0, 비교하는 값 보다 작으면 음수, 크면 양수를 반환하도록 구현해야한다.
또한 Comparable은 compareTo메소드의 매개변수는 하나고, Comparator의 compare메소드는 매개변수가 2개이다.
즉, Comparable은 자기자신과 인자로 들어온 값의 비교이며
Comparator는 두 매개변수 객체를 비교하는 것.
HashSet
Set 인터페이스의 특징대로 순서를 유지하지 않으며, 중복값을 허용하지 않는 컬렉션인 HashSet.
-> 저장된 순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.
Map 인터페이스와 달리 key와 value의 쌍을 저장하지 않고, 순수 값 그자체만을 저장한다.
내부 구현은 HashMap을 이용해서 만들어졌고, 이름에 Hash가 붙은 것처럼 해싱을 이용한다.
HashSet은 요소를 추가할 때 현재 저장된 요소와 같은 게 있는지 판별을 위해 추가하려는 요소의
equals와 hashCode를 호출한다.
-> 즉 저장되는게 객체라면 equals와 hashcode구현은 필수.
-> hashcode만 필요한게 아닌가? 라고 생각했는데, hashcode로 먼저 비교하고, 결과가 같다면 추가로 equals를 통해 비교한다고 한다. (-> 두 객체가 equals에서 true가 나온다면 두 객체의 hashcode는 같아야한다. 다만 그 역은 그러지 않아도된다. https://jaehoney.tistory.com/168)
-> 가능하면 해시를 직접 작성하기 보단 Objects.hash 메소드를 이용하자.
해싱을 사용하는 자료구조이기에 기본적으로 검색(탐색)의 속도는 O(1).
TreeSet
TreeSet은 완전 이진 탐색 트리(레드-블랙트리)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스.
이진 탐색트리는 기본적으로 루트 노드부터 값 삽입시 해당 노드를 기준으로 작으면 왼쪽, 크다면 오른쪽.
이런식으로 저장되는 자료구조.
-> 물론 최악의 경우 한쪽으로 쏠리지만 이걸 방지하기 위해 완전 이진 탐색트리를 쓴다
TreeSet은 기본적으로 저장되는 객체의 비교가 이루어지기에 저장되는 게 객체라면 Comparable을 구현해야한다.
TreeSet은 트리라는 구조처럼 정렬된 상태를 유지하기에 단일 값 검색과 범위검색(range search)이 빠르다.
나중에 나오는 TreeMap과의 차이는 단순 값만 저장하느냐, 키와 값의 쌍으로 저장하느냐의 차이뿐이다.
public class Hello {
public static void main(String[] args)
{
Set set = new TreeSet();
set.add(4);
set.add(1);
set.add(3);
set.add(10);
set.add(6);
set.add(2);
System.out.println(set);
}
}[1, 2, 3, 4, 6, 10]
입력한 순서는 유지하지 않지만, 트리라는 구조 특성상 자동으로 정렬되어 있다.
대부분의 경우 Hash > Tree의 사용빈도가 높지만, 범위검색과 단일 검색을 자주 하면서 정렬된 데이터가 필요하다면 Tree를 사용하면된다.
HashMap과 HashTable
HashTable과 HashMap의 내용은 같지만 새로운 버전인 HashMap을 사용하는게 좋다.
-> HashTable은 멀티쓰레드 환경을 고려해 동기화 처리가 되어있음.
HashMap은 HashSet과 동일하게 해싱을 구현한 자료구조(해시테이블)이며 Map인터페이스를 상속받았기에 key,value의 쌍으로 값을 저장한다. (값을 저장하는 기준은 key이게 값이 유일해야 한다.)
Key와 Value를 Map에선 Entry라는 클래스에 저장한다.
HashMap또한 HashSet과 동일하게 hashcode, equals와 같은 방법으로 key의 중복을 체크한다.
'웹프로그래밍 > Java' 카테고리의 다른 글
| 쓰레드 (0) | 2023.07.29 |
|---|---|
| 제네릭스 & 어노테이션 (0) | 2023.07.29 |
| Calendar와 Date 그리고 java.time (0) | 2023.07.27 |
| 자바 java.lang패키지 및 오토박싱&언박싱 (0) | 2023.07.26 |
| 자바의 예외처리(exception handling) (0) | 2023.07.26 |
