[윤성우의 열혈 Java 프로그래밍] Chapter 23 - 컬렉션 프레임워크 1
카테고리: Java lang
태그: java
23-1. 컬렉션 프레임워크의 이해
인스턴스의 저장과 삭제, 참조에 대한 문법
- '프레임워크'라는 표현의 이해
자바에서 말하는 프레임워크는 다음과 같이 이해할 수 있다.
잘 정의된 구조의 클래스들
즉, 프로그래머들이 쓸 수 있도록 잘 정의된 클래스들의 모임이라 할 수 있다.
다만, 컬렉션 관련된 클래스의 정의에 적용되는 설계 원칙 또는 구조가 존재하기 때문에
단순히 ‘컬렉션 라이브러리’라 하지 않고, ‘컬렉션 프레임워크’라고 한다.
- 컬렉션의 의미와 자료구조
컬렉션 프레임워크는 데이터의 저장 방법, 그리고 이와 관련있는 알고리즘에 대한 프레임워크이다.
즉, 자료구조와 알고리즘을 제네릭 기반의 클래스와 메소드로 미리 구현해 놓은 결과물이라 할 수 있다.
따라서 컬렉션 프레임워크를 이용하면 자료구조를 몰라도 트리 기반으로 데이터를 저장할 수 있고,
알고리즘을 몰라도 이진 탐색을 수행할 수 있는 것이다.
- 컬렉션 프레임워크의 기본 골격
컬렉션 클래스들이 구현하는 인터페이스들의 상속 관계를 보여주고 있다.
인스턴스를 저장하는 컬렉션 클래스들은 위의 인터페이스 중 하나를 구현하게 되어 있으며, 구현한 인터페이스에 따라서 컬렉션 클래스의 데이터 저장 방식이 결정된다.
23-2. List 인터페이스를 구현하는 컬렉션 클래스들
- ArrayList, LinkedList
List 인터페이스를 구현하는 대표적인 컬렉션 클래스 둘은 다음과 같다.
ArrayList: 배열 기반 자료구조, 배열을 이용하여 인스턴스 저장LinkedList: 리스트 기반 자료구조, 리스트를 구성하여 인스턴스 저장
List 인터페이스를 구현하는 컬렉션 클래스들은 공통적으로 다음 두 가지 특성을 가진다.
- 인스턴스의 저장 순서를 유지한다.
- 동일하 인스턴스의 중복 저장을 허용한다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ListCollection {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
//List<String> list = new LinkedList<>();
// 컬렉션 인스턴스에 문자열 인스턴스 저장
list.add("Toy");
list.add("Box");
list.add("Robot");
// 저장된 문자열 인스턴스의 참조
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i) + '\t');
}
System.out.println();
list.remove(0); // 첫 번째 인스턴스 삭제
// 첫 번째 인스턴스 삭제 후 나머지 인스턴스들을 참조
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i) + '\t');
}
System.out.println();
}
}
코드에 유연성을 제공하기 위해 위와 같이 List형 참조변수를 사용하는 것이 더 적절하다.
주로 List에 선언된 메소드를 호출하기 때문에 굳이 ArrayList형 참조변수를 선언할 필요가 없으며,
다음과 같이 컬렉션 클래스의 교체가 용이해진다.
List<String> list = new ArrayList<>();
-> List<String> list = new LinkedList<>();
- ArrayList vs LinkedList
ArrayList- 장점
- 저장된 인스턴스의 참조가 빠르다.
- 단점
- 저장공간을 늘리는 과정에서 시간이 많이 소요된다.
- 인스턴스의 삭제 연산에서 많은 연산이 필요하다. 따라서 속도가 느리다.
- 장점
LinkedList- 장점
- 저장공간을 늘리는 과정이 간단하다.
- 저장된 인스턴스의 삭제 과정이 단순하다.
- 단점
- 저장된 인스턴스의 참조과정이 배열에 비해 복잡하다. 따라서 속도가 느리다.
- 장점
- 저장된 인스턴스의 순차적 접근 방법 1: enhanced for문의 사용
다음과 같이 enhanced for문을 사용하여 저장된 인스턴스들에 순차적으로 접근이 가능하다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class EnhancedForCollection {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
//List<String> list = new LinkedList<>();
// 컬렉션 인스턴스에 문자열 인스턴스 저장
list.add("Toy");
list.add("Box");
list.add("Robot");
// 저장된 문자열 인스턴스의 참조
for (String s : list) {
System.out.println(s + '\t');
}
System.out.println();
list.remove(0); // 첫 번째 인스턴스 삭제
// 첫 번째 인스턴스 삭제 후 나머지 인스턴스들을 참조
for (String s : list) {
System.out.println(s + '\t');
}
System.out.println();
}
}
for-each문을 통한 순차적 접근의 대상이 되려면, 해당 컬렉션 클래스는 다음 인터페이스를 구현해야 한다.
public interface Iterable<T>
Collection이 Iterable을 상속하기 때문에
LinkedList와 ArrayList 클래스는 for-each문 사용이 가능하다.
- 저장된 인스턴스의 순차적 접근 방법 2
Iterable에는 다음 추상 메소드가 있다.
Iterable<T> iterator() // 반복자를 반환하는 메소드
반복자란,
저장된 인스턴스들을 순차적으로 참조할 때 사용하는 인스턴스로 일종의 ‘지팡이’에 비유할 수 있다.
그리고 이 반복자를 통해 호출할 수 있는 메소들을은 다음과 같다.
E next() // 다음 인스턴스의 참조 값을 반환
boolean hasNext() // next 메소드 호출 시 참조 값 반환 가능 여부 확인
void remove() // next 메소드 호출을 통해 반환했던 인스턴스 삭제
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class IteratorCollection {
public static void main(String[] args) {
List<String> list = new LinkedList<>();
list.add("Toy");
list.add("Box");
list.add("Robot");
list.add("Box");
Iterator itr = list.iterator(); // 반복자 처음 획득
// 반복자를 이용한 순차적 참조
while (itr.hasNext()) {
System.out.println(itr.next() + "\t");
}
System.out.println();
itr = list.iterator(); // 반복자 다시 획득
// 모든 "Box" 삭제
while (itr.hasNext()) {
if (itr.next().equals("Box")) {
itr.remove();
}
}
itr = list.iterator(); // 반복자 다시 획득
// 삭제 후 결과 확인
while (itr.hasNext()) {
System.out.println(itr.next() + "\t");
}
System.out.println();
}
}
- 배열보다는 컬렉션 인스턴스가 좋다. : 컬렉션 변환
첫 번째로 인스턴스의 저장과 삭제가 편하다.
두 번째로 ‘반복자’를 쓸 수 있다.
단, 배열처럼 ‘선언과 동시에 초기화’를 할 수 없어서 다음과 같은 방법을 써준다.
// 인자로 전달된 인스턴스들을 저장한 컬렉션 인스턴스의 생성 및 반환
List<String> list = new Arrays.asList("Toy", "Robot", "Box");
하지만 이렇게 생성된 컬렉션 인스턴스는 immutable하다.
따라서 새로운 인스턴스의 추가나 삭제가 필요한 상황이라면 다음 생성자를 기반으로 ArrayList 인스턴스를 생성해야 한다.
- public ArrayList(Collection<? extends E> c)
-> Collection을 구현한 컬렉션 인스턴스를 인자로 전달받는다.
-> 그리고 E는 인스턴스 생성 과정에서 결정되므로 무엇이든 될 수 있다.
-> 덧붙여서 매개변수 c로 전달된 컬렉션 인스턴스에서는 참조만(꺼내기만) 가능하다.
public static void main(String[] args) {
List<String> list = Arrays.asList("Toy", "Box", "Robot");
list = new ArrayList<>(list); // 생성자
}
23-3. Set 인터페이스를 구현하는 컬렉션 클래스들
- Set을 구현하는 클래스의 특성과 HashSet 클래스
Set 인터페이스를 구현하는 제네릭 클래스는 다음 두 가지 특징이 있다.
1) 저장 순서가 유지되지 않는다.
2) 데이터의 중복 저장을 허용하지 않는다.
import java.util.HashSet;
class Num {
private int num;
public Num(int n) { num = n; }
@Override
public String toString() {
return String.valueOf(num);
}
}
public class HashSetEqualityOne {
HashSet<Num> set = new HashSet<>();
set.add(new Num(7799));
set.add(new Num(9955));
set.add(new Num(7799)); // 같은 인스턴스일 것이라고 기대
System.out.println("인스턴스 수: " + set.size()); // 3 -> 중복 무시가 안 됨
for (Num n : set)
System.out.println(n.toString());
}
같은 인스턴스일 것이라고 기대하고 중복이 제거되어 Set에 들어갈 것이라 예상했지만, 모든 인스턴스가 들어갔다.
HashSet이 판단하는 동일 인스턴스의 기준은 Object 클래스에 정의되어 있는 다음 두 메소드의 호출 결과를 근거로 한다.
public boolean equals(Object obj)
public int hashCode()
두 인스턴스가 hashCode 메소드 호출 결과로 반환하는 값이 동일해야 한다.
그리고 이어서 두 인스턴스를 대상으로 equals 메소드의 호출 결과 true가 반환되면 동일 인스턴스로 간주한다.
- 해쉬 알고리즘과 hashCode 메소드
Set은 들어오는 데이터가 기존에 있는 데이터인지 검사해야한다.
모든 데이터와 비교연산을 하기엔 데이터가 많아질 수록 성능적으로 좋지 않기 때문에 데이터들을 어느정도 분류해놓으면 탐색 시간을 획기적으로 줄일 수 있다.
만약 특정 데이터의 존재 여부를 확인하려면 가장 효율적인 방법은 그 데이터가 속하는 부류를 먼저 찾고, 그 안에서만 비교연산을 하는 것이다.
이로써 탐색 대상이 줄어들게 된다.
이처럼 HashSet에서 동일 인스턴스의 존재 여부를 확인하는 것은 다음 두 단계를 거친다.
1) Object 클래스에 정의된 hashCode 메소드의 반환 값을 기반으로 부류 결정
2) 선택된 부류 내에서 equals 메소드를 호출하여 동등 비교
다시 돌아와서, 사용자가 직접 정의한 클래스의 인스턴스가 동일한지 기준을 정하기 위해 hashCode와 equals 메소드를 오버라이딩하여 정의해보자.
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
class Num {
private int num;
public Num(int n) {
num = n;
}
@Override
public String toString() {
return String.valueOf(num);
}
@Override
public int hashCode() {
return num % 3;
}
@Override
public boolean equals(Object o) {
return num == ((Num)o).num;
}
}
public class HashSetEqualityTwo {
public static void main(String[] args) {
Set<Num> set = new HashSet<>();
set.add(new Num(4444));
set.add(new Num(5555));
set.add(new Num(4444));
for (Iterator<Num> itr = set.iterator(); itr.hasNext();) {
System.out.println(itr.next());
}
}
}
- hashCode 메소드의 다양한 정의
hashCode를 정의할 땐 데이터들의 특성을 모두 반영하여 작성해야한다.
즉, 클래스를 정의할 때마다 hashCode를 정의하는 것은 꽤 번거로운 일이다.
그래서 자바에서는 다음 메소드를 제공하고 있다.
// java.util.Objects에 정의된 메소드, 전달된 인자 기반의 해쉬 값 반환
// java.lang.Object가 아니다. 헷갈리니 주의하자.
public static int hash(Object...values)
@Override
public int hashCode() {
return Objects.hash(model, color); // 전달 인자 model, color 기반 해쉬 값 반환
}
- TreeSet 클래스의 이해와 활용
TreeSet 클래스는 트리(Tree)라는 자료구조를 기반으로 인스턴스를 저장한다.
이는 정렬된 상태가 유지되면서 인스턴스가 저장됨을 의미한다.
인스턴스들의 참조 순서는 오름차순을 기준으로 한다.
그렇다면, 다음과 같이 인스턴스의 크고 작음을 정의하기 애매한 상황에서는 어떻게 할까?
class Person { // 이름과 나이 중 어떤 것을 기준으로 정렬해야할까?
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return String.format("%s(%d세)", name, age);
}
}
크고 작음에 대한 기준은 개발자가 결정할 일이다.
그래서 위와 같이 클래스를 정의할 때에 다음 인터페이스의 구현을 통해 크로 작음에 대한 기준을 정해주어야 한다.
public interface Comparable<T> // 이 인터페이스에 위치한 유일한 추상 메소드 int compareTo(T o)
- 인스턴스의 비교 기준을 정의하는 Comparable 인터페이스의 구현 기준
Comparable 인터페이스를 구현할 때 정의해야 할 추상 메소드는 다음과 같다.
int campareTo(T o)
이 메소드는 다음과 같이 정의하면 된다. 이는 일종의 약속이다.
- 인자로 전달된 o가 작다면 양의 정수 반환
- 인자로 전달된 o가 크다면 음의 정수 반환
- 인자로 전달된 o가 같다면 0을 반환
import java.util.Set;
import java.util.TreeSet;
/**
나이가 적으면 앞으로 오도록 만들 것!
*/
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return String.format("%s (%d)", name, age);
}
@Override
public int compareTo(Person person) {
return this.age - person.age;
}
}
public class ComparablePerson {
public static void main(String[] args) {
Set<Person> treeSet = new TreeSet<>();
treeSet.add(new Person("Yoon", 37));
treeSet.add(new Person("Hong", 53));
treeSet.add(new Person("Park", 22));
for (Person person : treeSet) {
System.out.println(person);
}
}
}
- Comparator 인터페이스를 기반으로 TreeSet의 정렬 기준 제시하기
위의 예제에서 나이가 적은 사람이 앞족에 위치하도록 compareTo 메소드를 구현해보았다.
만약 나이가 많은 사람이 앞쪽에 위치하도록 기준을 바꿔야한다면 어떻게 해야할까?
물론 메소드의 내용을 수정하면 되지만, 일시적인 기준 변경이라면 메소드를 수정하는 일은 적절치 않다.
그리고 이런 상황을 고려하여 다음 인터페이스가 제공된다.
public interface Comparator<T> // int compare(T o1, T o2)의 구현을 통해 정렬 기준을 결정할 수 있다.
이 인터페이스를 구현한 클래스의 인스턴스는 TreeSet
// TreeSet 인스턴스를 만들 때, '정렬'에 대한 기준 정보도 같이 전달해줄 수 있음.
public TreeSet(Comparator<? super E> comparator)
그리고 compare 메소드의 정의 기준은 다음과 같다.
int compare(T o1, T o2)
- o1이 o2보다 크면 양의 정수 반환
- o1이 o2보다 작으면 음의 정수 반환
- o1이 o2보다 같다면 0 반환
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return String.format("%s (%d)", name, age);
}
@Override
public int compareTo(Person person) {
return this.age - person.age;
}
}
class PersonComparator implements Comparator<Person> {
public int compare(Person p1, Person p2) {
return p2.age - p1.age; // 나이가 많은 사람을 앞에 세우는 연산
}
}
public class ComparatorPerson {
public static void main(String[] args) {
Set<Person> tree = new TreeSet<>(new PersonComparator());
tree.add(new Person("Yoon", 37));
tree.add(new Person("Hong", 53));
tree.add(new Person("Park", 22));
for (Person person : tree) {
System.out.println(person);
}
}
}
- 중복된 인스턴스를 삭제하려면
List를 구현하는 클래스는 인스턴스의 중복 삽입을 허용한다.
이렇게 중복 삽입된 인스턴스들을 하나만 남기고 모두 지워야 한다고 가정하면 어떻게 처리할 수 있을까?
Set을 활용해보자!
import java.util.*;
public class ConvertCollection {
public static void main(String[] args) {
// 중복이 포함된 리스트
List<String> list = Arrays.asList("Box", "Toy", "Box", "Toy");
// 중복을 제거하기위해 Set으로 타입 변환
Set<String> set = new HashSet<>(list);
// 중복이 제거된 Set으로 List를 만듬
List<String > new_list = new ArrayList<>(set);
}
}
23-4. Queue 인터페이스를 구현하는 컬렉션 클래스들
- 스택(Stack)과 큐(Queue)의 이해
Stack: 가장 먼저 저장된 데이터가 가장 마지막에 나오는 자료구조이다.
LIFO(last-in-first-out) -> 먼저 저장된 데이터가 마지막에 빠져나간다.
Queue: 들어간 순으로 빠져나오는 자료구조이다.
FIFO(first-in-first-out) -> 먼저 저장된 데이터가 먼저 빠져나간다.
- Queue 인터페이스와 큐(Queue)의 규현
큐 자료구조를 위한 Queue 인터페이스를 대표하는 세 가지 메소드는 다음과 같다.
boolean add(E e) // 넣기
E remove() // 꺼내기
E element() // 확인하기
위의 메소드들은 꺼낼 인스턴스가 없거나 저장 공간이 부족할 때 예외를 발생시킨다.
반면, 해당 상황에 특정값(null 또는 false)를 반환하는 메소드도 있다.
boolean offer(E e) // 넣기, 넣을 공간이 부족하면 false를 반환
E poll() // 꺼내기, 꺼낼 대상 없으면 null 반환
E peek() // 확인하기, 확인할 대상 없으면 null 반환
일반적인 선택은 offer, poll, peek이다.
비어있는 상황까지도 예외가 아닌 프로그램의 정상적인 흐름으로 간주하는 경우가 대부분이기 때문이다.
- 스택(Stack)의 구현
자바도 Stack을 지원한다.
하지만 자바 초기에 정의된 클래스로써 지금은 이전 코드와의 호환성 유지를 위해 존재하는 클래스일 뿐이라고 한다.
Stack은 동기화된 클래스로 멀티 쓰레드에 안전하지만, 그만큼 성능의 저하가 발생하기 때문에 대신에 자바 6에서 스택을 대신할 수 있는 Dequq이라는 자료구조를 살펴보도록하자.
Deque의 대표 메소드는 다음과 같다.
// 앞으로 넣고, 꺼내고, 확인하기
void addFirst(E e) // 넣기
E removeFirst() // 꺼내기
E getFirst() // 확인하기
// 뒤로 넣고, 꺼내고, 확인하기
void addLast(E e) // 넣기
E removeLast() // 꺼내기
E getLast() // 확인하기
마찬가지로 예외 대신 특정 값을 반환하는 메소드들도 있다.
// 앞으로 넣고, 꺼내고, 확인하기
boolean offerFirst(E e) // 넣기, 공간 부족하면 false 반환
E pollFirst() // 꺼내기, 꺼낼 대상 없으면 null 반환
E peekFirst() // 확인하기, 확인할 대상 없으면 null 반환
// 뒤로 넣고, 꺼내고, 확인하기
boolean offerLast(E e) // 넣기, 공간 부족하면 false 반환
E pollLast() // 꺼내기, 꺼낼 대상 없으면 null 반환
E peekLast() // 확인하기, 확인할 대상 없으면 null 반환
따라서 Deque을 스택처럼 사용하고 싶으면, 넣고 빼낼 방향을 하나로 고정시키면 된다.
offerFirst & pollFirst -> 앞으로 넣고 앞에서 꺼내기
offerLast & pollLast -> 뒤로 넣고 뒤에서 꺼내기
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeCollection {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>(); // Deque<String> deque = new LinkedList<>();
// 앞으로 넣기
deque.offerFirst("1. Box");
deque.offerFirst("2. Toy");
deque.offerFirst("3. Robot");
// 앞에서 빼기
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
}
}
(참고)
Deque 인터페이스에는 push랑 pop 메소드가 있고, Deque을 구현하는 LinkedList랑 ArrayDeque에는 이 메소드가 이미 구현되어있다.
따라서, Deque을 Stack으로 활용하고자 한다면, 그냥 push랑 pop을 활용해도 된다.
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeCollection {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>(); // Deque<String> deque = new LinkedList<>();
deque.push("1. Box");
deque.push("2. Toy");
deque.push("3. Robot");
System.out.println(deque.pop());
System.out.println(deque.pop());
System.out.println(deque.pop());
}
}
23-5. Map<K, V> 인터페이스를 구현하는 컬렉션 클래스들
- Key-Value 방식의 데이터 저장과 HashMap 클래스
Collection을 구현하는 클래스가 Value를 저장하는 구조였다면,
Map을 구현하는 클래스는 Value를 저장할 때, 이를 찾을 때 사용하는 Key를 함께 저장하는 구조이다.
Key는 지표이므로 중복될 수 없다. 반면Key만 다르면Value는 중복되어도 상관없다.
Map을 구현하는 대표 클래스로는 HashMap과 TreeMap이 있다.
둘의 가장 큰 차이점은 트리 자료구조를 기반으로 구현된 TreeMap은 정렬 상태(Key를 기준으로)를 유지한다는데 있다.
import java.util.HashMap;
import java.util.Map;
public class HashMapCollection {
public static void main(String[] args) {
Map<Integer, String> map = new HashMap<>();
// Key-Value 기반 데이터 저장
map.put(45, "Brown");
map.put(37, "James");
map.put(23, "Martin");
// 데이터 탐색
System.out.println(map.get(45));
System.out.println(map.get(37));
System.out.println(map.get(23));
// 데이터 삭제
map.remove(37);
// 데이터 삭제 확인
System.out.println("37번: " + map.get(37));
}
}
- HashMap의 순차적 접근 방법
HashMap 클래스는 Iterable 인터페이스를 구현하지 않으니 for-each문이나, 반복자를 얻어서 값에 순차적으로 접근할 수 없다.
다만, keySet 메소드를 통해 Key를 담은 Set을 생성해서 Value에 접근할 수 있다.
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
public class HashMapIteration {
public static void main(String[] args) {
Map<Integer, String> map = new HashMap<>();
map.put(45, "Brown");
map.put(37, "James");
map.put(23, "Martin");
// Key만 담고 있는 컬렉션 인스턴스 생성
Set<Integer> ks = map.keySet();
// Key와 Value를 출력(for-each문 기반)
for (Integer age: ks) {
System.out.println(age + " -> " + map.get(age));
}
System.out.println();
// Key와 Value를 출력(반복자 기반)
for (Iterator itr = ks.iterator(); itr.hasNext(); ) {
Integer age = (Integer) itr.next();
System.out.println(age + " -> " + map.get(age));
}
}
}
- TreeMap의 순차적 접근 방법
TreeMap은 트리 자료구조를 기반으로 구현되어 있어서 정렬 상태를 유지한다.
전에 작성한 코드에서 Map만 TreeMap으로 바꾸고 결과를 비교해보자.
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapIteration {
public static void main(String[] args) {
Map<Integer, String> map = new TreeMap<>(); // TreeMap으로 바꿈
map.put(45, "Brown");
map.put(37, "James");
map.put(23, "Martin");
// Key만 담고 있는 컬렉션 인스턴스 생성
Set<Integer> ks = map.keySet();
// Key와 Value를 출력(for-each문 기반)
for (Integer age: ks) {
System.out.println(age + " -> " + map.get(age));
}
System.out.println();
// Key와 Value를 출력(반복자 기반)
for (Iterator itr = ks.iterator(); itr.hasNext(); ) {
Integer age = (Integer) itr.next();
System.out.println(age + " -> " + map.get(age));
}
}
}
댓글 남기기