[Java] HashSet | TreeSet

Jeini·2022년 12월 8일
0

☕️  Java

목록 보기
42/59
post-thumbnail

💡 HashSet


✔️ 순서, 중복이 없다.

  • Set 인터페이스를 구현한 대표적인 Collection 클래스
  • 순서를 유지하려면, LinkedHashSet 클래스를 사용하면 된다.

HashSet 클래스는 Set 컬렉션 클래스에서 가장 많이 사용되는 클래스 중 하나이다.

JDK 1.2부터 제공된 HashSet 클래스는 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다.

이러한 HashSet 클래스는 내부적으로 HashMap 인스턴스를 이용하여 요소를 저장한다.

✏️ HashSet 생성자

  • initialCapacity: 배열의 용량
  • loadFactor: 언제 용량을 늘릴것인지

✏️ HashSet 메서드

❗️Set은 집합이기 때문에 이러한 기능이 가능하다.

  • addAll: 합집합
  • removeAll: 교집합
  • retainAll: 차집합

  • contains: 요소가 있는지 확인

📎 HashSet 객체저장

  • 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인해야 한다.
    같은 객체가 없으면 저장하고, 있으면 저장하지 않는다.

  • boolean add(Object o) 는 저장할 객체의 equals()hashcode() 를 호출한다.
    equals()hashcode() 가 같이 오버라이딩 되어 있어야 한다.

✏️ 객체 중복 예제

import java.util.*;

public class HashSetObject {
    public static void main(String[] args) {
        HashSet set = new HashSet();
		
        // 같은 String
        set.add("abc");
        set.add("abc");
        
        // 같은 사람
        set.add(new Person("Jennie" , 25) );
        set.add(new Person("Jennie", 25));

        System.out.println(set);

    }
}
class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        setAge(age);
        setName(name);
    }
    @Override
    public String toString() {
        return name + ": " + age;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public int getAge() {
        return age;
    }
}
[abc, Jennie: 25, Jennie: 25]

HashSet은 중복을 제거하지만 객체안에서 어떤것이 같은지 아닌지를 모르기 때문에 위 예시처럼 그대로 나온다.

이렇듯 이름과 나이가 같으면 같은 사람이라는 것을 객체 안에다 지정해줘야 한다.

✏️ equals()와 hashCode() 오버라이딩

    @Override
    public boolean equals(Object o) {
        if(o == null || !(o instanceof Person)) {
            return false;
        }
        Person other = (Person) o;
        return name.equals(other.getName()) && age == other.getAge();
    }

    @Override
    public int hashCode() {
        // int hash(Object ... values) 가변인자
        return Objects.hash(name, age);
    }

이렇게 만들어줘야 HashSet이 중복을 소거해준다.

✏️ 총정리 결과

import java.util.*;

public class HashSetObject {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        set.add("abc");
        set.add("abc");
        set.add(new Person("Jennie" , 25) );
        set.add(new Person("Jennie", 25));

        System.out.println(set);

    }
}
class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        setAge(age);
        setName(name);
    }
    @Override
    public String toString() {
        return name + ": " + age;
    }

    @Override
    public boolean equals(Object o) {
        if(o == null || !(o instanceof Person)) {
            return false;
        }
        Person other = (Person) o;
        return name.equals(other.getName()) && age == other.getAge();
    }

    @Override
    public int hashCode() {
        // int hash(Object ... values) 가변인자
        return Objects.hash(name, age);
    }

    public void setName(String name) {
        this.name = name;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public int getAge() {
        return age;
    }
}
[abc, Jennie: 25]

💡 TreeSet


✔️ 이진 탐색 트리(binary search tree)로 구현

  • 범위 검색정렬에 유리한 Collection
  • 이진 트리는 모든 노드가 최대 2개의 하위노드를 갖는다.
  • 각 요소(node)가 나무(tree)형태로 연결(LinkedList 변형)

class TreeNode {
	TreeNode left; // 왼쪽 자식노드
    Object elelment; // 저장할 객체
    TreeNode right; // 오른쪽 자식노드
}

📎 이진 탐색 트리(binary search tree)

  • 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
  • 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)


✏️ TreeSet의 데이터 저장과정

✔️ boolean add(Object o)

  • 루트부터 트리를 따라 내려가며 값을 비교한다.
  • 작으면 왼쪽, 크면 오른쪽에 저장한다.

HashSet은 equals(), hashCode() 로 비교
TreeSet은 compare() 를 호출해서 비교

✏️ TreeSet 생성자

✏️ TreeSet 메서드

  • Object first() : 오름차순으로 제일 작은 값을 나타낸다. (last() : 큰 값)
  • Object ceiling(Object o) : 올림 (floor() : 버림)

✏️ TreeSet 예제

✏️ 정렬이 돼서 나오는 TreeSet

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        // 범위 검색, 정렬.
        Set set = new TreeSet();

        for(int i = 0; set.size() < 6; i++) {
            int num = (int)(Math.random() * 45) + 1;
            set.add(num); // set.add(new Integer(num));
            // Integer클래스 안에 정렬기준을 이용했다.
        }
        System.out.println(set);

    }
}
[13, 14, 16, 21, 33, 36]

TreeSet은 정렬이 된 상태로 결과값이 나온다는 것을 알 수 있다.

✏️ 비교기준을 나타내야 한다.

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        Set set = new TreeSet();

        for(int i = 0; set.size() < 6; i++) {
            int num = (int)(Math.random() * 45) + 1;
            set.add(new Test()); 
        }
        System.out.println(set);
    }
}
class Test {} // 비교 기준이 없음
Exception in thread "main" java.lang.ClassCastException: class Test cannot be cast to class java.lang.Comparable (Test is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
	at java.base/java.util.TreeMap.put(TreeMap.java:536)
	at java.base/java.util.TreeSet.add(TreeSet.java:255)
	at TreeSetEx1.main(TreeSetEx1.java:9)

형변환 예외가 나온다. 그 이유는 비교기준이 없기 때문이다.

✏️ 비교기준 설정 comparator

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        Set set = new TreeSet(new TestComp()); // TreeSet에다 새로운 비교기준을 넣어준다.

        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());

        System.out.println(set);
    }
}

class TestComp implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        return 1;
    }
}
[TestComp@1cd072a9, TestComp@7c75222b, TestComp@4c203ea1, TestComp@27f674d]

✏️ 비교기준 설정 comparable

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        Set set = new TreeSet();

        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());

        System.out.println(set);
    }
}

class TestComp implements Comparable {
    @Override
    public int compareTo(Object o) {
        return 1;
    }
}
[TestComp@4c203ea1, TestComp@27f674d, TestComp@1d251891, TestComp@48140564]

✏️ 범위 검색에 유용한 TreeSet

import java.util.*;

public class TreeSetEx1 {
    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(50));
        System.out.println("50보다 같거나 큰 값: " + set.tailSet(50));
        System.out.println("40과 80사이의 값: " + set.subSet(40, 80));
    }
}
50보다 작은 값: [10, 35, 45]
50보다 같거나 큰 값: [50, 65, 80, 95, 100]
40과 80사이의 값: [45, 50, 65]


표를 그려보면 이렇다.


References
: https://cafe.naver.com/javachobostudy

profile
Fill in my own colorful colors🎨

0개의 댓글