컬렉션 프레임웍 2

Java의 정석 의 책을 읽고 정리한 내용입니다.

 

📖 G. Comparator와 Comparable

• Comparable을 구현한 클래스들이 기본적으로 오름차순으로 정렬되어 있지만 , 내림차순으로 정렬한다던가 아니면 다른 기준에 의해서 정렬되도록 하고 싶을 때 Comparator를 구현해서 정렬기준에 제공할 수 있다.

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

import java.util.*;

public class CompartorEx {

	public static void main(String[] args) {
			String[] strArr = {"cat", "Dog", "lion", "tiger"};
			
			Arrays.sort(strArr); // String의 comrable구현에 의한 정렬
			System.out.println("strArr="+Arrays.toString(strArr));
			
			Arrays.sort(strArr, String.CASE_INSENSITIVE_ORDER); // 대소문자 구분안함
			System.out.println("strArr="+Arrays.toString(strArr));
			
			Arrays.sort(strArr, new Desending()); // 역순정렬
			System.out.println("strArr="+Arrays.toString(strArr));
			
	}


}

class Desending implements Comparator{
	public int compare(Object o1, Object o2){
		if(o1 instanceof Comparable && o2 instanceof Comparable){
			Comparable c1 = (Comparable)o1;
			Comparable c2 = (Comparable)o2;
			return c1.compareTo(c2) * -1;  // -1을 곱해서 기본 정렬 방식의 역으로 변경한다.
											// 또는 c2.compareTo(c1)와 같이 순서를 바꿔도 된다.
		}
		return -1;
	}
}

strArr=[Dog, cat, lion, tiger]
strArr=[cat, Dog, lion, tiger]
strArr=[tiger, lion, cat, Dog]

• Arrays.sort()는 배열을 정렬할 때, Comparator를 지정해주지 않으면 저장하는 객체(주로 Comparable을 구현한 클래스의 객체)에 구현된 내용에 따라 정렬된다.

static void sort(Object[] a) // 객체 배열에 저장된 객체가 구현한 Comparable에 의한 정렬
static void sort(Object[] a, Compartor c) // 지정한 Comparator에 의한 정렬

 

📖 H. HashSet

• HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다.
• ArrayList와 같이 List인터페이스를 구현한 컬렉션과 달리 HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet()을 사용해야 한다.
• HashSet은 내부적으로 hashMap을 이용해서 만들어어 졌으며, HashSet이라는 이름은 해싱(hashing)을 이용해서 구현했기 때문에 붙여진 것이다!

 

생성자 또는 메서드	설명
HashSet()	HashSet객체를 생성한다.
HashSet(Collection c)	주어진 컬렉션을 포함하는 HashSet객체를 생성한다.
HashSet(int initialCapacity)	주어진값을 초기용량으로 하는 HashSet객체를 생성한다.
HashSet(int initialCapacity, float loadFactor)	초기 용량과 load factor를 지정하는 생성자
boolean add(Object o)	새로운 객체를 저장한다.
boolean addAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 추가한다.(합집합)
void clear()	저장된 모든 객체를 삭제한다.
Object clone()	HashSet을 복제해서 반환한다. (얕은복사)
boolean contains(Object o)	지정된 객체를 포함하고 있는지 알려준다.
boolean containsAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 포함하고 있는지 알려준다.
boolean isEmpty()	HashSet이 비어있는지 알려준다.
Iterator iterator()	Iterator를 반환한다.
boolean remove(Object o)	지정된 객체를 HashSet에서 삭제한다.(성공하면 true, 실패하면 false)
boolean removeAll(Collection c)	주어진 컬렉션에 저장된 모든 객체와 동일한 것들을 HashSet에서 모두 삭제한다(차집합)
boolea retainAll(Collection c)	주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 삭제한다.(교집합)
int size()	저장된 객체의 개수를 반환한다.
Object[] toArray()	저장된 객체들을 객체배열의 형태로 반환한다.
Object[] toArray(Object[] a)	저장된 객체들을 주어진 객체배열(a)에 담는다.

 

import java.util.*;

public class HashSetEx4 {

	public static void main(String[] args) {
		HashSet set = new HashSet();
		
		set.add(new String("abc"));
		set.add(new String("abc"));
		set.add(new Person2("David",10));
		set.add(new Person2("David",10));
		
		System.out.println(set);
	}

}

class Person2{
	String name;
	int age;
	
	Person2(String name, int age){
		this.name = name;
		this.age = age;
	}
	
	public boolean equals(Object obj){
		if(obj instanceof Person2){
			Person2 tmp = (Person2)obj;
			return name.equals(tmp.name) && age==tmp.age;
		}
		return false;
	}
	
	public int hashCode(){
		return (name+age).hashCode();
	}
	
	public String toString(){
		return name + ":"+age;
	}
}

• hashCode()는 String클래스의 hashCode()를 이용해서 구현했다.

 

🔔 오버라이딩을 통해 작성된 hashCode()
(1) 실행중인 애플리케이션 내의 동일한 객체에 대해서 여러 번 hashCode()를 호출해도 동일한 int값을 반환해야한다. 하지만 실행시마다 동일한 int값을 반환할 필요는없다.(단, equals메서드의 구현에 사용된 멤버변수의 값이 바뀌지 않았다고 가정한다.)
(2) equlas메서드를 이용한 비교에 의해서 true를 얻은 두 객체에 대해 각각 hashCode()를 호출해서 얻은 결과는 반드시 같아야 한다.
(3) equals메서드를 호출했을 때 false를 반환하는 두 객체는 hashCode()호출에 대해 같은 int값을 반환하는 경우가 있어도 괜찮지만, 해싱(hashing)을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int값을 반환하는 것이 좋다.

두 객체 equals : true이면 두 객체의 hashcode는 반드시 같아야 한다.
두 객체 hashcode : true이면 두 객체의 equals가 true일 수도 있고 false일 수도 있다.

 

import java.util.*;

public class HashSetEx5 {

	public static void main(String[] args) {
		HashSet setA   = new HashSet();
		HashSet setB   = new HashSet();
		HashSet setHab = new HashSet();
		HashSet setKyo =new HashSet();
		HashSet setCha = new HashSet();
		
		setA.add("1"); setA.add("2"); setA.add("3"); 
		setA.add("4"); setA.add("5");
		System.out.println("A ="+setA);
		
		setB.add("4"); setB.add("5"); setB.add("6");
		setB.add("7"); setB.add("8");
		System.out.println("B ="+setB);
		
		Iterator it = setB.iterator();
		while(it.hasNext()){
			Object tmp =it.next();
			if(setA.contains(tmp))
				setKyo.add(tmp);
		}
		
		it = setA.iterator();
		while(it.hasNext()){
			Object tmp =it.next();
			if(!setB.contains(tmp))
				setCha.add(tmp);
		}
		
		it = setA.iterator();
		while(it.hasNext())
			setHab.add(it.next());
		
		it = setB.iterator();
		while(it.hasNext())
			setHab.add(it.next());
		
		System.out.println("A ∪ B =" + setKyo);
		System.out.println("A ∩ B =" + setHab);
		System.out.println("A - B =" + setCha);
	}
}

A =[1, 2, 3, 4, 5]
B =[4, 5, 6, 7, 8]
A ∪ B =[4, 5]
A ∩ B =[1, 2, 3, 4, 5, 6, 7, 8]
A - B =[1, 2, 3]

 

📖 I. TreeSet

• TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스
• 이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보여주는 자료구조이다.
• TreeSet은 이진 검색 트리의 성능을 향상시킨 레드 - 블랙 트리(Red-Black tree)로 구현되어 있다.
• Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

 

이진 검색 트리(binary search tree)는
- 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
- 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
- 노드의 추가 삭제에 시간이 걸린다.(순차적으로 저장하지 않으므로)
- 검색(범위검색)과 정렬에 유리하다.
- 중복된 값을 저장하지 못한다.

 

생성자 또는 메서드	설명
TreeSet()	기본생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp)	주어진 정렬조건으로 정렬하는 TreeSet을 생성
TreeSet(SortedSet s)	주어진 SortedSet을 구현한 컬렉션을 저장하는 TreeSet을 생성
boolean add(Object o)	지정된 객체(o)를 Collection에 추가
boolean addAll(Collection c)	Collection(c)의 객체들을 Collection에 추가
Object ceiling(Object o)	지정된 객체와 같은 객체를 반환. 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
void clear()	지정된 모든 객체를 삭제한다.
Object clone()	TreeSet을 복제하여 반환한다.
Comparator comparator()	TreeSet의 정렬기준(Comparator)를 반환한다.
boolean contains(Object o)	지정된 객체가 포함되어 있는지를 확인한다.
boolean containsAll(Collection c)	Collection의 객체들이 포함되어 있는지 확인한다.
NavigableSet descendingSet()	TreeSet에 저장된 요소들을 역순으로 정렬해서 반환
Object first()	정렬된 순서에서 첫번째 객체를 반환한다.
Object floor(Object o)	지정된 객체와 같은 객체를 반환, 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
NavigableSet headSet(Object toElement, boolean inclusive)	지정된 객체보다 작은 값의 객체들을 반환, inclusive가 true이면, 같은 값의 객체도 포함
Object higher(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
boolean isEmpty()	TreeSet이 비어있는지 확인한다.
Iterator iterator()	TreeSet의 Iterator를 반환한다.
Object last()	정렬된 순서에서 마지막 객체를 반환한다.
Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체중 제일 가까운 값의 객체를 반환, 없으면 null
Object pollFirst()	TreeSet의 첫번째 요소(제일 작은 값의 객체)를 반환
Object pollLast()	TreeSet의 마지막 번째 요소(제일 큰 값의 객체)를 반환
booelan remove(Object o)	지정된 객체를 삭제한다.
boolean retainAll(Collection c)	주어진 컬렉션과 공통된 요소만을 남기고 삭제한다.(교집합)
int size()	저장된 객체의 개수를 반환한다.
Spliterator spliterator()	TreeSet의 spliterator를 반환
SortedSet subSet(Object fromElement, Object toElement)	범위 검색(fromElement와 toElement사이)의 결과를 반환한다.(끝 범위인 toElement는 범위에 포함되지 않음)
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	범위 검색의(fromElement와 toElement사이) 결과를 반환한다. (fromInclusize가 true면 시작값이 포함되고, toInclusive가 true면 끝 값이 포함된다.)
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.
Object[] toArray()	저장된 객체를 객체배열로 반환한다.
Object[] toArray(Object[] a)	저장된 객체를 주어진 객체배열에 저장하여 반환한다.

 

• TreeSet은 대문자가 소문자보다 우선한다.
• 대소문자가 섞여 있어야 하거나 다른 방식으로 정렬해야하는 경우 Comparator를 이용하면 된다.

import java.util.*;
public class TreeSetEx2 {

	public static void main(String[] args) {
		TreeSet set  = new TreeSet();
		int[] score = {80,95,50,35,45,65,10,100};
		
		for(int i=0; i<score.length; i++)
			set.add(new Integer(score[i]));
		
		System.out.println("50보다 작은값: "+set.headSet(new Integer(50)));
		System.out.println("50보다 큰값: "+set.tailSet(new Integer(50)));
		
	}

}

50보다 작은값: [10, 35, 45]
50보다 큰값: [50, 65, 80, 95, 100]

• hashSet에 메서드와 tailSet메서드를 이용하면 , TreeSet에 저장된 객체 중 지정된 기준 값보다 큰 값의 객체들과 작은 값의 객체들을 얻을 수 있다.

 

📖 J. HashMap과 Hashtable

• HashTable과 HashMap의 관계는 Vector과 ArrayList의 관계와 같아서 Hashtable보다는 새로운 버전인 HashMap을 사용한 것을 권한다.
• HashMap은 Map을 구현했으므로 앞에서 살펴본 Map의 특징 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다.
• 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
• HashMap은 키와 값을 각각 Object타입으로 저장한다.

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

 

HashMap의 생성자와 메서드

생성자 / 메서드	설명
HashMap()	HashMap 객체를 생성
HashMap(int initialCapacity)	지정된 값을 초기용량으로 하는 HashMap 객체를 생성
HashMap(int initialCapacity, float loadFactor)	지정된 초기용량과 load factor의 HashMap객체를 생성
hashMpa(Map m)	지정된 Map의 모든 요소를 포함하는 HashMap을 생성
void clear()	HashMap에 저장된 모든 객체를 제거
Object clone()	현재 HashMap을 복제해서 반환
boolean containsKey(Object key)	HashMap에 지정된 키(key)가 포함되어 있는지 알려준다. (포함되어 있으면 true)
boolean containsValue(Object value)	HashMap에 지정된 값(value)가 포함되어 있는지 알려준다. (포함되어 있으면 true)
Set entrySet()	HashMap에 저장된 키와 값을 엔트리(키와 값의 결합)의 형태로 Set에 저장해서 반환
Object get(Object key)	지정된 키(key)의 값(객체)을 반환, 못찾으면 null반환
Object getOrDefault(Object key, Object defalutValue)	지정된 키(key)의 값(객체)을 반환한다. 키를 못찾으면 키본값(defaultValue)로 지정된 객체를 반환
boolean isEmpty()	HashMap이 비어있는지 알려준다.
Set keySet()	HashMap에 저장된 모든 키가 저장된 Set을 반환
Object put (Object key, Object vlaue)	지정된 키와 값을 HashMap에 저장
Object remove(Object key)	HashMap에서 지정된 키로 저장된 값(객체)를 제거
Object replace(Object key, Object value)	지정된 키의 값을 지정된 객체(value)로 대체
boolean replace(Object key, Object oldValue, Object newValue)	지정된 키와 객체(oldValue)가 모두 일치하는 경우에만 새로운 객체(newValue)로 대체
int size()	HashMap에 저장된 요소의 개수를 반환
Collections values()	HashMap에 저장된 모든 값을 컬렉션의 형태로 반환

 

✔️ 해싱과 해시함수

• 해싱이란 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다.
• 해시 함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

 

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

• 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 된다.

 

배열은 배열의 크기가 커져도, 원하는 요소가 몇 번째에 있는지만 알면 아래의 공식에 의해서 빠르게 원하는 값을 찾을 수 있다.

배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size * n

• 서로 다른 두 객체에 대해 equlas()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다.