Collection

자바가 가지고 있는 컬렉션은 상황에 따라 필요한 여러가지 자료구조를 제공합니다. 이를 이용해 손 쉽게 대용량의 데이터를 관리할 수 있습니다.

컬렉션 역시 객체이고, 컬렉션 인터페이스를 구현하고 있습니다.

컬렉션 인터페이스를 구현하지는 않지만 map 역시 자바의 컬렉션 프레임워크의 일부로 간주되고 있습니다.

컬렉션 프레임워크를 간단하게 살펴보겠습니다.

List 인터페이스를 구현한 A클래스는 모두 순서를 가지고 있습니다. 따라서 순서가 중요한 경우 list를 사용합니다. (vector와 arraylist 차이는 동기화, null값 허용 여부)

Set은 오로지 값만을 가지고 인덱스나 키 값을 가지고 있지 않습니다. 때문에 유일성이 중요할 때 사용합니다.

Map은 키값을 가지고 있습니다. 순서는 중요하지 않지만 이름/값 으로 쌍을 이루는 데이터에서 사용합니다. (hashmap 과 hashtable 차이는 동기화와 null값 허용 여부)

arraylist는 배열 형태로 자료를 저장하고 순서를 가지고 있습니다. 그렇기 때문에 저장된 데이터에 접근하는데 상수시간만큼 소요되고 무작위로 접근할 수 있습니다.

배열의 사이즈는 초기에 고정되어 있기 때문에 배열의 크기 이상으로 데이터가 저장되면 사이즈를 늘려주는 연산이 추가 되어야 합니다.

1. n개의 자료를 저장할때 ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장

2. 무작위접근(random access) 가능

3. 사이즈 고정되어 있음

4. 삽입 시 사이즈를 늘려주는 연산 추가되야 함

5. 삭제 시에는 순차적인 인덱스 구조로 인해 삭제된 빈 인덱스를 채워야 하기 하기 때문에 연산이 추가되어야 함

6. 지속적으로 삭제 되는 과정에서 공간만큼 낭비되는 메모리가 많음

7. 삽입 삭제가 빈번하게 발행하는 프로세스의 경우 좋지 않음

만약 데이터를 배열의 중간에 삽입하게 된다면 뒤에 있는 데이터들을 한칸씩 뒤로 밀어 공간을 확보합니다.

반대로 중간에 데이터가 삭제되면 순서 유지를 위해 데이터를 한칸씩 당겨 옵니다.

이런 연산이 지속적으로 발생하기 때문에 자료의 삽입, 삭제가 빈번한 작업의 경우 적합하지 않은 자료구조입니다.

링크드리스트 역시 순서를 가지는 자료구조입니다. 하지만 다음 데이터의 위치를 아는 참조자를 이용해서 순서를 파악하기 때문에 접근하기 위해서는 순차적으로 리스트를 따라가야 합니다.

또 메모리 공간상에 데이터가 불연속적으로 저장되고, 참조자를 사용하는데 추가적인 메모리가 사용됩니다.

1. 연결형태로 연결 가능

2. ArrayList처럼 뒤로 밀거나 채우는 작업 없이 주소만 서로 연결시켜 주면 되기 때문에 추가 삭제가 ArrayList보다 빠르고 용이함.

3. 삽입삭제가 빈번하게 발생되면 Linked List을 사용해 시스템 구현이 바람직함.

4. 순차접근(sequential access)만 가능

5. 단순 LinkedList 는 단방향성을 갖고 있어 인덱스를 이용해 자료를 검색하는 애플리케이션에 적합하지 않음

6. 순차접근도 참조의지역성(한번 참조한 데이터는 다시 참조될 가능성이 높음) 때문에 LinkedList보다 ArrayList가 훨씬 빠름.

7. n개의 자료를 저장할때 LinkedList는 자료들을 저장공간에 불연속적인 단위로 저장

8. LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됨

9. LinkedList는 참조자를 위해 추가적인 메모리를 할당해야함(자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가 적인 메모리할당은 비실용적임)

링크드 리스트에 새로운 데이터를 추가할 때는 다음 노드의 위치만을 바꿔주면 되기 때문에 다른 연산 작업이 필요하지 않아서 arraylist에 비해 더 짧은 시간이 걸립니다.

삭제를 할 때도 다음 노드의 위치만을 바꿔주면 됩니다.

hash는 hash 함수에 의해 만들어진 값을 말합니다. 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.

각 객체의 해시값을 이용해 중복 여부를 판별하는 것이 hashset이고, 이 hash 값을 인덱스 혹은 주소로 삼아 데이터를 저장하는 것이 해시 맵, 해시 테이블 입니다.

hash를 사용한 자료구조는 속도 면에서 장점을 가지지만 hash와 데이터를 매핑하는 메모리 공간이 따로 필요하다는 점, 다른 객체가 같은 해시값을 가지는 해시 충돌이 발생 한다는 점 등의 단점이 있습니다.

hashmap은 키값을 통해 얻은 해시코드를 인덱스로 삼아 테이블을 만듭니다. 그리고 진짜 값이 저장된 곳의 위치를 매핑합니다. 이렇게 하면 접근하는데 상수시간만큼이 걸리게 되기 때문에 속도 면에서 큰 이점을 얻을 수 있지만 별도의 인덱스 테이블을 구성해야 한다는 단점이 있습니다.

TreeSet은 이진탐색트리(BinarySearchTree)의 형태로 데이터를 저장하는 컬렉션입니다. TreeSet은 마찬가지로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지 않습니다. 자료가 항상 정렬된 상태로 저장되기 때문에 항상 정렬된 데이터가 필요할 때 유용하게 사용할 수 있습니다. 이 때 접근 속도는 O(logN) 입니다.

자바 콜렉션에서는 손쉽게 정렬하는 방법을 제공하고 있습니다.

Collections 클래스에 있는 sort() 메소드를 호출하면 List 인터페이스를 구현한 List를 인자로 넘길 수 있습니다. 그리고 넘긴 인자가 오름차순으로 정렬되게 됩니다.

하지만 이 때 정렬할 수 있는 것은 Comparable 객체로 구성된 목록 뿐입니다. 만약 Comparable의 하위 유형이 아닌 클래스 유형을 정렬하려고 한다면 이 방법을 사용할 수 없습니다. 때문에 정렬하고자 하는 클래스 유형은 Comparable 인터페이스를 구현해야 합니다.

comparable을 구현한 클래스는 위에서 처럼 compareTo() 메소드를 구현합니다.

Comparable 인터페이스를 구현하지 않고 두 객체를 비교할 수 있는 방법은 comparator를 구현한 클래스를 이용하는 것입니다.

comparator와 comparable의 차이점은 comparable은 같은 유형의 다른 원소와 비교하는 compareTo 메소드를 이용하지만 comparator는 그 자체가 별도의 클래스이기 때문에 원하는대로 마음껏 만들 수 있다는 점입니다.