Collection FrameWork 자료구조의 이해

Collection FramWork

자바는 Collection FramWork를 제공합니다

이 안에는 대부분의 자료구조가 존재합니다. List, Map, Set, Tree...

또 기본적으로 Collection은 Parameterized Type을 사용합니다.

 

Collection을 한마디로 정리하면 자료를 다루는 방법과 저장하는 구조가 다른 Abstract Data Type의 집합입니다.
따라서 용도에 따라 어떤 자료구조를 사용할 것인지 잘 이해했다면 Collection FrameWork를 이해했다고 볼 수 있습니다.

 

 

List

List Interface를 상속받는 구현체는 대표적으로 ArrayList, LinkedList 가 존재합니다.

둘다 같은 List를 상속받아 구현체로써 사용되지만 , 구현할떄 사용되는 Representation이 다릅니다.

이런식으로 Collection Interface를 상속받은 구현체는 구현시 사용되는 자료구조가 다르거나 정렬의 유무에서 차이가 나는 경우게 대부분입니다.

 

데이터 구조

1. ArrayList 배열 사용
2. LinkedList node구조 사용

이렇게 구조에서 차이가 나지만 실제 동작에서는 ArrayList가 할 수 있는 일은 LinkedList가 전부 할 수 있으며

LinkedList 가 할 수 있는 일은 ArrayList가 전부 수행 가능합니다.

 

그럼 왜 나눠서 쓰는 걸까요??
그냥 하나로 통일해서 쓰면 안될까요??

 

ArrayList는 배열을 사용합니다. 따라서 주소가 sequential하게 연결돼있습니다.

따라서 특정 index에 접근하는게 매우 빠릅니다 시작주소 + 3 하면 3번쨰 index에 접근 가능하게 되는 것이죠

반면에 원소를 더하거나 삭제하는 경우에는 배열의 요소들을 한 칸씩 뒤로 이동시키거나 앞으로 당겨야 하기 때문에 상당히 느린 연산을 수행하게됩니다.

 

LinkedList는 node 구조를 사용합니다 배열이 아님으로 주소가 sequential하게 연결돼있지 않습니다.
따라서 특정 index에 접근하는게 ArrayList에 비해 느립니다.

 

하지만 원소를 더하거나 삭제하는 연산을 할때 node들 사이에 연결만 이어주고 끊어주면 되기때문에 ArrayList보다 연산이 빠릅니다.

정리하자면 다음과 같습니다.

 

• ArrayList : 리스트 크기 변경 안될때 , 데이터 접근이 빈번할 때
• LinkedList : 리스트 크기 변경이 자주 일어날떄 , 요소의 삽입/삭제가 빈번할 때

이렇게 같은 List자료구조지만 구현돼있는 내부 구조가 다르기 떄문에 용도에 맞게 사용할 수 있어야 합니다.

 

 

Set

Set은 중복을 허용하지 않는 대표적인 자료구조입니다.

크게 HashSet , TreeSet 으로 나뉩니다.

Hash는 이름그대로 HashCode를 사용하며 Tree는 내부적으로 BinarySearchTree 구조를 사용합니다.

 

이점은 중복을 어떻게 확인할 것인지에 큰 차이가 생깁니다.

• HashSet
  1. HashCode 비교
  2. Equals 비교
  3. 중복없음

 

• TreeSet
  1. 요소들이 이미 정렬돼있음
  2. Tree를 순회하면서 직접 Element 비교 (Comparable Implements 필요)
  3. 중복없음

HashSet은 HashCode와 Equals만 이용하면 되기 떄문에 원소를 추가하는 연산이 빠릅니다.

반면에 TreeSet은 직접적인 순회를 해야하기 떄문에 HashSet에 비해 느립니다. 하지만 정렬된 상태를 유지하기 떄문에

 

정렬된 상태가 필요한 경우에는 TreeSet을 그렇지 않다면 HashSet쓰는게 일반적으로 유리합니다.

public class Main {

    public static void main(String[] args) {

        Set<Person> set = new HashSet<>();

        set.add(new Person(20, "홍길동"));
        set.add(new Person(20, "홍길동"));

        for (Person p : set) {
            System.out.println(p);
        }

    }
}

class Person {


    int age;
    String name;

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

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Person person = (Person) o;

        return age == person.age && Objects.equals(name, person.name);
    }

//    @Override
//    public int hashCode() {
//        return Objects.hash(age, name);
//    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

}

Equals 구현 , HashCode 주석처리

따라서 중복체크를 똑바로 못합니다.

 

 

HashCode의 주석처리를 지워주면 중복체크가 정상적으로 작동합니다.

public class Main {

    public static void main(String[] args) {

        Set<Person> set = new TreeSet<>();

        set.add(new Person(20, "홍길동"));
        set.add(new Person(20, "홍길동"));

        for (Person p : set) {
            System.out.println(p);
        }

    }
}

class Person implements Comparable<Person> {


    int age;
    String name;

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

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    public int compareTo(Person o) {

        return this.age - o.age;

    }
}

TreeSet은 해시코드와 Equals를 쓰지 않습니다.

대신 Comparable의 compareTo 를 사용합니다

지금은 age를 기준으로 compareTo가 구현이 돼있습니다.

public static void main(String[] args) {

        Set<Person> set = new TreeSet<>();

        set.add(new Person(20, "홍길동"));
        set.add(new Person(21, "홍길동"));

        for (Person p : set) {
            System.out.println(p);
        }

    }

이 코드에서는 나이가 다르면 이름이 같아도 다른 객체기 떄문에 2개가 들어갑니다.

 

Map

Map은 Key : Value 쌍으로 이루어져 있습니다.

여기서는 Key가 해시코드 역할을 합니다.

Map 자료구조도 대표적으로 HashMap , TreeMap 이 존재합니다.

또 내부적으로 HashMap은 배열과 연결리스트 기반 , Tree는 노드기반 구조를 사용합니다

기존과 똑같이 Hash는 HashCode , Equals 를 사용합니다.

public class Main {

    public static void main(String[] args) {

        Map<Person, Integer> map = new HashMap();

        map.put(new Person(20, "홍길동"), 1);
        map.put(new Person(20, "홍길동"), 2);


        for (Person p : map.keySet()) {
            System.out.println(p);
        }

    }
}

class Person {


    int age;
    String name;

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

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Person person = (Person) o;

        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }


}

 

 

마찬가지로 TreeMap은 compareTo를 구현해 써야 합니다.

public class Main {

    public static void main(String[] args) {

        Map<Person, Integer> map = new TreeMap<>();

        map.put(new Person(20, "홍길동"), 1);
        map.put(new Person(20, "홍길동"), 2);


        for (Person p : map.keySet()) {
            System.out.println(p);
        }

    }
}

class Person implements Comparable<Person> {


    int age;
    String name;

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

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }


    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
    }
}

 

Collection FramWork를 이해하고 응용한다는 것은

자료구조를 용도에 맞게 문제 해결에 더 적합한 것으로 선택해서 사용할 수 있음을 의미합니다.

 

도움이 되셨다면 좋겠습니다.