Set(HashSet), Queue(LinkedList)

Set


java_data_structure_map

이번에 알아볼 자바 자료구조는 Set, 그 중에서도 HashSet입니다.

저번 챕터에서 알아본 List는 순서를 중요시 여기는 자료구조였습니다.

Set은 순서를 신경쓰지 않습니다.

데이터가 존재하냐 안하냐만이 중요합니다.


이런 상황을 가정해보겠습니다.

어떤 웹 사이트에서 하루에 접속하는 사람들 수를 구하고자 합니다.

접속하는 IP를 세면 되겠죠.

근데 한사람이 여러번 접속하면 한 IP가 여러번 찍힐 것입니다.

이건 한번으로 카운트 해줘야 제대로 된 접속자 수를 구할 수 있습니다.

이럴 때 쓰는게 Set입니다.

그냥 수학에서 집합 이라고 보시면 됩니다.

math_set (수학책 맨 앞단원에 있어 항상 제일 지저분했던 집합단원)


Set 인터페이스를 구현한 주요 클래스는 3개가 있습니다.

클래스 특징
HashSet 순서가 필요없는 데이터를 hash table에 저장. Set 중에 가장 성능이 좋음
TreeSet 저장된 데이터의 값에 따라 정렬됨. red-black tree 타입으로 값이 저장. HashSet보다 성능이 느림
LinkedHashSet 연결된 목록 타입으로 구현된 hash table에 데이터 저장. 저장된 순서에 따라 값이 정렬. 셋 중 가장 느림

3개의 클래스가 성능 차이가 나는 이유는 데이터 정렬 때문입니다.

HashSet은 별도의 정렬 작업이 없어 제일 빠릅니다.

하지만 수백만 건의 데이터를 처리하는게 아니면 크게 체감하기는 힘들다고 합니다.

hash table이나 red-black tree 등의 자료구조에 대해서는

나중에 별도로 정리해보겠습니다.

일단 지금은 자바에서 이 자료구조의 사용법에 대해서 알아보겠습니다.



HashSet


HashSet_Java_API

먼저 HashSet의 상속관계를 살펴보겠습니다.

AbstractCollection을 확장한 건 ArrayList와 같지만,

HashSet은 AbstractSet을 확장했습니다.

AbstractSet 문서에 들어가보면 구현되어 있는 메소드는

equals(), hashCode(), removeAll() 3개 뿐입니다.

Set은 순서가 필요없고, 중복을 허용하지 않으므로

중복을 체크하는 equals()와 hashCode()는 필수인거 같습니다.


이번엔 HashSet의 생성자를 살펴보겠습니다.

Java_HashSet_Constructor

총 4개의 생성자가 있습니다.

여기서 load factor라는 용어가 나옵니다.

이에 대해 자세히 알려면 Hash Table이라는 자료구조에 대해서

알아봐야 합니다.

자세한 설명은 »여기«를 참조하시면 됩니다.

HashSet() 생성자의 설명을 보면 HashMap() 객체를 쓰는데

초기 저장용량(initial capacity)가 16이고 load factor는 0.75라고 되어있습니다.

간단히 설명하자면

저장된 element의 수 == 저장용량 * load factor

입니다. 즉, 저장용량이 고정돼 있을 때 element를 증가시키면

load factor도 커지겠죠. 커지다가 0.75에 도달하게 되면

저장용량을 약 두배로 늘립니다. 이때 저장용량을 늘리는 과정이

애플리케이션에 부하를 많이 주게 됩니다.

그래서 저장될 데이터(element)의 수가 대충 짐작이 가능하다면

처음에 객체를 생성할 때 저장용량을 데이터 수에 맞게 설정해주면 좋습니다.

load factor 0.75 값은 API에 제일 이상적인 값이라 나와있습니다.

물론 개발하려는 애플리케이션의 목적에 따라 값을 수정할 수 있지만

대부분의 상황에선 기본값을 쓰는게 좋다고 합니다.


아무튼 그래서 (저같은) 초보 개발자들은 load factor를 건드리는

네번째 생성자는 사용하지 않아도 된다고 합니다.


HashSet의 메소드를 살펴보겠습니다.

Java_HashSet_method

순서가 필요없어서 그런지 메소드가 적습니다.

예제를 살펴보겠습니다.

SetSample.java

import java.util.HashSet;
import java.util.Set;

public class SetSample {
    public static void main(String[] ar){
        SetSample ex = new SetSample();
        String[] alphabet = new String[]{
                "A", "B", "A", "D", "C", "E", "F", "G", "E",
                "T", "M", "O"
        };
        System.out.println(ex.getAlphabetKinds(alphabet));
//        A B C D T E F G M O
//        10
        System.out.println(ex.getAlphabetKinds2(alphabet));
//        A B C D T E F G M O
//        10
    }

    public int getAlphabetKinds(String[] alphabet){
        if(alphabet == null) return 0;
        if(alphabet.length == 1) return 1;

        HashSet<String> alphabetSet = new HashSet<>();

        for(String spell: alphabet){
            alphabetSet.add(spell);
        }

        for(String item: alphabetSet){
            System.out.print(item + " ");
        }
        System.out.println();

        return alphabetSet.size();
    }

    public int getAlphabetKinds2(String[] alphabet){
        if(alphabet == null) return 0;
        if(alphabet.length == 1) return 1;

        Set<String> alphabetSet2 = new HashSet<>();

        for(String spell: alphabet){
            alphabetSet2.add(spell);
        }

        for(String item: alphabetSet2){
            System.out.print(item + " ");
        }
        System.out.println();

        return alphabetSet2.size();
    }
}

getAlphabetKinds()와 getAlphabetKinds2()모두

String 배열을 받아 HashSet을 만들고 출력하고 있습니다.

두 메소드의 차이점은 객체 생성입니다.

HashSet<String> alphabetSet = new HashSet<>();
Set<String> alphabetSet = new HashSet<>();

사실 둘 중 아무거나 써도 상관없으나

두번째 방법이 많이 쓰인다고 합니다. 이유는…

Set을 구현한 클래스는 HashSet 말고도 여러 클래스가 있는데

종류에 상관없이 사용하려고 Set 객체로 구현합니다.

ArrayList도 마찬가지로 List로 구현하는게 좋다고 합니다.


String 배열에 중복되는 알파벳이 있는데도

HashSet 객체에 추가하니 중복 알파벳이 없어지는 걸 볼 수 있습니다.


다른 예제를 살펴보겠습니다.

SetSample2.java

import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;

public class SetSample2 {
    public static void main(String[] ar){
        String[] alphabet = new String[]{
                "A", "B", "A", "D", "C", "E", "F", "G", "E",
                "T", "M", "O"
        };
        SetSample2 ex = new SetSample2();
        ex.printHashSet(alphabet);
    }

    public void printHashSet(String[] str){
        Set<String> alpha = new HashSet<>();
        for(String item: str){
            alpha.add(item);
        }

        Iterator<String> iter = alpha.iterator();
        while(iter.hasNext()){
            System.out.print(iter.next() + " ");
        }
//        A B C D T E F G M O
        System.out.println();
        System.out.println();

        if(alpha.contains("Z")){
            System.out.println("alpha set contains \"Z\"");
        }else{
            System.out.println("alpha set does not contain \"Z\"");
        }
//        alpha set does not contain "Z"
        Iterator<String> iter2 = alpha.iterator();
        while(iter2.hasNext()){
            System.out.print(iter2.next() + " ");
        }
//        A B C D T E F G M O
        System.out.println();
        System.out.println();

        if(alpha.contains("A")){
            alpha.remove("A");
            System.out.println("\"A\" is removed from set alpha");
        }else{
            System.out.println("alpha set does not contains \"A\"");
        }
//        "A" is removed from set alpha
        Iterator<String> iter3 = alpha.iterator();
        while(iter3.hasNext()){
            System.out.print(iter3.next() + " ");
        }
//        B C D T E F G M O
    }
}

여기서는 HashSet의 출력을 Iterator 객체를 통해 구현하고 있습니다.

또한 contains()와 remove() 메소드를 사용하고 있습니다.



Queue


Queue는 FIFO(First In First Out)의 용도로 사용하는 자료구조입니다.

fifo

먼저 들어간게 먼저 나온다!

한줄로 ATM을 사용하는 상황입니다.

먼저 온 사람이 먼저 ATM을 사용하고 나오는 형식입니다.

IT에서 FIFO의 상황을 찾자면…

lol_waiting

먼저 로그인을 시도한 9000명 이상이 접속이 되야

제 차례가 되서 로그인할 수 있는 것이죠


그럼 Queue 인터페이스를 구현한 LinkedList를 살펴보겠습니다.



LinkedList


먼저 LinkedList라는 자료구조에 대해서 간단히 살펴보겠습니다.

LinkedList

각각의 데이터는 각각의 node란 곳에 저장이 됩니다.

node는 두 부분으로 나뉘어져 있는데

한곳은 데이터를 저장하고, 다른 한곳은 다음 노드의 주소를 참조합니다.

node A는 ‘내 다음 node는 B다!’ 라는 건 알지만

C나 D의 위치, 존재여부도 모릅니다.


배열과 비슷하지만, 메모리 관리 측면에서 좀 더 효율적입니다.

예를 들어 크기 5의 배열이 있다고 가정하겠습니다.

1번째 위치의 값이 삭제된다면 2, 3, 4번째 위치의 값은

하나씩 앞으로 당겨져야 합니다.

LinkedList의 경우를 살펴보겠습니다.

5개의 값이 있는 LinkedList 객체가 있습니다.

0번째 노드는 1번째 노드를 참조하고, 1번쨰 노드는 2번째 노드는 참조하겠죠.

이 상황에서 1번째 노드를 삭제하면 2, 3, 4번째 노드의 위치가 다 옮겨지는게 아닙니다.

그냥 0번째 노드가 참조하는 노드를 2번째 노드로 설정하면 끝입니다.

즉, 중간에 있는 값이 삭제되거나 추가되는 상황에서는

배열보다 LinkedList를 쓰는게 메모리 관리 측면에서 더 효율적입니다.


이제 자바에서 LinkedList 클래스를 살펴보겠습니다.

Java_api_LinkedList

지금은 Queue를 구현하는데 사용하고 있지만 List도 구현하는 걸 확인할 수 있습니다.


LinkedList 클래스의 생성자를 살펴보겠습니다.

Java_LinkedList_Constuctor

LinkedList는 객체 생성시 크기를 지정하지 않는 걸 볼 수 있습니다.(empty list)

각 데이터들이 앞뒤로 연결되는 구조이기 때문에 미리 공간을 만들어 놓을 필요가 없습니다.


API 문서에서 LinkedList의 메소드를 살펴보면

여러 인터페이스를 구현한 만큼 메소드도 많습니다.

그런데 자세히 살펴보면 중복된 기능을 가진 메소드들이 많습니다.

예를 들어 add(), addLast(), offer(), offerLast()

이 4개의 메소드들은 모두 LinkedList 객체 가장 뒤에 값을 추가하는 역할을 합니다.

이렇게 중복된 메소드들이 많은 이유는 마찬가지로 여러 인터페이스를 구현했기 때문입니다.

저 메소드를 섞어서 쓰면 보는 사람은 더 혼동될 것이기 때문에

하나를 정해서 그것만 쓰는게 좋습니다.

저는 addLast()가 가장 명확하게 기능을 말해주고 있는거 같아 맘에 드네요.


예제코드로 몇가지 메소드를 사용해보겠습니다.

QueueSample.java

import java.util.LinkedList;
import java.util.ListIterator;

public class QueueSample {
    public static void main(String[] ar){
        QueueSample ex = new QueueSample();
        ex.checkLinkedList();
    }

    public void checkLinkedList(){
        LinkedList<String> ll = new LinkedList<>();
        ll.add("Teemo");
        System.out.println(ll);
//        [Teemo]
        ll.add("Jinx");
        System.out.println(ll);
//        [Teemo, Jinx]
        ll.addFirst("Zed");
        System.out.println(ll);
//        [Zed, Teemo, Jinx]
        ll.add(1, "Rengar");
        System.out.println(ll);
//        [Zed, Rengar, Teemo, Jinx]
        System.out.println(ll.set(0, "Gnar") + " is changed to Gnar");
//        Zed is changed to Gnar
        System.out.println(ll);
//        [Gnar, Rengar, Teemo, Jinx]
        System.out.println("ll.getFirst() = " + ll.getFirst());
//        ll.getFirst() = Gnar
        System.out.println("ll.indexOf(\"Teemo\") = " + ll.indexOf("Teemo"));
//        ll.indexOf("Teemo") = 2
        System.out.println("ll.removeFirst() = " + ll.removeFirst());
//        ll.removeFirst() = Gnar
        System.out.println(ll);
//        [Rengar, Teemo, Jinx]

        System.out.println();
        ListIterator<String> li = ll.listIterator();
        if(li.hasNext()){
            System.out.println("li.next() = " + li.next());
        }
//        li.next() = Rengar
        System.out.println("li.next() = " + li.next());
//        li.next() = Teemo
        System.out.println("li.previous() = " + li.previous());
//        li.previous() = Teemo
        System.out.println("li.previous() = " + li.previous());
//        li.previous() = Rengar
    }
}

마지막 부분에 ListIterator 부분을 보겠습니다.

Iterator는 다음 데이터만을 검색할 수 있었습니다.

ListIterator는 이 단점을 보완해 이전 메소드도 검색가능한 인터페이스 입니다.