Collection Framework : List, Set, Map

1. Collection Framework

 

Collection Framework 은 데이터 군을 다루고 표현하기 위한 자료 구조이다.

자바에서는 Collection Framework에서 크게 List, Set, Map 이렇게 3 가지 형태의 인터페이스로 분류하였다.

이 중 List 와 Set 간의 공통 부분을 추출하여 인터페이스 Collection 를 만들었고, Map 은 Collection 과의 관계가 없다.

 

 JDK1.2 버전 이전에서는 Vector, Stack, Hashtable, Properties 와 같은 legacy 클래스가 쓰였으며, 

현재까지도 존재하지만 이는 이전에 작성된 코드와의 호환(하위 호환)을 위해 남겨둔 것으로 사용을 자제해야 한다.

 

2. Collection Framework 인터페이스

 

🔹 Collection interface

List 와 Set 의 조상 인터페이스인 Collection 에서 정의된 메서드는 자료 구조에 저장된 데이터를 읽고, 추가하고, 삭제하는 등의 메서드가 존재한다.

 

🔹 List interface

Collection 인터페이스를 상속 받은 List 인터페이스는 순서가 있는 데이터의 집합으로 index 로 관리 가능하다.

이러한 특성으로 데이터가 중복되어도 관리가 가능하고, 저장 순서가 유지된다는 장점이 있다.

 

🔹 Set interface

List 와 마찬가지로 Collection 을 상속 받은 Set 인터페이스는 List 와 달리 중복을 허용하지 않고, 저장 순서를 보장하지 않는다는 특징이 있다. 

 

🔹 Map interface

Collection Framework에 독자적으로 존재하는 Map 인터페이스는 키(key) 와 값(value)을 하나의 쌍으로 묶어서 저장한다.키와 값 한 쌍은 Entry 라는 단위로 다뤄지고 이는 Map 인터페이스 내부에 내부 인터페이스로 정의되어 있다.키는 List의 index 같은 역할을 하기 때문에 중복을 허용하지 않지만, 값에 대해서는 중복을 허용한다.만일 기존에 저장된 데이터와 동일한 키와 값을 저장하려고 하면, 기존 값을 덮어 쓰게 된다.

 

 

3. List 인터페이스 구현

 

🔹ArrayList

ArrayList는 List 인터페이스를 구현한 클래스로 List 와 같이 저장 순서가 유지되고 중복을 허용한다는 특징이 있다.

또한 기존의 Vector 를 개선한 것으로 유사성이 있기에 Vector 보다 ArrayList 사용을 추천한다.

내부적으로는 배열을 사용하고 있지만 사용자는 배열의 길이에 신경 쓰지 않더라도 내부 구현으로 큰 배열을 새로 생성하여 저장해준다.

 

🔹LinkedList

배열은 기본적인 자료 구조로 사용하기 쉽고 데이터에 대한 순차 접근으로 빠르게 읽을 수 있다는 장점이 있지만,

생성한 배열은 크기를 변경할 수 없어 보다 커질 때마다 복사를 해야 한다는 점과비순차에 대해 비교적 느려진다는 단점이 있기에 이를 해결하고자 LinkedList 가 만들어졌다.

LinkedList 는 데이터가 서로를 연결하고 있기 때문에 이러한 이름이 붙었는데

각 노드(LinkedList의 데이터 단위)는 자기 다음 노드의 주소를 저장하여 순서를 기억하는 형태로 구현되었다.

따라서 새로운 데이터의 삽입이나 기존 데이터의 삭제에 대해서는 해당 주소를 바꿔서 기억시키면 되기 때문에 비교적 처리 속도가 빨라지게 되는 것이다.

class Node {
	// 다음 노드 주소 저장
	Node next;
    // 자신이 저장한 데이터
    Object obj;
}

 

하지만 이러한 LinkedList에도 단점이 존재했는데, 바로 단방향 진행이다.

앞의 노드를 기억하기 때문에 뒤 쪽으로의 진행은 쉽게 할 수 있지만 이전으로는 접근이 어려운 것이다.

이를 극복하기 위해 나온 것이 Doubly Linked List(이중 연결리스트) 이다.

이중 연결리스트의 노드에는 이전 노드 주소를 저장하는 참조 변수가 하나 더 생기게 되었고,

이로 인하여 접근과 이동에 대하여 이점을 보게 되었다.

class Node {
	// 다음 노드 주소 저장
	Node next;
    // 이전 노드 주소 저장
    Node previous;
    // 자신이 저장한 데이터
    Object obj;
}

 

하지만 이 또한 맨 앞 노드와 맨 뒤 노드는 서로를 알 수 없게 되어 null 값으로 저장하게 된다.

그래서 이를 참조할 수 있도록 하는 Doubly Circular Linked List(이중 원형 연결리스트)가 구현되었다. 

이는 마치 텔레비전 채널을 돌리는 것으로 연상해보면 쉽게 이해할 수 있다.

첫 채널에서 뒤로 가면 마지막 채널이, 마지막 채널에서 앞으로 가면 첫 채널이 나오는 원리이다.

 

ArrayList 와 LinkedList 비교
1. 순차적으로 추가 / 삭제하는 경우, ArrayList 가 빠르다.
2. 비순차적으로 추가 / 삭제하는 경우, LinkedList 가 빠르다.
3. 데이터 접근은 ArrayList 가 빠르다.

 

 

4. Set 인터페이스 구현

 

🔹 HashSet

Set 인터페이스를 구현하고 해시 함수 이용하는 클래스이다.

Set 인터페이스를 구현하였기 때문에 중복을 허용하지 않는다는 특징이 있다.

이러한 특징으로 이미 있는 데이터를 추가하려고 하면 false를 반환한다.

 

그렇다면 HashSet 에서는 무엇을 중복이라고 인정하는 것일까.

class HashSetTest {
	public static void main(String[] args) {
    	
        HashSet set = new HashSet();
        
        set.add("abc");
        set.add("abc");
        set.add(new Person("David", 10);
        set.add(new Person("David", 10);
        
        System.out.println(set);
        
        실행 결과
        [abc, David:10, David:10]
    }
}

class Person {
	
    String name;
    int age;
	
    // 생성자 생략
}

코드를 짜며 기대하는 방향은 아마 [abc, David:10] 일 것이다.

하지만 HashSet 은 이름도 나이도 같은 David 를 서로 다른 객체라고 분류했고 따라서 추가를 허용하였다.

 

왜 다른 객체로 인지하게 되었을까?

이유는 간단하다. 

각 객체는 new 연산자를 통해 생성되었기 때문에 서로 다른 주소를 참조하게 되었기 때문이다.

 

이를 통해 알 수 있는 점은 코드 상에서 하나의 객체가 동일하다고 판별시킬 수 있는 방법은

주소값과 객체 내의 데이터 모두가 같아야 한다는 것이다.

 

class HashSetTest {
	public static void main(String[] args) {
    	
        HashSet set = new HashSet();
        
        set.add("abc");
        set.add("abc");
        set.add(new Person("David", 10);
        set.add(new Person("David", 10);
        
        System.out.println(set);
        
        실행 결과
        [abc, David:10]
    }
}

class Person {
	
    String name;
    int age;
	
    // 생성자 생략
    
    @Override
	public boolean equals(Object obj) {
    	return age == ((Person)obj).age && this.name.equals(((Person)obj).name);
	}
    
    @Override
	public int hashCode() {
		return Objects.hash(new Integer(age).hashCode(), name.hashCode());
	}
}

두 객체를 같은 값으로 인식시키기 위해서는 equals()와 hashCode() 메서드를 사용자 정의해야 한다.

equals()를 통해 객체에 저장된 멤버의 동일함을 판단하게 된다.

hashCode()를 통해서는 멤버를 통해 해시 코드를 반환하도록 하였다.

이로 인하여 같은 멤버를 가지면 같은 해시 코드를 같게 되는 것이고,  중복에 대한 처리가 완료되는 것을 확인할 수 있다.

 

하지만 HastSet은 저장 순서를 보장하지 않기 때문에 저장 순서를 보장하기 위해서 LinkedHashSet 을 사용하기도 한다.

 

🔹 TreeSet

TreeSet은 Set과 SortedSet을 구현한 클래스로 이진 검색 트리(Binary search tree)로 구현되었다.

이진 검색 트리는 정렬, 검색, 범위검색에 있어서 높은 성능을 보이는 자료 구조이다.

TreeSet은 이를 더 향상시킨 Red-Black tree 구조로 구현되어있다.

 

Set 인터페이스를 구현했기 때문에 중복을 허용하지 않고, 저장 순서를 유지하지 않는다는 특징을 가지지만

정렬 기준(c)에 따른 순서를 보장한다는 특징이 있다.

 

때문에 TreeSet에서는 정렬 기준이 굉장히 중요하게 작용한다.

만일 TreeSet 생성 시에 지정한 제네릭 타입이 comparable 또는 comparator 를 구현하지 않았다면,

인스턴스 자체는 생성이 되지만 정렬 기준이 없는 상태이기 때문에 예외가 발생하기 쉬워진다.

 

 이진 트리도 노드로 구성되어 있는데 멤버는 다음과 같다.

class TreeNode {
	
    // 왼쪽 자식 노드
    TreeNode left;
    // 객체 저장
    Object element;
    // 오른쪽 자식 노드
    TreeNode righ;
}

노드는 두 개의 '자식 노드'를 가질 수 있고,

자식 노드를 갖는 노드를 '부모 노드', 그렇지 못한 노드를 '리프 노드' 라고 한다.

이들의 최상위는 '루트 노드'라고 한다.

 

부모 노드의 왼쪽은 부모 노드보다 작은 값이, 오른쪽은 큰 값이 저장된다는 특징이 있다.

즉 데이터를 전부 넣으면 가장 왼쪽이 가장 작은 값이 들어가게 되고,

가장 오른쪽이 가장 큰 값이 들어가는 형태를 보이게 된다.

 

값을 추가하고 삭제할 때마다 정렬 기준에 따라 항상 비교하기 때문에 시간이 걸린다는 단점이 있지만,

정렬 기준에 따라 정렬이 되어 있기 때문에 검색에 유리하다는 특징이 있다.

 

 

5. Map 인터페이스 구현

 

🔹 HashMap

Map 을 구현했기 때문에 키와 값을 묶어서 하나로 관리하는 Entry 로 저장된다는 특징이 있다.

여기에 해시를 더했기 때문에 검색하는 데에 있어서 뛰어난 성능을 보인다.

 

키는 중복을 허용하지 않고, 값은 중복을 허용한다는 특징이 있는데,이로 인하여 같은 키 값으로 데이터를 추가하려고 하면 기존 값이 새로운 값으로 덮어 써진다는 사실을 잊으면 안 된다.

또한 null 값을 허용하기 때문에 map.put(null, null); 또는 map.get(null); 같은 작성을 할 수 있다.

 

키가 중복이 아니기 때문에 가능한 메서드가 바로 keySet() 이다.

Set 또한 중복을 허용하지 않기 때문에 Map 의 키는 Set 으로 만들 수 있게 되는 것이다.

 

Hashtable 은 legacy 이므로 하위 호환을 위하여 남겨 놓았기 때문에 HashMap을 이용하는 것을 추천한다.

 

🔹 TreeMap

이름에서도 알 수 있듯이 이진 트리의 형태이므로 검색과 정렬에 적합하다.

하지만 HashMap 이 보다 검색 측면에서 유리하고, 범위 검색과 정렬에 대해서는 TreeMap 이 유리하다.

 

 

6. Hashing

 

해싱이란 해시함수(Hash Function)를 이용하여 해시테이블(Hash Table)에 저장하고, 이를 검색하는 방식을 말한다.

 

구조는 배열와 링크드 리스트를 조합하여 사용하고 있다.

서류 분류를 생각하면 이해하기 쉽다.

배열을 연도별 서류함이라고 생각하고, 그 안에 분류되어 들어가는 서류가 링크드 리스트로 존재한다.

예를 들어 1978 년 관련 서류가 새롭게 추가된다고 생각해보자.

일단 70년대 서류함(배열)을 찾을 것이고, 해당 서류함을 열어 77년과 79년을 찾아 그 사이에 넣을 것(링크드 리스트)이다. 

 

하지만 앞서 이야기 했듯이 링크드 리스트는 검색에 있어서 데이터가 많아질수록 불리한 자료 구조를 가지고 있다.

때문에 하나의 배열에 하나의 데이터가 저장된 형태로 구성하게 되면 빠른 검색을 할 수 있게 된다.

그렇지만 분류 자체를 배열로 하기 때문에 배열의 길이를 변경해야 할 때 불편함이 생긴다는 단점이 있다.