[Java] Collections Framework

JAVA

[Java] Collections Framework - Set

SangRok Jung 2022. 7. 26. 11:40

Set <E> Interface

집합과 같은 데이터를 메모리에 저장하고자 할 때 사용되는 자료구조.

저장 순서의 개념이 없다. (저장 순서가 유지 되지 않는다.)

데이터의 중복 저장을 허용하지 않는다.

수학의 "집합" 특징을 가지고 있다.

▷ HashSet

set Interface를 구현한 대표적인 Collection class
순서를 유지하러면 LinkedHashSet Class를 사용.

▷ TreeSet

범위 검색과 정렬에 유리한 Collection Class
HashSet보다 데이터 추가 삭제에 시간이 더 걸림

▶ 메서드

메서드	설명
boolean add(Object o) boolean addAll(Collection c)	지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가한다.
void clear()	Collection의 모든 객체를 삭제한다.
boolean contains(Object o) boolean containsAll(Collection c)	지정된 객체(o)또는 Collection의 객체들이 Collection에 포함되어 있는지 확인한다.
boolean equals(Object o)	동일한 Collection인지 비교한다.
int hashCode()	Collection의 hash code를 반환한다.
boolean remove(Object o)	지정된 객체를 삭제한다.
boolean removeAll(Collection c)	지정된 Colleciton에 포함된 객체들을 삭제한다.
boolean retainAll(Collection c)	지정된 Colleciton에 포함된 객체만을 남기고 다른 객체들은 Colleciton에서 삭제한다. 이 작업으로 인해 Colleciton에 변화가 있으면 true를 그렇지 않으면 false를 반환한다.
int size()	Colleciton에 저장된 객체의 개수를 반환한다.
Object[] toArray()	Collection에 저장된 객체를 객체배열(Object[])로 반환한다.
Object[] toArray(Object[] a)	지정된 배열에 Colleciton의 객체를 저장해서 반환한다.

▶ 동일 데이터 기준

Object가 정의 하고 있는 두 method의 호출 결과로 판단
- equals()
- hashCode()

▶ 동일데이터의 판단

equlas() 와 hashCode()를 Overriding.
hashCode를 구해서 equals로 비교.
Mod 연산의 나누는 값이 큰 경우 - Unique
Mod 연산의 나누는 값이 작은 경우 - 분류
- 분류를 이용하여 연산의 횟수를 줄이기 위해 Equlas(), HashCode()를 Override 한다.

public boolean equals(Object obj) {
        if(this == obj)
            return true;
        if(obj == null)
            return false;
        if(getClass() != obj.getClass())
            return false;
        return ((this.model == ((Moniter)obj).model) && 
                (this.color == ((Moniter)obj).color));
    }



public int hashCode() {
        //값이 너무 크기 때문에 작게 해준다.
        int hashColor = color.hashCode();
        int hashModel = model.hashCode();
        return (int)((hashModel + hashColor) / 10000);
    }

▶ Hash Algorithm

분류 대상 : 3, 5, 7, 12, 25, 31
적용 Hash Algorithm : num % 3

분류를해 놓으면 탐색의 속도가 매우 빨라지고 존재 유뮤의 확인이 빠르다.

* 비둘기 집의 원리 : 42^10의 확률로 충돌 할 수 있다. 비둘기 집의 원리

    @Override
    public boolean equals(Object obj){
        // try를 사용하면 처리 속도의 저하가 발생합니다.
        // try{
        //     if(this.value == ((IntValue)obj).value){
        //         return true;
        //     }
        //     else{
        //         return false;
        //     }
        // }
        // catch(Exception e){
        //     return false;
        // }
        
        if(this == obj)
            return true;
        if(obj == null) 
            return false;
        if(getClass() != obj.getClass())
            return false;
        return (this.value == ((IntValue)obj).value);
    }


    @Override
    public int hashCode() {
        // return this.value % 3;
        return Objects.hash(value);
    }

HashSet Interface

순서가 유지되지 않으며 중복이 허용되지 않는다.
컬렉션 내의 중복 요소들을 쉽게 제거 할 수 있다.

▶ 메서드

생성자 또는 메서드	설명
HashSet()	HashSet 객체를 생성한다.
HashSet(Collection c)	주어진 컬렉션을 포함하는 HashSet객체를 생성한다.
HashSet(int initailCapacity, float loadFactor)	초기용량과 load factor를 지정하는 생성자.
boolean add(Object o)	새로운 객체를 저장한다. (성공하면 true, 실패하면 false)
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에서 모두 삭제한다.(차집합)
boolean retainAll(Collection c)	주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 삭제한다. (교집합)
int size()	저장된 객체의 개수를 반환한다.
Object[] toArray()	저장된 객체들을 객체배열의 형채로 반환한다.
Object[] toArray(Object[] a)	저장된 객체들을 주어진 객체배열(a)에 담는다.

▶ 구현 1

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

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

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);
    }
}

// equals(), hashCode()를 오버라이딩 해야 HashSet이 바르게 동작.
class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String toString() {
        return name + " : " + age;
    }

    @Override
    public int hashCode() {
        // int hash(Object... values) //가변인자
        return Objects.hash(name, age); //가변인자 => 변수를 더 넣어도 된다.
    }

    @Override
    public boolean equals(Object o) {
        if(!(o instanceof Person))
            return false;

        // 형변환 필요
        Person p = (Person)o;

        // this의 이름과 나이를 p로 비교.
        return this.name.equals(p.name) && this.age == (p.age);
    }
}

▶ 구현 2

public class smple {
    public static void main(String[] args) {
        Object[] objArr = {"1", new Integer(1), "2", "2", "3", "3", "4", "4"};
        Set set = new HashSet();

        for(int i = 0; i < objArr.length; i++) {
            set.add(objArr[i]); // HashSet에 objArr의 요소들을 저장.
        }

        // HashSet에 저장된 요소 출력.
        System.out.println(set);

        // HashSet에 저장된 요소들을 출력한다. (Iterator이용)
        Iterator it = set.iterator();

        while(it.hasNext()) {
            System.out.println(it.next());
        }
    }

    // [1, 1, 2, 3, 4] 1하나는 문자열 객체
    // 1
    // 1
    // 2
    // 3
    // 4
}

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


        // set의 크기가 6이하일 동안 1~45 의 난수저장.
        for(int i = 0; set.size() < 6; i++) {
            int num = (int)(Math.random() *45) + 1;
            set.add(num);
        }

        // 정렬
        // * set은 정렬이 안된다.
        // => set의 모든 요소를 list에 저장한뒤 정렬.
        List list = new LinkedList(set);    //LinkedList(Collection c)
        Collections.sort(list);             //Collections.sort(List list)
        System.out.println(list);
    }
}

▶ 구현 3

교집합, 합집합, 차집합 구하기

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);

        // 간단하게 구하기
        setA.retainAll(setB);   // 교집합. 공통된 요소만 남기고 삭제
        setA.addAll(setB);      // 합집합. setB의 모든 요소를 추가(중복 제외)
        setA.removeAll(setB);   // 차집합. setB의 공통 요소를 제거
    }
}

TreeSet<E> Interface

이진 탐색 트리구조(binary search tree)로 구현하여 정렬상태를 유지하면서 저장하는 Interface.
이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖는다.
정렬상태를 만들기위해 저장되는 Class는 comparable<T> Interface를 Implement 해야한다.
별도의 정렬기준을 제시하기 위해 Comparator<T> Interface를 사용.
범위 탐색과 정렬에 유리

▶ Binary search tree(이진 탐색 트리)

부모보다 작은 값은 왼쪽, 큰값은 오른쪽에 저장.
데이터가 많아질 수 록 비교 횟수 증가에 따라 추가 삭제에 더 많은 시간이 소요.

▶ TreeSet의 데이터 저장 과정

boolean add(Object o)
루트부터 트리를 따라 내려가며 값을 비교하여 작으면 왼쪽, 크면 오른쪽에 저장한다.

▶ 주요 생성자 및 메서드

생성자 또는 메서드	설명
TreeSet()	기본 생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp)	주어진 정렬기준으로 정렬하는 TreeSet을 생성
Object first()	정렬된 순서에서 첫 번째 객체를 반환한다.
Object last()	정렬된 순서에서 마지막 객체를 반환한다.
Object celling(Object o)	지정된 객체와 같은 객체를 반환. 없으면 큰 값을 가진 객체 중 제일 가가운 값의 객체를 반환. 없으면 null
Object floor(Object o)	지정된 객체와 같은 객체를 반환. 없으면 작은 값을 가진 객체 중 제일 가까운 객체를 반환. 없으면 null
Object higer(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값을 객체를 반환. 없으면 null
SortedSet subSet(Object fromElement, Object toElement)	범위 검색(fromElement와 toElement사이)의 결과를 반환한다. (끝 범위인 toElement는 범위에 포함되지 않음)
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.

▶ 범위 검색 메서드

메서드	설명
SortedSet subSet(Object fromElement, Object toElement)	범위 검색(fromElement와 toElement사이)의 결과를 반환한다. (끝 범위인 toElement는 범위에 포함되지 않는다.)
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.

    public static void main(String[] args) {
        // tree set
        TreeSet<Integer> tree = new TreeSet<>();

        // input the data
        tree.add(1);
        tree.add(2);
        tree.add(7);
        tree.add(3);
        tree.add(9);

        // size 출력
        System.out.println("count = " + tree.size());

        // print of for 
        for(Integer i : tree){
            System.out.println(i);
        }


        System.out.println("--------------------------------------------------------");


        // print of iterator
        Iterator<Integer> iter = tree.iterator();
        while(iter.hasNext()){
            System.out.println(iter.next());
        }
    }

▶구현 1

TreeSet은 저장할 때 이미 정렬하기 때문에 읽어올 때 따로 정렬할 필요가 없다.

public class smple{
    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))
        }

        System.out.println(set);
    }
}

▶구현 2

TreeSet은 범위를 검색할 때 유리하다.

subSet을 이용하여 b~d의 문자만을 추출한다.

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

        String from = "b";
        String to   = "d";

        set.add("abc"); set.add("car"); set.add("dance");
        set.add("elephant"); set.add("flower"); set.add("alien");
        set.add("Car"); set.add("dZZZZ"); set.add("elevator");
        set.add("bat"); set.add("dzzzz");

        System.out.println(set);
        System.out.println("range serch : from " + from + " to " + to);
        System.out.println("result1 : " + set.subSet(from, to));    // 전체 집합중 부분집합만 추출
        System.out.println("result2 : " + set.subSet(from, "dzzz"));
    }
}

▶구현 3

public class ex11_15 {
    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(50));
        System.out.println("40과 80사이의 값 : " + set.subSet(40, 80));
    }
}
}

* Tree traversal(트리 순회)

이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회 라고 한다.
전위, 중위, 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.

'JAVA' 카테고리의 다른 글

[Java] Collections Framework - Collections method (0)	2022.07.26
[Java] Collections Framework - Map (0)	2022.07.26
[Java] Collections Framework - Arrays (0)	2022.07.24
[Java] Collections Framework - Stack & Queue (0)	2022.07.21
[Java] Collections Framework - List Interface (0)	2022.07.21

현재글[Java] Collections Framework - Set

꾸준함이 말미암아