HashSet<E> / TreeSet<E>

HashSet<E>

해시알고리즘

HashSEt<E> 클래스를 제대로 활용하기 위해서는 간단하게나마 해시 알고리즘을 이해해야 한다.

num%3

3, 5, 7, 12, 25, 31 이라는 집합이 있을때 집합 원소들을 3으로 나누면 연산의 결과를 0,1,2, 3가지로 나눌수 있다.

연산결과 0 : 3, 12

연산결과 1 : 5

연산결과 2 : 7, 25, 31

이렇게 부류가 나뉜 상태에서 집합에 정수가 5가 존재하는지 확인하는 가장 효율적인 방법은

찾고자 하는 수인 5를 3으로 나머지 연산하여 나온 결과가 속하는 부류를 찾는것이 가장 효율적인 방법이다.

그럼 나머지 연산의 결과가 0과 1 인 부류는 검색의 대상에서 제외가 된다. 즉 검색의 대상이 줄어들은것이다.

이것이 해시 알고리즘의 장점이다. 해시 연산의 결과값 0, 1 ,2 를 가르켜 '해시 값' 이라 하며 

이 해시 값을 기준으로 데이터를 구분하게 된다.

검색1단계 -> 구하고자 하는 정수의 해시값을 계산한다.

검색2단계-> 해시 값이 속하는 부류 내에서 구하고자 하는 정수가 존재하는지 확인한다.

이렇게 두단계를 거치는 이유는 검색의 효율성과 속도 향상을 위한 것이다.

HashSet<E> 클래스는 해시 알고리즘을 적용하여 데이터를 저장하고 검색한다.

HashSet<E> 클래스의 장점은 "매우 빠른 검색속도" 이다.

HashSet<E> 클래스는 데이터 저장시에 검색의 과정을 거친다. 중복을 허용하지 않기 때문이다.

중복된 데이터가 있는지 판단은 

Object 클래스의 hashCode 메소드의 반환값을 해시 값으로 활용

Object 클래스의 equals 메소드의 반환값을 이용해서 내용 비교

Object 클래스의 hashCode 메소드는 인스턴스가 다르면 구성 내용에 상관없이 전혀 다른 해시값을 반환하게 되어있다.

따라서 구성이나 값은 같지만 해시코드가 다른 데이터를 저장하게 된다.

값은 같지만 다른 인스턴스를 동일한 데이터로 인식이 되게 하려면

public int hashCode() 메소드와 public boolean equals(Object obj) 메소드를 오버라이딩 해야된다.

public class HashTest {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        HashSet<String> hs = new HashSet<String>();
        hs.add(new String("first"));
        hs.add(new String("second"));
        hs.add(new String("third"));
        hs.add(new String("first"));
        
        System.out.println("저장된데이터수 :"+hs.size());
        Iterator<String> itr = hs.iterator();
        while(itr.hasNext())
            System.out.println(itr.next());
    }
 
}

TreeSet<E>

TreeSet<E> 클래스는 '트리(Tree)' 라는 자료구조를 기반으로 구현되어 있다.

트리는 데이터를 정렬된 상태로 저장하는 자료구조이다. 

따라서 이를 기반으로 구현된 TreeSet<E>클래스 역시 데이터를 정렬된 상태로 유지한다.

TreeSet<E> 클래스는 중복된 데이터의저장을 허용하지 않고 오름차순으로 정렬이 이뤄진다.

TreeSet<E> 클래스에는 decendingIterator 라는 내림차순으로 검색해 반환하는 메소드로 

내림차순으로정렬해 출력도가능하다.

public static void main(String[] args){
        TreeSet<Integer> ts =new TreeSet<Integer>();
        ts.add(1);
        ts.add(4);
        ts.add(3);
        ts.add(4);
        ts.add(2);
        
        Iterator<Integer> itr = ts.iterator();
        while(itr.hasNext()){
            System.out.println(itr.next());
        }

데이터의 중복저장미허용과 오름차순정렬에의한 결과 1 2 3 4 

정렬의 방식이 숫자라면 정렬의 기준이 오름차순이 가능하지만

정렬의대상이 인스턴스라면 정렬 기준을 Comparable<T> 인터페이스를 구현해 정의한다.

Comparable<T>인터페이스는 다음과 같이 정의한다.

인자로 전달된 obj의 멤버변수가 작다면 양의정수 반환

인자로 전달된 obj의 멤버변수가 크다면 음의정수 반환

인자로 전달된 obj의 멤버변수가 같다면 0반환

public class Person implements Comparable<Person> {
    String name;
    int age;
    public Person(String name,int age){
        this.name=name;
        this.age=age;
    }
    @Override
    public int compareTo(Person o) {
        if(age>o.age)
            return 1; //매개변수가 작다면 양수 반환
        else if(age<o.age)
            return -1; //매개변수가 크다면 음수 반환
        else
            return 0; //같다면 0 반환
        
        return 0;
    }
}

compareTo 메서드를 통해 인스턴스간의 크고 작음을 비교 가능하게 되었다.

TreeSet<T> 는 Person 인스턴스가 저장될 때 마다 compareTo메서드를 호출해 

반환되는 값을 기준으로 정렬을 진행 할 것이다.

comparator<T> 

comparator<T> 인터페이스는 문자열의 정렬 기준을 정의할수 있다.

public class strLenComparator implements Comparator<String> {
 
    @Override
    public int compare(String o1, String o2) {
        if(o1.length()>o2.length())
            return 1;
        else if(o1.length()<o2.length())
            return 2;
        else
            return 0;
    }
}