8. HashSet
연결리스트와 set의 차이는
•
Set은 중복을 허용하지 않는다.
•
null인 성분이 하나만 존재한다.
•
순서가 존재하지 않는다.
Set의 Class는 위와 같이 구성이 된다. 우리는 HashSet과 TreeSet을 주로 사용하게 될 계획이다.
HashSet: Methods
•
Constructors
Constructor은 위의 4가지가 존재한다.
•
이때 HashSet(int initialCapacity, float loadFactor)을 중심으로 봐보자
◦
initialCapacity : element를 몇개 담을 수 있도록 설정하지를 정하는 것이다.
◦
loadFactor : capacity의 일정 수준 이상 차오르면 capacity를 두배로 증가시켜라(ex 0.75 : 75% capacity가 찼을 때)
•
Methods
이 외의 함수로는 위와 같이 존재한다.
•
subclass of AbstractCollection
◦
addAll, containsAll, retainAll, toArray(), toArray(T[] a), toString
와 같은 함수들 역시 함께 포함되어 있다.
•
subclass of AbstractSet
◦
equals, hashCode, removeAll 과 같은 함수들이 포함되어 있다.
HashSet: Example 1
class Lecture {
public static void main(String[] args) {
String[] strArr = {"1", "1", "2", "2", "3", "3", "4", "4", "4"};
Set<String> set = new HashSet<>();
// set에 element가 계속 추가 된다.
for(int i=0; i<strArr.length; i++) {
set.add(strArr[i]);
}
System.out.println(set);
}
}
Plain Text
복사
중복을 허용하지 않기 때문에 다음과 같은 출력결과가 나올 것이 예상된다.
// ArrayList로 했을때의 결과
HashSet: Example 2
우리가 set으로 데이터를 저장한 다음 list로 바꾸어야 하는 이유 : 중복을 피하기 위해서
class Lecture {
public static void main(String[] args) {
Set<Integer> set = new HashSet<>();
//set의 size가 6보다 작으면 계속 돌도록 한다.
for( ; set.size() < 6; ) {
// 1~45 숫자중에서 하나의 Integer을 삽입하는 과정이다.
int num = (int)(Math.random()*45) + 1;
set.add(Integer.valueOf(num));
}
//아래와 같이 링크드리스트를 만들면 중복이 허용되지 않응 데이터 행렬이 나올 것으로 예상이 된다.
List<Integer> list = new LinkedList<>(set);
Collections.sort(list);
System.out.println(list);
}
}
Plain Text
복사
HashSet: Example 3
class Lecture {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
int[][] board = new int[5][5];
// 1-50 까지의 숫자 중에서 하나를 골라서 Bingo Board를 제작한다.
for( ; set.size() < 25; ) {
set.add((int)(Math.random()*50)+1+"");
}
// Set으로 부터 iterator을 가져와서 중첩 for문을 활용해서 보드의 값을 채워 나간다.
Iterator<String> it = set.iterator();
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[i].length; j++) {
board[i][j] = Integer.parseInt(it.next());
System.out.print((board[i][j] < 10 ? " " : " ") + board[i][j]);
}
System.out.println();
}
}
}
Plain Text
복사
만약 HashSet을 사용하는 경우 특정한 패턴이 보이게 된다. 어떤 숫자들은 앞에 안보이고 뒤에만 보이는 식으로 말이다.
이것은 우리가 elements의 ordering을 정해 놓지 않았기 때문에 자바가 자체적으로 ordering하는 방법을 가지게 되어 생긴 문제점이다.
그래서 만약에 우리가 LinkedHashSet을 사용하게 된다면 oreder of elements가 유지될 것이다.
public class Ex19_03 {
public static void main(String[] args) {
Set<String> set = new LinkedHashSet<>();
int[][] board = new int[5][5];
for(;set.size()<25;) {
set.add((int)(Math.random()*50)+1+"");
}
Iterator<String> it = set.iterator();
for(int i = 0 ;i<board.length;++i) {
for(int j = 0;j<board[i].length;++j) {
board[i][j] = Integer.parseInt(it.next());
System.out.print((board[i][j]<10?" ":" ")+board[i][j]);
}
System.out.println();
}
}
}
Plain Text
복사
HashSet: Example 4
만약 raw type의 class가 존재할때 이 class를 사용하는 HashSet은 중복을 어떻게 대처할 것인가? 결론부터 말하자면 중복이 되어버린다!
왜하하면 중복 체크는 equals와 hashCode를 기준으로 하기 때문에 이것을 바꾸지 않으면 중복이 된것처럼 처리된다.
class Person {
String name;
int age;
Person(String name, int age) { this.name = name; this.age = age; }
public String toString() { return name + ":" + age; }
}
public class Lecture {
public static void main(String[] args) {
HashSet<Person> set = new HashSet<>();
set.add(new Person("David", 10));
set.add(new Person("David", 10));
System.out.println(set);
}
}
Plain Text
복사
HashSet: Example 5
class Person {
String name;
int age;
Person(String name, int age) { this.name = name; this.age = age; }
// 아래와 같이 equals를 새로 정의해 주면 문제가 발생하지 않는다.
public boolean equals(Object obj) {
if(obj instanceof Person) {
Person tmp = (Person)obj;
return name.equals(tmp.name) && age==tmp.age;
}
return false;
}
// 또한 hasCode 역시 아래와 같이 설정하면 hashCode가 동일하게 출력될 수 있다.
public int hashCode() { return (name+age).hashCode(); }
public String toString() { return name + ":" + age; }
}
public class Lecture {
public static void main(String[] args) {
HashSet<Person> set = new HashSet<>();
set.add(new Person("David", 10));
set.add(new Person("David", 10));
System.out.println(set);
}
}
Plain Text
복사
HashSet: hashCode
hashCode() 의 값은 같은 object에 대해서는 같은 값을 반환해야 한다. 하지만 다른 날 다른 시점에서 돌린 hashCode는 값이 달라질 수 있다.
만약 equals가 true를 반환하면 hashCode도 같아야 한다.
만약 equals가 false를 반환하면 hashCode도 달라야 한다.
하지만 hashCode는 Collision을 막을 수 없다. 그러나 perfromance degradation을 막을 수는 없다. 만약 Collision이 발생하면 그때부터는 sequential하게 탐색을 해야 한다. 왜냐하면 HashSet에서 데이터를 같은 locate에 저장을 해야 할때가 된다면 연결리스트로 데이터가 한 Array에 연결되어 있기 때문이다.
HashSet: Example 6
HashSet<String> setA = new HashSet<>();
HashSet<String> setB = new HashSet<>();
HashSet<String> setHab = new HashSet<>();
HashSet<String> setKyo = new HashSet<>();
HashSet<String> 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<String> it = setB.iterator();
while(it.hasNext()) { String tmp = it.next(); if(setA.contains(tmp)) setKyo.add(tmp); }
it = setA.iterator();
while(it.hasNext()) { String 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);
Plain Text
복사
9. TreeSet
TreeSet은 Binary Search Tree를 이용해서 데이터를 저장한다.
특징으로
최소 2개의 자식 노드를 포함하고 있고 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 값이 커야 한다.
그래서 위와 같이 데이터를 저장하면 Sorting된 형태로 데이터를 저장하고 있는 것이 된다. 그렇기에 어떤 데이터를 찾을 때 찾고자 하는 값을 빠르게 찾을 수 있다는 장점이 있다.
또한 중복을 허용하지 않고 입력 순서에 종속되지 않는다.
TreeSet: Behavior
데이터 하나를 저장하면 값을 비교하여서 좌/우로 이동하면서 데이터를 저장하게 된다.
TreeSet: Methods
•
Constructor
•
Methods
TreeSet: Example 1
위에서 HashSet 으로 데이터를 저장했던 코드이다. 여기에서는 TreeSet을 이용하여 중간에 sort를 해주는 과정이 존재하지 않는다.
public class Lecture {
public static void main(String[] args) {
Set<Integer> set = new TreeSet<>();
for( ; set.size() < 6; ) {
int num = (int)(Math.random() * 45) + 1;
set.add(Integer.valueOf(num));
}
System.out.println(set);
}
}
Plain Text
복사
TreeSet: Example 2
public class Lecture {
public static void main(String[] args) {
TreeSet<String> 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);
//subSet을 통하여 from에서 to 까지의 출력이 이루어 진다.
System.out.println("result1: " + set.subSet(from, to));
System.out.println("result2: " + set.subSet(from, to + "zzz"));
}
}
Plain Text
복사
TreeSet: Example 3
tree set을 이용한 range search를 한 예시
public class Lecture {
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet<Integer>();
int[] score = {80, 95, 50, 35, 45, 65, 10, 100};
for(int i=0; i<score.length; i++) set.add(Integer.valueOf(score[i]));
System.out.println("less than 50: " + set.headSet(Integer.valueOf(50)));
System.out.println("greater than or equal to 50: " + set.tailSet(Integer.valueOf(50)));
}
}
Plain Text
복사
