Java – Collection – Set

> Set (Interface)

  Set 은 중복 Element를 허용하지 않는 Collection의 종류이다.  또한 Set을 구현한 자료형들은 서로 equals와 hashCode를 이용하여 비교할 수 있게 엄격한 조건을 가지고 있다.  동일한 Element를 가지고 있는 Set의 두 구현체들은 서로 구현방법이 달라도 equals를 만족한다.  (이는 결국 동일한 객체만 중복으로 보지 않는다는걸 의미하기도 한다.)

 

> HashSet

  HashSet은 일반적으로 알고 있는 HashTable의 구조를 가진다.  내부적으로는 사실 HashMap을 기반으로 구현되어 있다.  Key-Value로 구성된 HashMap 에서 Key만을 사용하는 것으로 볼 수 있다.   Value는 불변객체를 이용해 Dummy값으로 설정한다.  또한 HashMap의 특징 처럼 Element가 추가된 순서 혹은, 특정 순서와 관계 없이 순회가 이루어진다. (Ordering 보장하지 않는다.)  또한 Null요소를 허용한다.  (중복 불허용이니, 결국 1개의 Null)
   Hash함수가 버킷간에 Element를 적절히 분산 시킨다는 가정하에 기본 작업 (add, remove, contains, size)에 일정한 시간 성능을 제공한다 .  iterator를 이용해 핸들링하려면, HashSet 인스턴스의 사이즈 (Element 수)와, 초기 HashSet 생성자의 (capacity)를 설정한 경우 잔여 공간의 합계에 비례 한 시간이 필요하다.  따라서 iterator 이용할 때 성능이 중요 할 경우 초기 용량을 알맞게 설정하는 것이 중요하다.

  HashSet은 기본적으로 non-thread safe하다. (동기화를 보장하지 않는다.)  복수의 thread가 동시에 HashSet를 이용하려면 외부적으로 동기화를 구현하거나,  Collections.synchronizedSet 메소드를 사용하여 Wrapping 하여 사용하여야 한다.

Set s = Collections.synchronizedSet (new HashSet (…));

 

> TreeSet

  NavigableSet 인터페이스의 구현체인 TreeSet은 실제 구현 Source를 보면 버킷(Element를 담는 공간)으로 TreeMap을 이용한다.  Element는 Natural Order (객체별 기본 Comparable 인터페이스 구현에 의한 compareTo 결과)로 정렬되거나 생성자에 부여된 Comparator에 의한 순서로 정렬 된다.

TreeSet의 버킷으로 이용되는 TreeMap은 Self-balancing Binary Search Tree의 종 류중 하나인 Red-black Tree 방식으로 내부 Element를 구조화 한다.

동기화 관련해서는 HashSet과 같은 특징을 가진다.

 

 

 

 

Java – Collection – List

> List (Interface)

  List Interface를 구현한, 자료구조 Class들의 특징을 이야기 하려고 한다.  List는, 소속된 Element의 순서가 있는 Collection 종류이다.   각 Element가 삽입되는 위치를 정확하게 제어 할 수 있다.  또한 정수로 되어있는 Index를 이용해 Element 접근할 수 있다.

  Set과 달리 List는 일반적으로 중복 요소를 허용한다.  문법적으로 이야기 하자면, 일반적으로 List는 e1.equals(e2)가 허용되는 소속 Element들이 존재할 수 있다.  그리고 일반적으로 null Element를 허용하는 경우 여러 개의 null Element를 허용한다.

Iterator를 이용하여 Element의 삽입 및 교체, 접근 등이 가능하며 구현체들은 Iterator를 얻기위한 메서드를 제공한다.

  List를 구현한 구현체로는 ArrayList와 LinkedList가 일반적으로 사용된다. 

  Element로의 접근 및 검색, 삽입, 삭제 등 에서 두 구현체는 구현방법에 따른 성능차이를 보인다.  경우에 따라 ArrayList와 LinkedList가 더 적합한 경우가 존재한다.  

 

> ArrayList

Element들을 저장하는 방법에 있어서 Array[배열]를 사용한다.   그러므로 배열의 장점 및 단점을 어느 정도 공유한다.  예를 들면, Index를 이용해 각 Element에 Direct로 접근 할 수 있는 장점이 있으며, Array가 초기 Size가 정해져 있는 단점이 있어 확장이 용이하지 않은 단점을 가지고 있다.  단지 ArrayList는 System.arraycopy를 이용해 특정 Size를 넘어가면 자동 확장하게 구현되어 있다.  그러나 분명 자동 확장이라 하더라도 확장할때의 성능 저하는 존재한다.   그러한 점 때문에 ArrayList는 초기 생성 할 때 배열의 초기 Size를 지정할 수 있다.  (DEFAULT_CAPACITY = 10)  어느 정도 크기가 예상될 경우 기본 크기를 그에 맞게 초기에 설정하는 것이 성능상 유리하다.

또한 List의 중간에 Member의 추가 및 삭제가 이루어질 경우도 부하가 존재한다.  배열의 구조를 생각한다면 당연하게 생각 될 것이다.

ArrayList 배열은 일단 확장하고 나면, Element들을 삭제하여도 그 배열 크기는 줄어들지 않는다.  Element의 수가 계속해서 늘었다 줄었다 한다면 ArrayList는 최적의 선택이 아닐 수 있다.

 

> LinkedList

Element들을 저장하는 데 배열을 이용하지 않고, 리스트 안에서 다음 Element를 가리키는 내부 객체를 이용한다.  LinkedList의 각 Element는 해당 Element의 고유 객체(item)와 함께 다음 Element를 가리키는 재귀적 타입인 next라는 필드를 가지고 있다.  또한 prev라는 필드는 직전의 Element를 가리킨다.   이를 이용하면 리스트 사이를 쉽게 이동할 수 있고 순서대로 각 원소를 찾아 처리할 수도 있다.  이러한 특징은 ArrayList의 단점을 없에 준다.  List의 중간에 삭제나 삽입이 이루어지기 수월하고, 확장에 따른 부하가 존재하지 않는다.  그러나 ArrayList가 가지고 있는 장점이 LinkedList에서는 단점이 된다.   Index를 이용한 Element로의 Direct접근이 불가능하다.  get(int index)를 이용할 경우 LinkedList는 List의 첫 요소 부터 혹은 끝부터 List를 순회하여 해당 index를 찾도록 구현 할 수 밖에 없는 것이다. 

 

> ArrayList와 LinkedList의 성능 비교

 

 

Java – Collection 개요 (자료구조)

> 필요없는 사족 (Posting 계기)

Java – Collection에 관한 참고자료 및 Post, 책 등은 사실 이렇게 중복 Post를 할 필요가 없을 정도로 많고 쉽게 찾아 볼 수 있다.  알고리즘에 대해 이야기 할 때, 그리고 자료구조 혹은 Data 핸들링을 위한 이야기 들 가운데 항상 등장한다.  하지만 여기 저기 흩어진 각자의 정리방법, 혹은 Tip들에 대해 블로그 Category로 모을 수 있으면 어떨까 하는 생각에 Posting작업을 시작하게 되었다.

Java를 다루는 이에게 Collection이란 기초적이면서도, 언제든 다시 상기해야 하는 시점이 오는 주제가 아닌가 싶다.

끈기 있게 할 수 있을지 모르겠다.  될 수 있으면 각 개별 Collection들의 특징, 혹은 관련된 Tip, 비교 자료 등을 빠짐없이 이 blog-Category에 모을 수 있다면 하는 소망이 있다.
(단순히 link하는 정도를 넘어)

 

> Java – Collection

Collection은 배열과 같은 다른 객체를 저장, 핸들링하는 것을 목적으로하는 객체이다.   배열과 달리 Collection에는 요소의 일부를 반환하고 변환 및 정렬 등의 메서드를 포함하고 있다.  또한 Collection은 primitive type(int, long, boolean 등)을  요소의 type으로 지정할 수 없다. (하지만 primitive type에 대응되는 wrapper Class를 사용할 수 있다. 예: int -> java.lang.Integer)

모든 Collection 객체는 궁극적으로 java.util.Collection 인터페이스를 구현한다.  그러나 인터페이스를 직접 구현하는 경우는 별로 없다.  Collection 추가 메소드를 지정하는 여러 하위 인터페이스가 있다.  이러한 하위 인터페이스들은 Collection의 기능을 결정한다.  개별 클래스는 일반적으로 구현방식에서만 차이를 보인다. (예를 들어, 모두 ArrayList와 LinkedList는 List의 일반적인 기능을 모두 만족하지만, 내부 구현 방식에 있어 차이를 보인다.)

Collection 인터페이스 의 대부분의 구현은 java.util에 있다.

Map은 Collection 인터페이스를 상속하지 않음에도 불구하고,  일반적으로 Collection을 이야기 할때 항상 포함되기에 함께 이야기해보겠다.

 

> Java Collection 구조

 

> 자료구조 별 일반 특징 비교 (대분류)

 

> 주요 자료구조 별 특징 비교 (실구현 Class)

 

> 참고 URL