Comparator & Comparable
-
Comparator(java.lang)와 Comparable(java.util)은 모두
인터페이스로컬렉션을 정렬하는데 필요한 메서드를 정의 -
Comparable을 구현하고 있는 클래스들은 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들, 주로 Integer와 같은 wrapper클래스와 String, Date, File과 같은 것들이며 기본적으로 오름차순, 즉 작은 값에서부터 큰 값의 순으로 정렬되도록 구현되어 있다.
-
Comparable을 구현한 클래스는 정렬이 가능하다는 것을 의미
public interface Comparator{
int compare(Object o1, Object o2);
boolean equals(Object obj);
}
public interface Comparable{
public int compareTo(Object o);
}compareTo()의 반환값은 int이지만 실제로는 비교하는 두 객체가 같으면 0, 비교하는 값보다 작으면 음수, 크면 양수를 반환하도록 구현해야한다.
compare()도 객체를 비교해서 음수, 0, 양수 중의 하나를 반환하도록 구현해야한다.
Integer 클래스의 일부
public final class Integer extends Number implements Comparable{
...
public int compareTo(Object o){
return compareTo((Integer)o);
}
public int compareTo(Integer anotherInteger){
int thisVal = this.value;
int anotherVal = anotherInteger.value;
// 비교하는 값이 크면 -1, 같으면 0, 작으면 1을 반혼한다.
return (thisVal<anotherVal ? -1 : (thisVal == anotherVal ? 0 :1));
}
...
}Comparable 기본 정렬기준을 구현하는데 사용
Comparator 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용
public int compareTo(Integer anotherInteger)
{
int thisVal = this.value;
int anotherVal = anotherInteger.value;
// 왼쪽 값이 크면 음수, 두값이 같으면 0, 왼쪽값이 크면 양수
return thisVal - anotherVal; // 내림 차순의 경우 반대로
} 즉 a.compareTo(b)에서 b가 크면 -1, 같으면 0, a가 크면 1
Array.sort()와 같은 메서드의 정렬 알고리즘은 이미 완벽 하므로, 우리는 사용 시 compareTo()를 구현하여 어떤 비교 기준으로 정렬 할지만 알려주면 됨
package ch11;
import java.util.*;
public class Ex11_7 {
public static void main(String[] args)
{
String[] strArr = {"cat", "Dog", "lion", "tiger"};
Arrays.sort(strArr); // String의 Comparable구현에 의한 정렬
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 Descending()); // 역순 정렬
System.out.println("strArr= " + Arrays.toString(strArr));
}
}
class Descending 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;
}
}
Arrays.sort()는 배열을 정렬할 때, Comparator를 지정해주지 않으면 저장하는 객체
(주로 Comparable을 구현한 클래스의 객체에 구현된 내용에 따라 정렬된다.)
static void sort(Object[] a) // 객체 배열에 저장된 객체가 구현한 Comparable에 의한 정렬
static void sort(Object[] a, Comparator c) //지정한 Comparator에 의한 정렬String의 Comparable구현은 문자열이 사전 순으로 정렬되도록 작성되어 있다.
-문자열의 오름차순 정렬은 공백, 숫자, 대문자, 소문자의 순으로 정렬되는 것을 의미
package ch11;
import java.util.*;
public class Ex11_8 {
public static void main(String[] args) {
Integer[] arr = {30, 50, 10, 40, 20};
Arrays.sort(arr); // Integer가 가지고 있는 기본 정렬 기준 compareTo()로 정렬.
System.out.println(Arrays.toString(arr));
Arrays.sort(arr, new DescComp());
System.out.println(Arrays.toString(arr));
}
}
class DescComp implements Comparator
{
public int compare(Object o1, Object o2)
{
if(!(o1 instanceof Integer && o2 instanceof Integer))
{
return -1;
}
Integer i = (Integer)o1;
Integer i2 = (Integer)o2;
return i.compareTo(i2) * -1;
}
}HashSet
HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스 특징대로 HashSet은 중복된 요소 저장 X
요소를 추가하기 위해 add or addAll()메서드 사용 시, 중복된 요소를 추가하고자 한다면 false return
저장 순서를 유지하고자 한다면 LinkedHashSet 사용해야 함
package ch11;
import java.util.*;
public class Ex11_9 {
public static void main(String[] args) {
// 1 하나는 String 하나는 Integer
Object[] objArr = {"1", new Integer(1), "2","2","3","3","4","4","4"};
Set set = new HashSet();
for(int i =0; i < objArr.length; i++)
{
set.add(objArr[i]);
}
//HashSet에 저장된 요소들을 출력한다.
System.out.println(set);
//HashSet에 저장된 요소들을 출력(Iterator이용)
Iterator it = set.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
}
}
중복되지 않는 로또 번호 생성
package ch11;
import java.util.*;
public class Ex11_10 {
public static void main(String[] args) {
Set set = new HashSet();
for(int i = 0; set.size() < 6; i++)
{
int num = (int)(Math.random() * 45) + 1;
set.add(new Integer(num));
}
/*
Collections 클래스의 sort(List list)를 사용했다. List인터페이스를 필요로 하기에
LinkedList의 생성자 LinkedList(Collection c)를 이용해서 HashSet에 저장된 객체들을
LinkedList에 담아서 처리
*/
List list = new LinkedList(set);
Collections.sort(list);
System.out.println(list);
}
}
package ch11;
import java.util.*;
public class Ex11_11 {
public static void main(String[] args) {
HashSet set = new HashSet();
set.add("abc");
set.add("abc");
set.add(new Person("David", 10));
set.add(new Person("David", 10));
System.out.println(set);
}
}
class Person{
String name;
int age;
Person(String name, int age){
this.name = name;
this.age = age;
}
public String toString() { return name + ":" + age;}
}
[David:10, abc, David:10]이름과 나이가 같으면 같은 사람으로 인식하도록 하려는 의도로 작성하였으나, 서로 다른 것으로 인식하는 것을 볼 수 있음
public boolean equals(Object obj)
{
if(!(obj instanceof Person)) return false;
// object엔 name이란 멤버가 없기에 형변환!
Person p = (Person)obj;
return this.name.equals(p.name) && this.age == p.age;
}
public int hashCode()
{
// Objects의 hash 메서드 이용, iv들을 인자로 사용
// int hash(Object... values) 가변 인자들
return Objects.hash(name,age);
}HashSet의 add메서드는 새로운 요소를 추가하기 전에 기존의 요소와 같은지 확인 하기 위해 equals()와 hashCode()를 호출하기 때문에 목적에 맞게 오버라이딩 해야함!
getter와 setter 만드는 것처럼 generate equals() and hashCode() 가능
package ch11;
import java.util.*;
public class Ex11_12 {
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]TreeSet
이진 탐색 트리(Binary search tree)라는 자료 구조의 형태로 데이터를 저장하는 컬렉션 클래스
이진 탐색 트리 -> 정렬, 검색, 범위검색에 높은 성능
TreeSet -> 이진 검색 트리의 성능을 향상시킨 Red-Black Tree로 구현
Set 인터페이스 구현 -> 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장 순서 유지 X
이진트리 예
class TreeNode{
TreeNode left; // 왼쪽 자식 노드
Object element; // 객체를 저장하기 위한 참조변수
TreeNode right; // 오른쪽 자식 노드
}왼쪽노드 -> 부모 노드 -> 오른쪽 노드 순으로 읽어오면 오름차순으로 정렬된 순서 얻음
3,7의 범위에 있는 값을 검색이 매우 빠름(범위 검색)
링크드 리스트 보다 데이터의 추가/삭제 시간은 더 걸리지만 검색과 정렬 기능 뛰어남!
-
첫 번째로 저장되는 값 -> 루트
-
두 번째 값은 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려감
-
왼쪽 레벨이
제일 작은 값, 오른쪽 마지막 레벨이제일 큰 값 -
컴퓨터는 알아서 값을 비교하지 못하므로 TreeSet에 저장되는 객체가
Comparable을 구현 하던가 아니면,Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 함 -> 안 할 시 예외 발생
로또 번호 생성기 예시
package ch11;
import java.util.*;
public class Ex11_14 {
public static void main(String[] args) {
// 이미 정렬을 하기에 따로 정렬할 필요 X
Set set = new TreeSet();
for(int i = 0; set.size() < 6; i++)
{
int num = (int)(Math.random() * 45) + 1;
set.add(num);
}
System.out.println(set);
Iterator st = set.iterator();
while(st.hasNext()) {
System.out.println(st.next());
}
}
}
[6, 13, 22, 27, 36, 41]
6
13
22
27
36
41
package ch11;
import java.util.*;
public class Ex11_15 {
public static void main(String[] args) {
TreeSet set = new TreeSet();
String from = "b";
String to = "d";
set.add("abc"); set.add("alien"); set.add("bat");
set.add("car"); set.add("Car"); set.add("disc");
set.add("dance"); set.add("dZZZZ"); set.add("dzzzz");
set.add("elephant"); set.add("elevator"); set.add("fan");
set.add("flower");
System.out.println(set);
System.out.println("range search : from: " + from+ " to: " + to);
System.out.println("result1 : " + set.subSet(from, to)); // 범위 검색
/*
d로 시작하는 단어까지 포함시키고자 한다 끝범위에 "zzz" 붙이면됨
d로 시작하는 단어 중 dzzz 다음에 오는 언어는 없을 거기 때문
왠만하면 대소문자 통일 해서 쓰자(대문자를 우선하기 때문)
*/
System.out.println("result1 : " + set.subSet(from, to + "zzz"));
}
}[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : from: b to: d
result1 : [bat, car]
result1 : [bat, car, dZZZZ, dance, disc]
set.headSet(new Integer(50)); -> 기준 값보다 작은 값들
set.tailSet(new Integer(50)); -> 기준 값보다 큰 값들
HashMap & Hashtable
Map 인터페이스를 구현하였기에 key와 value를 묶어서 하나의 데이터(entry)로 저장한다
해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 뛰어난 성능
HashMap 소스코드 일부
public class HashMap extends AbstractMap implements Map, Coneable, Serializable
{
transient Entry[] table;
...
static class Entry implements Map.Entry
{
final Object key;
Object value;
...
}
}
/* 키와 값은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각 배열로 선언하기 보단
하나의 클래스로 정의해서 하나의 배열로 다루는것이 무결성 측면에서 바람직하다*/키(key) : 컬렉션 내의 키 중에서 유일해야 한다(중복X) -> 일종의 아이디
값(value) : 키와 달리 데이터의 중복을 허용한다 -> 일종의 비밀번호
활용 예시
HashMap을 이용하여 id,pw 인증해보기
package ch11;
import java.util.*;
public class Ex11_16 {
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("myId", "1234");
map.put("asdf", "1111");
map.put("asdf", "1234"); // 이미 존재하는 키 추가 가능하지만 기존 값 없어짐
Scanner s = new Scanner(System.in);
while(true)
{
System.out.println("id와 password를 입력해주세요.");
System.out.print("id: ");
String id = s.nextLine().trim();
System.out.print("password :");
String password = s.nextLine().trim();
System.out.println();
if(!map.containsKey(id))
{
System.out.println("입력하신 id는 존재하지 않습니다. 다시 입력해주세요.");
continue;
}
if(!(map.get(id)).equals(password))
{
System.out.println("비밀번호가 일치하지 않습니다. 다시 입력해주세요.");
}else {
System.out.println("Id와 비밀번호가 일치합니다. ");
break;
}
}
}
}
id와 password를 입력해주세요.
id: asdf
password :1111
비밀번호가 일치하지 않습니다. 다시 입력해주세요.
id와 password를 입력해주세요.
id: asdf
password :1234
Id와 비밀번호가 일치합니다. HashMap은 키와 값으로 null 또한 허용한다
데이터 저장 및 읽기
package ch11;
import java.util.*;
public class Ex11_17 {
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("김자바", 90);
map.put("김자바", 100);
map.put("이자바", 100);
map.put("장자바", 80);
map.put("안자바", 90);
/*entrySet을 이용해서 map에 저장된 데이터를 읽어오는 방법을 보여줌 */
Set set = map.entrySet();
Iterator it = set.iterator();
while(it.hasNext()) {
Map.Entry e = (Map.Entry)it.next();
System.out.println("이름 : " + e.getKey() + ", 점수 : " + e.getValue());
}
set = map.keySet();
System.out.println("참가자 명단 : " +set);
Collection values = map.values();
it = values.iterator();
int total = 0;
while(it.hasNext()) {
int i = (int)it.next();
total += i;
}
System.out.println("총점 : " +total);
System.out.println("평균 : " +(float)total/set.size());
System.out.println("총점 : " +Collections.max(values));
System.out.println("총점 : " +Collections.min(values));
}
}
이름 : 안자바, 점수 : 90
이름 : 김자바, 점수 : 100
이름 : 이자바, 점수 : 100
이름 : 장자바, 점수 : 80
참가자 명단 : [안자바, 김자바, 이자바, 장자바]
총점 : 370
평균 : 92.5
총점 : 100
총점 : 80
HashMap을 이용하여 그래프 표현해보기
package ch11;
import java.util.*;
public class Ex11_18 {
public static void main(String[] args) {
String[] data = {"A","K","A","K","D","K", "A", "K", "K", "K", "Z", "D"};
HashMap map = new HashMap();
for(int i = 0; i < data.length; i++)
{
if(map.containsKey(data[i])) {
int value = (int)map.get(data[i]);
map.put(data[i], value + 1); // 기존에 있는 키는 기존 값에 1을 더해서 저장.
} else {
map.put(data[i], 1); // 기존에 없는 키는 값을 1에 저장.
}
}
Iterator it = map.entrySet().iterator(); // set형태에서 .iterator()
while(it.hasNext())
{
Map.Entry entry = (Map.Entry)it.next();
int value = (int)entry.getValue();
System.out.println(entry.getKey() + ": " + printBar('#', value) + "" + value);
}
}
public static String printBar(char ch, int value)
{
char[] bar = new char[value];
for(int i=0; i < bar.length; i++)
bar[i] = ch;
return new String(bar);
}
}
HashMap과 같이 해싱을 구현한 컬렉션 클래스들은 저장 순서를 유지하지 않는다
A: ###3
D: ##2
Z: #1
K: ######6해싱이란?
해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법
해시 함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 원하는 데이터 빠르게 찾을 수 있다
ex)HashSet, HashMap, HashTable
해싱에 사용하는 자료 구조 : 배열 + LinkedList의 조합
저장할 데이터의 키를 해시 함수에 넣으면 배열의 한 요소를 얻게되고, 다시 그곳에 연결되어 있는 Linked List에 저장하게 된다
데이터 찾는 과정
- 검색하고자하는 값의 키를
해시 함수로 호출 - 해시함수의 계산결과인
해시 코드를 이용해 해당 값이 저장되어 있는 LinkedList 찾음 - Linked List에서 검색하는 키와 일치하는 데이터를 찾게 됨
Collections의 메서드
동기화
java.util.Collection은 인터페이스
java.util.Collections는 클래스
멀티 쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시에 접근 할 수 있기 때문에 데이터 무결성 유지를 위해 공유되는 객체의 동기화(Synchronization)가 필요
Vector와 Hashtable과 같은 구버젼 클래스들을 자체적으로 동기화
-> 멀티쓰레드 프로그래밍이 아닌 경우 성능 저하
static Collection synchronizedCollection(Collection c)
static List synchronizedList(List list)
static Set synchronizedSet(Set s)
static Map synchronizedMap(Map m)
static SortedSet synchronizedSortedSet(SortedSet s)
static SortedMap synchronizedSortedMap(SortedMap m)
// 사용법
List syncList = Collections.synchronizedList(new ArrayList(...));
변경불가, 싱글톤
멀티쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유하다보면 데이터 가 손상될수 있는데 , 이를 방지하기 위해 사용하는 메서드
static Collection unmodifiableCollection(Collection c)
static List unmodifiableList(List list)
static Set unmodifiableSet(Set s)
static Map unmodifiableMap(Map m)
static NavigableSet unmodifiableNavigable(Set s)
static SortedSet unmodifiableSortedSet(SortedSet s)
static NavigableMap unmodifiableNavigableMap(NavigableMap m)
static SortedMap unmodifiableSortedMap(SortedMap m)단 하나의 객체만을 저장하는 컬렉션을 만드는 경우
static List singletonList(Object o)
static Set singleton(Object o) // singletonSet이 아님을 주의
static Map singletonMap(Object key, Object value)한 종류의 객체만 저장하는 컬렉션 만들기
static Collection checkedCollection(Collection c, Class type)
static List checkedList(Collection c, Class type)
...List list = new ArrayList();
List checkedList = checkedList(list, String.class);
checkedList.add("abc"); //OK
checkedList.add(new Integer(3)); // 에러호환성 때문에 제공을 하고 있으며 요새는 보통 지네릭스로 간단히 처리
예제
package ch11;
import java.util.*;
import static java.util.Collections.*;
public class Ex11_19 {
public static void main(String[] args) {
List list = new ArrayList();
System.out.println(list);
addAll(list, 1,2,3,4,5);
System.out.println(list);
rotate(list,2); // 오른쪽으로 두칸이동.
System.out.println(list);
swap(list,0,2); //첫 번째와 세번째를 교환.
System.out.println(list);
shuffle(list); //저장된 요소의 위치를 임의로 변
System.out.println(list);
sort(list,reverseOrder()); // 역순 정
System.out.println(list);
sort(list); // 정렬
System.out.println(list);
int idx = binarySearch(list,3); // 3이 저장된 위치 반환
System.out.println("index of 3" + idx);
System.out.println("max=" +max(list));
System.out.println("min=" +min(list));
System.out.println("min" +max(list, reverseOrder()));
fill(list,9); // list를 9로 채운다
System.out.println("list="+list);
//list와 같은 크기의 새로운 list를 생성하고 2로 채운다. 단, 결과는 변경불가
List newList = nCopies(list.size(), 2);
System.out.println("newList ="+ newList);
System.out.println(disjoint(list, newList)); // 공통요소가 없으면 true
copy(list,newList);
System.out.println("newList=" + newList);
System.out.println("list=" + list);
replaceAll(list,2,1);
System.out.println("list="+list);
Enumeration e = enumeration(list);
ArrayList list2 = list(e);
System.out.println("list2 =" + list2);
}
}
[]
[1, 2, 3, 4, 5]
[4, 5, 1, 2, 3]
[1, 5, 4, 2, 3]
[1, 3, 2, 5, 4]
[5, 4, 3, 2, 1]
[1, 2, 3, 4, 5]
index of 32
max=5
min=1
min1
list=[9, 9, 9, 9, 9]
newList =[2, 2, 2, 2, 2]
true
newList=[2, 2, 2, 2, 2]
list=[2, 2, 2, 2, 2]
list=[1, 1, 1, 1, 1]
list2 =[1, 1, 1, 1, 1]컬렉션 클래스 정리 및 요약
Journey for Backend Developer