Set과 Queue

Set 컬렉션 클래스

1. 요소의 저장 순서를 유지하지 않는다. (순서 상관 X)
2. 같은 요소의 중복 저장을 허용하지 않는다. (중복 X)

Set 컬렉션은 어떤 경우 쓰이는 걸까?

예를 들어 어떤 서버에 1분간 사용자가 요청한 로그가 있다. 이 서버에 붙어서 요청한 IP를 기준으로 사용자의 수가 얼마나 되는지 확인한다고 가정해보자.

1분간 동일한 서버에 요청하는 중복 사용자 수는 매우 많다.

이러한 경우 배열로 확인하려면 indexOf() 메소드를 활용하여 해당 객체가 존재하는지 확인한 후 add() 메소드로 추가하는 작업을 반복해야한다.

하지만 반복을 싫어하는 선배님들께서 좋은것을 만들어 주었다. Set이다.

Set을 구현한 클래스를 사용하면 단순히 데이터를 추가만 해주면 된다. → 데이터 중복이 발생하지 않고 저장된다.

이때 각 사용자가 사용한 IP의 순서는 중요하지 않다.

• Set 인터페이스를 구현한 주요 클래스

성능 차이가 발생하는 이유는 데이터 정렬 때문이다. HashSet이 가장 빠른 이유는 별도의 정렬 작업이 없어 제일 빠르다.

• Red-Black 트리 구조

레드-블랙 트리를 간략히 말하면 각 노드의 색을 붉은 색 혹은 검은색으로 구분하여 데이터를 빠르고, 쉽게 찾을 수 있는 구조의 이진(binary)트리를 말한다.

더 구체적인 자료는 아래의 링크에서 확인해보자.

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

HashSet에 관하여

• HashSet의 상속관계

java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractSet<E>
            java.util.HashSet<E>

AbstractCollection을 확장한 것은 ArrayList와 동일하다.

반면에 HashSet은 AbstractSet을 확장했다. AbstractSet 클래스는 abstract 클래스이다.

구현되어 있는 메소드는 Object 클래스에 선언되어 있는 equals(), hashCode() 메소드와 이 클래스에서 추가한 removeAll() 이다.

• HashSet이 구현한 인터페이스들

• List에 정의되어 있는 것중에 Set에는 없는 메소드는 ?

Set은 순서가 없다. 그렇기 때문에 순서가 매개 변수로 넘어가는 메소드나, 수행 결과가 데이터의 위치와 관련된 메소드는 Set 인터페이스에서는 필요가 없다.

따라서…

get(int index) , indexOf(Object o)와 같은 메소드들은 Set에 있지않다.

HashSet의 생성자

• HashSet의 4개의 생성자

• 로드 팩터(load-factor)란 ?
  • (데이터 개수) / (저장공간)을 의미한다.

만약 데이터의 개수가 증가하여 로드 팩터보다 커지면, 저장 공간의 크기는 증가되고 해시 재정리 작업(rehash)을 해야만 한다. 데이터가 해시 재정리 작업에 들어가면, 내부에 갖고 있는 자료 구조를 다시 생성하는 단계를 거쳐야하므로 성능에 영향이 발생한다.

로드 팩터라는 값이 클수록 공간은 넉넉해지지만, 데이터를 찾는 시간은 증가한다.

따라서 초기 공간 개수와 로드 팩터는 데이터의 크기를 고려하여 산정하는 것이 좋다.

이유는 초기가 (데이터개수) / (로드팩터) 보다 클 경우에는 데이터를 쉽게 찾기 위한 해시 재정리 작업이 발생하지 않기 때문이다.

따라서 대량의 데이터를 여기에 담아 처리할 때에는 초기 크기와 로드 팩터의 값을 조절해 가면서 가장 적당한 크기를 찾아야만 한다.

HashSet의 주요 메서드

• HashSet에 선언되어 있는 메소드 목록

• HashSet 예제

public class SetSample {
    public static void main(String[] args) {
        SetSample sample = new SetSample();
        String[] cars = new String[]{
            "Tico","Sonata","BMW","Benz",
            "Lexus","Mustang","Grandeure",
            "The Beetle","Mini Cooper","i30",
            "BMW","Lexus","Carnibal","SM5",
            "SM7","SM3","Tico"
        };

        System.out.println(sample.getCarKinds(cars));
    }

    public int getCarKinds(String[] cars) {
        if(cars==null) return 0; // ①
        if(cars.length==1) return 1; // ②
        Set<String> carSet = new HashSet<>(); // ③

        //④
        for (String car : cars) {
            carSet.add(car);
        }

        return carSet.size(); // ⑤
    }
}

① cars라는 배열이 null 인지 아닌지 체크하는 코드 → null인 배열을 매개 변수로 받을 경우 NullPointerException이 발생한다.

② cars 배열의 크기가 1인지 확인했다. → 배열의 크기가 1이면, 확인할 필요도 없이 결과도 1이기 때문이다.

③ carSet이라는 HashSet 객체를 생성

④ 생성한 carSet 객체에 cars 배열의 값들을 하나씩 담았다. 이렇게 하면, 중복된 값은 없고 유일한 자동차 이름만 남는다.

⑤ carSet의 크기를 리턴했다 → 결과 값 : 14

• HashSet에 저장되어 있는 값을 꺼내는 방법 1

public void printCarSet(Set<String> carSet){
    for(String temp : carSet){
        System.out.print(temp + " ");
    }
}

• 결과

Mustang Lexus Tico i30 Grandeure Carnibal Sonata BMW Benz SM3 The Beetle SM5 Mini Cooper SM7
14

• HashSet에 저장되어 있는 값을 꺼내는 방법 2

public void printCarSet2(Set<String> carSet){
    Iterator<String> iterator = carSet.interator(); //①
    while(iterator.hasNext()) { // ②
        System.out.print(iterator.next() + " "); // ③
    }

    System.out.println();
}

① iterator() 라는 메소드를 사용하여 Iterator 객체를 생성한다.

② while문을 사용하여 다음 데이터가 존재하는지를 hasNext()라는 메소드를 사용하여 지속적으로 확인

③ next() 메소드를 사용하여 다음 값을 얻어낸다.

• 결과

Mustang Lexus Tico i30 Grandeure Carnibal Sonata BMW Benz SM3 The Beetle SM5 Mini Cooper SM7
14

Queue에 관하여

Queue를 배우기 앞서서 LinkedList 를 알아보자.

LinkedList란 ?

1. LinkedList에 A라는 하나의 값이 추가되면 제일 앞에 데이터를 집어 넣는다. → LinkedList의 가장 앞의 값도 A며, 가장 끝에 있는 값도 A다.

1. B라는 데이터를 집어넣었다. 그러면 가장 앞에 있는 값은 A이고, 가장 뒤에 있는 값은 B다. → A는 뒤에 B가 있다는 것을, B는 A가 앞에 있다는 것을 기억하고 있는다.

1. C라는 데이터를 집어넣었다 그러면 가장 앞의 값은 A, 그 다음은 B, 마지막에는 C가 위치한다. LinkedList에서는 앞에 있는 데이터와 뒤에있는 데이터만 기억한다. 간략히 말하면, A는 뒤에 있는 값이 B라는 것만 알고, C가 있다는 것은 생각도 안한다. C라는 데이터도 앞에 B라는 것만 기억한다.

LinkedList라는 것은 왜 쓸까?

배열을 쓰지 않고 LinkedList를 왜 쓰는 것일까? 뭔가가 있겠지? 라고 생각하겠지만 이건 너무 무책임한 말이다. 구체적으로 알고 있어야한다.

간단한 배열과 같이 데이터를 담아서 순차적으로 뺄 경우에는 LinkedList가 필요없을 수 있다. 하지만 배열의 중간에 있는 데이터가 지속적으로 삭제되고, 추가될 경우에는 LinkList가 배열보다 메모리 공간 측면에서 훨씬 유리하다.

이유는 배열과 같은 ArrayList와 vector는 각 위치가 정해져 있고, 그 위치로 데이터를 찾는다. 그런데 맨 앞의 값을 삭제하면, 그 뒤에 있는 값들은 하나씩 앞으로 위치를 이동해야 제대로 된 위치의 값을 가지게 된다.

반면에 LinkedList는 중간에 있는 데이터를 삭제하면, 지운 데이터의 앞에 있는 데이터와 뒤에 있는 데이터를 연결하면 끝이다.

위치를 맞추기 위해서 값을 이동하는 단계를 거칠 필요가 없어진다.

LinkedList는 List 인터페이스뿐만 아니라 Queue와 Deque 인터페이스도 구현하고 있다. 따라서 LinkedList 자체가 List이면서도 Queue, Deque도 된다는 뜻이다.

LinkedList 클래스가 구현한 인터페이스 중에서 Java 6에서 추가된 Deque라는 것이 있다.

Deque의 풀네임은 “Double Ended Queue" 이다.

LinkedList에 관하여

• LinkedList 상속 관계

java.lang.Object
    java.util.AbstractCollect<E>
        java.util.AbstractList<E>
            java.util.AbstractSequentialList<E>
                java.util.LinkedList<E>

상속관계를 보면, ArrayList 클래스나 Vector 클래스와 상속관계는 비슷하지만, AbstractSequentialList가 부모인 것을 볼 수 있다. AbstractList와 AbstractSequentialList의 차이점은 add(), set(), remove() 등의 메소드에 대한 구현 내용이 상이하다는 정도다.

• LinkedList 클래스가 구현한 인터페이스 목록

LinkedList는 List도 되고 Queue도 된다. 두 인터페이스의 기능을 모두 구현한 특이한 클래스이다.

LinkedList의 생성자와 주요 메서드

LinkedList는 생성자가 두 개 밖에 없어서 주요메소드와 같이 다루겠다.

• LinkedList 생성자 목록

• LinkedList 주요 메소드 목록

각 메소드의 이름을 보면 중복된 기능을 수행하는 메소드가 많다.

LinkedList가 여러 종류의 인터페이스를 구현했기 때문에 그렇다.

public class QueueSample {
    public static void main(String[] args) {
        QueueSample sample = new QueueSample();
        sample.checkLinkedList1();
    }

    public void checkLinkedList1() {
        LinkedList<String> link = new LinkedList<>();
        link.add("A");
        System.out.println(link);

        link.addFirst("B");
        System.out.println(link);

        link.offerFirst("C");
        System.out.println(link);

        link.addLast("D");
        System.out.println(link);

        link.offer("E");
        System.out.println(link);

        link.offerLast("F");
        System.out.println(link);

        link.push("G");
        System.out.println(link);

        link.add(0, "H");
        System.out.println(link);
        System.out.println("EX = " + link.set(0, "I"));
        System.out.println(link);
    }
}

• 결과

[A]
[B, A]
[C, B, A]
[C, B, A, D]
[C, B, A, D, E]
[C, B, A, D, E, F]
[G, C, B, A, D, E, F]
[H, G, C, B, A, D, E, F]
EX = H
[I, G, C, B, A, D, E, F]

메소드는 어떤걸 쓰는게 좋을까? add? offer? push?

LinkedList 소스를 보면 맨 앞에 추가하는 메소드는 동일한 기능을 수행하는 어떤 메소드를 호출해도 addFirst() 메소드를 호출한다. 맨 뒤에 추가하는 메소드는 동일한 기능을 수행하는 offer() 관련 메소드를 호출하면 add()나 addLast() 메소드를 호출하도록 되어 있다.

따라서

팀 프로젝트할 때는 같이 어떤 메소드를 쓸 지 선정하여 사용하는 것이 좋다.

• LinkedList 클래스에서 특정 위치의 데이터를 꺼내는 메소드 목록
  • 권장 사항 : 맨 앞에 데이터를 가져오는 메소드는 모두 내부적으로 getFirst() 메소드를 호출하므로, 이 메소드를 사용할 것을 권장

• LinkedList에 어떤 객체가 포함되어 있는지 확인하는 메소드
  • 데이터의 값으로 위치를 찾거나, 존재하는지를 확인하려면 이 표에 있는 메소드들을 쓰면된다.

• LinkedList에 데이터를 삭제하는 메소드 목록

• LinkedList 객체를 하나씩 검색하기 위한 Iterator 객체에 대해서

마지막으로 링크는 이것을 한번에 볼 수 있는 링크를 주겠다..

자바8 API - LinkedList

LinkedList (Java Platform SE 8 )

참고자료

• 위키피디아 - https://ko.wikipedia.org/wiki/레드-블랙_트리
• 자바의 신