[자바의 정석]11. 컬렉션 프레임웍-2

1.7 Comparator와 Comparable

• Arrays.sort()를 사용할때 해당 Array의 요소에 Comparable 구현에 의해 정렬되는 것이다.
• Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있다.
• Comparable 구현 클래스
  • Integer와 같은 Wrapper 클래스와 String, Date, File 등
  • 기본적으로 오름차순

public interface Comparator{
	int compare(Object o1, Object o2);
	boolean equals(Object o);
}

public interface Comparable{
	int compareTo(Object o);
}

• Comparable은 java.lang 패키지에 Comparator은 java.util 패키지에 있다.
• compare()과 compareTo()는 두 객체를 비교한다는 같은 기능을 목적으로 둔다.
• compareTo()의 반환값은 int지만, 실제로는 두 객체가 같으면 0, 비교하는 값보다 작으면 음수, 크면 양수를 반환
• compare()도 같이 동작한다.
• TreeSet도 compareTo 메서드를 사용한다.
• Comparator가 익명클래스, 내림차순 등에 사용된다.

Comparable: 기본 정렬 기준을 구현하는데 사용
Comparator: 기본 정렬 기준 외에 다른 기준으로 정렬하고자할 때 사용

• Arrays.sort(arr, Comparator c) Comparator에 의해 정렬된다.
• 뒤에 Comparator가 없다면, arr에 저장된 객체가 구현한 Comparable에 의해 정렬된다.

<String의 Comparator>

• 주로 사전순(공백, 숫자, 대문자, 소문자) 순으로 정렬된다.
  • 대소문자 구분하고 싶지 않다면 Arrays.sort(arr, String.CASE_INSENSITIVE_ORDER)
  • 내림차순 하고싶다면 compare()에서 결과값에 -1을 곱해주면 된다.

 

1.8 HashSet

• Set 인터페이스를 구현한 가장 대표적인 컬렉션
• 중복 비허용, 데이터 저장 순서 비유지
• 요소 추가시, add나 addAll을 사용하는데 중복된 요소를 추가하고자 한다면 return 값이 false가 된다.
• 저장 순서를 유지하고 싶다면 LinkedHashSet 사용
• HashSet은 내부적으로 HashMap을 이용해 만들어짐.
  • hashing을 이용해 구현했다.
• Object의 hashCode()는 객체의 주소로 이루어져있다.
  • 객체의 주소는 중복될 수 없다.

List<Object> list = new LinkedList<>();
list.add("1");
list.add(new Integer(1));
Set<Object> set = new HashSet<>(list);
System.out.println(set)
// [1,1];
// 0번째 1은 String, 1번째 1은 Integer이다. == 중복이 아니다.

• 컬렉션 정렬은 Collections.sort()를 사용한다.

<HashSet 객체 비교>

• HashSet의 add 메서드는 새로운 요소를 추가하기 전 기존에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출한다.
  • HashSet에서 프로그래머가 생성한 객체를 비교하기 위해서는 equals()와 hashCode()를 오버라이딩 해야한다.

public boolean equals(Object o){
	if(o instanceof User){
		User u = (User)o;
		return Object.equals(name, u.name) && Object.equals(age, u.age);
	}
	return false;
}

public int hashCode(){
	//return (name + age).hashCode(); // String의 hashCode()를 사용한다. 문자열 내용으로 해시코드 생성
	return Object.hash(name, age) // JDK 1.8부터 Object 클래스의 hash()를 사용해 작성할 수 있다.
}

<오버라이딩된 해시코드>

1. 실행 중인 어플리케이션 내의 동일한 객체에 대해 여러번 hashCode()를 호출해도 동일한 int값을 반환해야 한다.
   1. 단, 실행시마다 동일한 int값을 반환할 필요는 없다.
   2. String 클래스의 hashCode()는 문자열을 기반으로 해시코드를 생성해 항상 같은 값을 반환
   3. Object 클래스의 hash()는 바뀔 수 있음
2. equals 메서드를 이용한 비교에서 true를 얻은 두 객체에 대해 각각 hashCode()를 호출해 얻은 결과는 반드시 같아야 한다.
   1. equals()가 true이면 hashCode()가 동일하다.
3. equals()를 호출했을 때, false를 반환하는 두 객체는 hashCode()에 대해 같은 int값을 반환하는 경우가 있을 수 있지만, hashing을 사용하는 컬렉션의 성능 향상을 위해 다른 int를 반환하는 것이 좋다.

 

1.9 TreeSet

• 전위 순회
  • Root - L - R
• 중위 순회
  • L - Root - R
• 후위 순회
  • L - R - Root
• 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터 저장
• 이진 검색 트리는 정렬, 검색, 범위검색에 높은 성능을 보인다.
• TreeSet은 이진 검색 트리의 성능을 향상시킨 ‘레드-블랙 트리’로 구현되어 있다.
• Set 인터페이스로 구현해 중복된 데이터 비허용, 정렬된 위치에 바로 저장해 저장순서 비유지
• 이진 크리는 링크드 리스트처럼 여러 개의 노드가 서로 연결된 구조
  • 각 노드에 최대 2개의 노드를 연결할 수 있음
  • 루트라는 하나의 노드에서 계속해서 확장된다.
  • 하나의 부모 노드는 0,1,2개의 자식노드를 가질 수 있다.
• 검색 O(longN)

class TreeNode{
	TreeNode left; // 왼쪽 자식 노드
	Object element; // 객체 저장을 위한 참조변수
	TreeNode right; // 오른쪽 자식 노
}

• 첫번째로 저장되는 값이 루트가 되고, 비교하면서 트리를 따라 내려간다.
• 작은 값은 왼쪽에 큰 값을 오른쪽에 저장한다.
• 왼쪽 마지막 레벨 == 가장 작은 값, 오른쪽 마지막 레벨 == 가장 큰 값
• TreeSet에 저장되는 객체는 Comparable을 구현하든 TreeSet에게 Comparator를 제공해야 한다.

<TreeSet의 기능>

• 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색이 매우 빠르다.
• 트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아 저장해야하므로 삭제의 경우 트리 일부를 재구성해야 한다.
  • 링크드 리스트보다 데이터의 추가/삭제 시간이 더 걸린다.
  • 대신 배열이나 링크드 리스트에 비해 검색과 정렬기능이 뛰어나다.

이진 검색 트리는
- 모든 노드는 최대 두개의 자식을 가짐
- 왼쪽 자식 노드의 값은 부모 노드보다 작고 오른쪽 자식 노드는 부모 노드보다 크다.
- 노드의 추가, 삭제에 시간이 걸린다.(순차 저장이 아님)
- 검색(범위 검색)과 정렬에 유리하다.
- 중복된 값을 저장하지 못한다.

 

1.10 HashMap과 Hashtable

• Hashtable과 HashMap의 관계는 Vector와 ArrayList의 관계와 같다.
• HashMap을 사용해라.
• HashMap은 Map의 구현체로 key-value의 한 쌍으로 값을 저장하고 key는 중복 비허용, value는 중복을 허용한다. 저장 순서 비유지.
• hashing을 사용해 데이터 검색에 뛰어난 성능을 가진다.

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
	transient Node<K,V>[] table;
	...
	static class Node<K,V> implements Map.Entry<K,V> {
		final int hash;
		final K key;
		V value;
		...
	}
	...
}		

• key와 value는 서로 관련된 값이기 때문에 Node로 묶어 하나의 클래스로 정의해 사용한다.
• 하나의 배열로 다루는 것이 데이터의 무결성을 지키기에 바람직하다.

키(key): 컬렉션 내의 key 중 유일해야 한다.
값(value): 키(key)와 달리 데이터의 중복을 허용한다.

• key는 저장된 값을 찾는데 사용되기 때문에 유일해야한다.
• +) Hashtable은 key나 value로 NULL을 허용하지 않지만, HashMap은 Null이 허용된다.
  • map.get(null);, map.put(null, null);가능

<해싱과 해시함수>

• 해싱(hashing)이란 해시함수(hash function)를 이용해 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다.
• 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 검색에 적합하다.
• 해싱에서 사용하는 자료구조는 배령과 링크드 리스트 조합으로 되어있다.

<해싱 검색 순서>

1. 검색하고자 하는 값의 키로 해시함수 호출
2. 해시함수의 계산결과(해시코드)로 해당 값이 저장되어있는 링크드 리스트를 찾는다.
3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.

• 해싱에서 가장 중요한것이 해시함수의 알고리즘이다.

 

1.11 TreeMap

• 이진 검색 트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다.
• 검색과 정렬에 적합한 컬렉션 클래스이다.
• 검색의 경우 HashMap이, 범위검색이나 정렬이 필요한 경우 TreeMap이 좋다.

 

1.12 Properties

• HashMap의 구버전인 Hashtable을 상속받아 구현한 것.
• Hashtable은 키와 값을 (Object, Object)의 형태로 저장하는데, Properties는 (String, String)의 형태로 저장하는 보다 단순화된 컬렉션
• 주로 애플리케이션의 환경설정과 관련된 속성을 저장하는데 사용되며
• 데이터를 파일로부터 읽고 쓰는 편리한 기능 제공
• key와 같은 값이 없는 경우 null을 반환한다.
• .getProperties(”key값”)

 

1.13 Collections

• Arrays가 배열과 관련된 메서드를 제공하는 것처럼, Collections는 컬렉션과 관련된 메서드를 제공한다.

<컬렉션의 동기화>

• 멀티 쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시에 접근할 수 있기 때문에 데이터의 일관성(consistency)을 유지하기 위해 공유되는 객체에 동기화(synchronization)가 필요하다.
• Vector와 Hashtable과 같은 구버전은 자체적으로 동기화 처리가 되어있는데, 멀티쓰레드 환경이 아닐 경우 성능을 낮춘다.
• 그래서 ArrayList와 HashMap과 같은 컬렉션은 동기화를 자체적으로 처리하지 않고 필요한 경우에만 Collections 클래스의 동기화 메서드를 이용해 동기화 처리가 가능하도록 변경했다.
  • synchronizedXXX(Collection c); // XXX에는 Collection명이 들어간다.

<변경불가 컬렉션 만들기>

• 컬렉션에 저장된 데이터를 보호하기 위해서 컬렉션을 변경할 수 없게, 읽기 전용으로 만들어야 할 수 있다.
• 주로 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유하다보면 데이터가 손상될 수 있다. 이를 방지하기 위해 아래 메서드를 사용한다.
  • unmodifiableXXX(Collection c)

<싱글톤 컬렉션 만들기>

• 단 하나의 객체만 저장하는 컬렉션을 만들고 싶은 경우
  • singletonXXX(Collection c)

<한 종류의 객체만 저장하는 컬렉션 만들기>

• 컬렉션에 모든 종류의 객체를 저장할 수 있는 것은 장점이기도 하고 단점이기도 하다.
• 대부분의 경우 한 종류의 객체를 저장한다.
• 컬렉션에 지정된 종류의 객체만 저장할 수 있도록 제한하고 싶을 때
  • checkedXXX(Collection c, Class type);

💡 제너릭스로 모두 간단하게 처리할 수 있다. 있는 이유는 호환성 때문에

 

1.14 컬렉션 클래스 정리 & 요약

컬렉션	특징
ArrayList	배열기반, 데이터의 추가와 삭제에 불리, 순차적인 추가삭제는 제일 빠름. 임의의 요소에 대한 접근성이 뛰어남.
LinkedList	연결기반. 데이터의 추가와 삭제에 유리. 임의의 요소에 대한 접근성이 좋지 않음
HashMap	배열과 연결이 결합된 형태. 추가, 삭제, 검색, 접근성이 모두 뛰어남. 검색에는 최고의 성능을 보임.
TreeMap	연결기반. 정렬과 검색(특히 범위검색)에 적합. 검색성능은 HashMap보다 떨어짐
Stack	Vector를 상속받아 구현
Queue	LinkedList가 Queue인터페이스를 구현
Properties	Hashtable을 상속받아 구현
HashSet	HashMap를 이용해서 구현
TreeSet	TreeMap을 이용해서 구현
LinkedHashMap    LinkedHashSet	HashMap과 HashSet에 저장순서유지기능을 추가