[Java] 컬렉션 프레임워크 (3)

이번 글에서는 Set, Map, TreeSet/TreeMap, Collections 유틸 클래스에 대해서 다뤄보겠습니다.

 

HashSet

Set 인터페이스는 순서가 없고 중복을 허용하지 않는 '집합'의 속성을 띄는 자료구조입니다.

그 중에서 HashSet은 Set 인터페이스를 구현한 대표적인 구현 클래스입니다.

 

HashSet은 중복을 허용하지 않기 때문에 객체를 저장하기 전에 기존의 컬렉션에 같은 객체가 있는지 먼저 확인합니다.

add(Object o) 메서드를 호출하면 저장할 객체의 equals()와 hashCode()를 호출하여 중복을 체크합니다.

단, equals()와 hashCode()는 아래의 코드와 같이 오버라이딩되어 있어야 합니다.

class Person {
	String name;
	int age;
	
	@Override	
	public int hashCode() {
		//Objects.hash()함수로 여러 인자들에 대한 해시코드(데이터가 저장된 실졔 메모리 주소)를 리턴
 		return Objects.hash(name, age);  //가변 인자
	}

	@Override
	public boolean equals(Object obj){
		if(!(obj instanceof Person)) return false;
		Person p = (Person)obj;
		
		return this.name.equals(p.name) && this.age == p.age;
	}
}

HashSet 이외에도 LinkedHashSet이 있는데, 순서가 유지되는 Set 자료구조라고 생각하면 됩니다.

 

다음은 Set 인터페이스에서 지원하는 메서드입니다.

교집합

setA.retainAll(setB);

 

합집합

setA.addAll(setB);

 

차집합

setA.removeAll(setB);

---

TreeSet

TreeSet은 이진 탐색 트리의 속성을 가진 Set 구현 클래스입니다.

 

이진 탐색 트리(Binary Search Tree)

자료구조에서 하나의 데이터 단위를 Node라고 합니다.

트리는 이러한 노드들이 LinkedList의 변형된 형태로, 하나의 부모 노드에 여러 자식 노드들이 계층형으로 연결되어 있는 구조입니다.

그 중에서 이진 탐색 트리는 모든 노드가 최대 2개의 자식 노드를 가지는 구조이며,

(왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)의 속성을 가집니다.

TreeSet에 데이터 추가하기

TreeSet 내부 데이터는 정렬된 상태를 유지하기 때문에, TreeSet에 객체를 넣기 위해선 아래의 두가지 방법이 있습니다.

1. 애초에 TreeSet 컬렉션 생성시 인자로 Comparator타입의 정렬 기준을 넣는다.

class TestComp implements Comparator{
	@Override
	public int compare(Object o1, Object o2){
		return 1;
	}
}

class Test { }  //빈 객체

Set set = new TreeSet(new TestComp());  //기준을 인자로 줌

for (int i = 0; set.size() < 6; i++) {
	set.add(new Test());
}

 

2. 컬렉션에 Comparable을 구현하는 객체를 넣는다.

Set set = new TreeSet();

for (int i = 0; set.size() < 6; i++) {
	int num = (int)(Math.random() * 45) + 1;  //1 ~ 45
	set.add(new Integer(num));  //wapper 객체는 내부적으로 Comparable을 구현한다
}

 

이진 탐색 트리의 장단점

이진 탐색 트리의 장점은 범위 탐색에 유리한 것입니다.

그림처럼 50 보다 작은 값을 구하려면 50을 기준으로 왼쪽에 연결된 모든 노드들을 리턴하는 headSet 메서드를 호출하면 됩니다.

그 밖에도 subSet(), tailSet() 등의 메서드가 있습니다.

set.subSet("b", "e");  //사전순으로 b와 e사이 모든 노드 탐색
set.headSet(50);
set.tailSet(50);

 

트리의 중위 순회를 이용하면 오름차순 정렬된 값을 얻을 수 있습니다.

트리의 중위 순회는 트리를 (왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드)순으로 출력하는 것을 말합니다.

이진 탐색 트리는 (왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)의 속성을 가진다고 했는데 중위 순회를 이용하면 정렬된 컬렉션을 얻을 수 있습니다.

 

그러나 단점은 데이터가 많아질수록 삽입/삭제시 시간이 점점 더 오래걸리는 것입니다.

이진 탐색 트리는 (왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)의 속성을 가지기 때문에,

데이터를 추가하려면 루트부터 계층적으로 차례 차례 값을 비교하여 알맞은 위치에 삽입해야 합니다.

그러나 데이터가 많아지면 많아질수록 계층적으로 비교해야할 횟수가 증가하게 됩니다.

---

Map

Map은 접근성이 좋은 Array와 변경이 유리한 LinkedList 두 가지가 조합된 자료구조입니다.

key와 그에 대응되는 value 한 쌍의 값이 저장되는 컬렉션이며,

순서가 없고 Key의 중복은 불가하지만, value의 중복은 허용하는 것이 특징입니다.

HashMap은 동기화를 지원하지않고 Hashtable은 동기화를 지원합니다.

 

HashMap

HashMap은 Map 인터페이스를 구현한 대표 클래스입니다.

해싱 기법을 이용하여 데이터를 저장, 검색하기 때문에 데이터 검색이 매우 빠릅니다.

put(key, value) 메서드를 이용해서 값을 저장합니다.

순서를 유지하려면 LinkedHashMap을 사용합니다.

 

해싱(Hashing)

해싱은 해시 함수(Hash Function)를 사용해서 HashMap에 데이터를 저장, 검색하는 것을 말합니다.

보통 Objects.hash()를 사용해서 해시 함수를 호출합니다.

 

특정 key에 대한 value를 검색하려면, 그림처럼 key를 인자로 해시 함수를 호출해서 해시 코드를 리턴 받습니다.

해시 코드를 이용해서 배열의 index에 접근하고 해당 위치에 연결된 LinkedList에서 key에 일치하는 데이터를 찾습니다.

 

해시 함수는 어떠한 Key에 대해 항상 같은 HashCode를 반환해야 합니다.

그러나 서로 다른 Key로 해시 함수를 통해 반환된 각각의 HashCode는 같을 수도 있습니다.

 

TreeMap

TreeMap은 이진 탐색 트리 속성을 가지는 Map 구현 클래스입니다.

---

Collections

Collections는 컬렉션을 다루기 위한 static 메서드를 제공하는 유틸 클래스입니다.

아래의 메서드들을 제공합니다.

• 컬렉션 채우기: fill()
• 컬렉션 복사: copy()
• 컬렉션 정렬: sort()
• 컬렉션 검색: binarySearch()

이 밖에도 다양한 메서드가 있습니다.

 

컬렉션 동기화

기존에 항상 동기화를 제공하는 Vector나 Hashtable과 다르게 synchronizedXXX() 메서드를 사용하면,

필요할 때만 동기화하여 성능을 개선할 수 있습니다.

List syncList = Collections.synchronizedList(new ArrayList(...));

 

ReadOnly(변경 불가) 컬렉션 만들기

unmodifiableXXX() 메서드를 사용하면, 변경 불가 컬렉션을 만들 수 있습니다.

List unmodifiableList = Collections.unmodifiableList(new ArrayList(...));

 

Singleton 컬렉션 만들기

singleton은 메모리에 오직 한 개의 객체만 존재하도록 하는 것을 말하며 singletonXXX() 메서드를 사용합니다.

List singletonList = Collections.singletonList(new ArrayList(...));

 

한 타입의 객체만 저장하는 컬렉션 만들기

checkedXXX() 메서드를 사용하면 컬렉션안에 타입을 통일시킬 수 있습니다.

그러나 JDK 1.5 버전 이후로 제네릭이 등장해서 지금은 사용하지 않습니다.

List list = new ArrayList();
List checkedList = Collections.checkedList(list, String.class);  //String만 저장 가능

---

정리

ArrayList: 배열 기반에 순차적 데이터 추가/삭제 유리(Stack)

LinkedList: 비순차적 데이터 추가/삭제 유리(Queue)

HashSet: 순서X, 중복X

HashMap/Hashtable: Array과 LinkedList를 합친 자료구조, 검색 기능 향상

TreeMap/TreeSet: 범위 검색, 정렬 기능 향상

 

 

 

Ref.

https://www.youtube.com/playlist?list=PLW2UjW795-f6xWA2_MUhEVgPauhGl3xIp

https://www.acmicpc.net/problem/18240

https://dlsdn73.tistory.com/402