JAVA의 정석 정독하기 #11 - Collection Framework

컬렉션 프레임워크 (Collection Framework) 란?

‘데이터 군’을 저장하는 클래스들을 표준화한 설계’를 뜻한다.

 

JDK 1.2 이전까지는 다수의 데이터를 저장해야할때

Vector, Hashtable, Properties와 같은 클래스를 이용해 서로 다른 각자의 방식으로 처리해야했다.

 

JDK 1.2부터 컬렉션 프레임워크가 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고

모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다.

 

핵심 인터페이스

컬렉션 프레임워크는 컬렉션 데이터 그룹을 크게 3가지 타입이 존재한다고 인식하고

각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다.

• List : 순서가 있는 데이터의 집단 (중복 가능)
• Set : 순서가 없는 데이터의 집단 (중복 불가능)
• Map : 키와 값의 쌍으로 이루어진 데이터의 집합 (키는 중복 불가능)

그리고 List와 Set을 구현한 컬렉션 클래스들의 공통부분을 Collection 부모 인터페이스로 다시 정의했다.

(Map은 List와 Set과는 다른 형태로 다루기 때문에 상속계층도에 포함되지 못했다.)

 

Vector, Stack, Hashtable, Properties와 같은 클래스들도 존재하지만

컬렉션 프레임워크가 만들어지기 이전부터 존재하던 클래스들이다.

 

이 클래스들도 컬렉션 프레임워크와의 호환을 위해 설계를 변경해서 남겨두었지만

이 클래스들은 컬렉션 프레임워크의 명명법, 사용법을 따르지 않으므로,

사용하지 않는 것이 좋다고 책에선 이야기한다.

(대신 ArrayList와 HashMap을 사용하라고 한다)

 

Collection 인터페이스

List와 Set의 공통 메서드를 뽑아 만든 인터페이스이다.

boolean add(Object o) 
boolean addAll(Collection c)

void clear()
boolean remove(Object o)
boolean removeAll(Collection c)

boolean contains(Object o)
boolean containsAll(Collection c)

int hashCode()
boolean equals(Object o)

boolean isEmpty()
int size()

 

다음과 같은 메서드를 제공한다.

메서드 이름만 봐도 무슨 역할을 하는지 알 것 같으니 개별 메서드에 대한 자세한 설명은 넘어간다.

위 메서드 외에도 iterator(), toArray() 등의 더 다양한 메서드가 존재한다.

 

앞서 설명했듯이 List와 Set에서 공통으로 사용하는 메서드들이므로

List와 Set 인터페이스를 구현하는 모든 클래스에서 사용하는 메서드들이다.

 

List 인터페이스

List 인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다.

배열과 다른 점은 크기가 변경될 수 있으므로 저장할 수 있는 데이터의 갯수가 가변적일때 유용하다.

boolean add(int index, Object element) // 지정된 위치에 객체를 추가한다
boolean addAll(int index, Collection c)

Object get(int index) // 지정된 위치에 있는 객체를 반환한다
int indexOf(Object o) // 특정 객체의 위치를 반환한다

Object remove(int index) // 특정 위치에 있는 객체를 삭제한 후 객체를 반환한다
Object set(int index, Object element) // 지정된 위치에 있는 객체를 변경한다
void sort(Comparator c) // 리스트를 정렬한다.

 

다음과 같은 메서드를 지원한다.

 

List는 순서가 있다는 것이 가장 중요한 특징이다.

특정 순서에 객체를 추가하거나 가져오거나 삭제하는 메서드들이 Collection 인터페이스에서 추가되었다.

 

인터페이스의 구현 클래스로는 ArrayList, LinkedList, (Vector), (Stack)이 존재한다.

 

ArrayList

“ArrayList는 컬렉션 프레임워크에서 가장 많이 사용되는 클래스일 것이다.” 

 

ArrayList는 List 인터페이스를 구현한 가장 대표적인 클래스이다.

 

기존에 존재하던 Vector를 개선한 것으로 구현원리와 기능적 층면이 동일하나

가능하면 ArrayList를 사용하라고 책에서는 이야기한다.

 

어떻게 구현되어 있는가?

ArrayList의 소스코드를 보면 elementData라는 이름의 Object 배열을 멤버 변수로 선언하고 있다.

ArrayList는 이 배열을 이용해 데이터를 순차적으로 저장한다.

 

그렇다. ArrayList는 이름에 맞게 기본적으로 배열을 이용해 데이터를 저장한다.

그런데 배열의 크기는 고정적인거 아닌가요? List는 크기가 변경된다면서요? 라는 질문이 나온다.

 

ArrayList는 데이터를 저장할때 다음과 같은 방식으로 저장한다.

1. Object 배열을 생성해 데이터 저장 (기본 크기는 10)
2. 배열에 더 이상 공간이 없으면 더 큰 새로운 배열을 생성 (원래 크기의 1.5배)
3. 기존의 내용을 복사한 다음 그 뒤부터 다시 데이터 저장.

즉 상황에 맞게 내부적으로 더 큰 배열을 만들어 값을 복사하는 방식으로 데이터를 관리한다.

 

따라서 처음 설정 크기보다 더 많은 데이터를 넣어 중간에 배열의 크기를 증가시키거나 배열 중간에 요소를 추가 혹은 삭제할경우

배열을 통채로 복사하거나, 값을 순서대로 모두 이동시켜야하기 때문에 데이터가 많다면 성능 저하의 요소가 될 수 있다.

 

따라서 처음 생성할때 저장할 요수의 개수를 고려해 실제 저장할 개수보다 약간 여유있는 크기로 하는 것이 좋다.

 

LinkedList

링크드 리스트는 비순차적 데이터의 추가, 삭제에 시간이 많이 걸린다는 배열의 단점을 보완하는 자료구조이다.

불연속적으로 존재하는 데이터를 참조를 통해 서로 연결한 형태로 구성되어 있다.

 

새로운 데이터를 추가할때 새로운 요소를 생성한 이후,

추가하고자 하는 위치의 이전요소의 참조만 고친 후 새로운 요소가 그 다음 요소를 참조하도록

변경하기만 하면 되므로 처리 속도가 매우 빠르다.

 

더블 링크드 리스트는 이전 요소에 대한 접근을 위해 이전 요소에 대한 참조가 가능하도록 추가한 자료구조이다.

 

자바의 LinkedList는 더블 링크드 리스트로 구현되어 있다.

 

이러한 구조때문에 다음과 같은 장단점을 가진다.

• 비순차적인 추가/삭제 시 처리 속도가 ArrayList보다 빠르다.
• 그러나 순차적인 추가/삭제(stack구조)시에는 ArrayList보다 느리다.
• 특정 인덱스의 데이터를 탐색할때 순차적으로 탐색해야 하므로 (get(i)메서드 사용 시) 배열과 ArrayList보다 느리다.

 

Set 인터페이스

Set 인터페이스는 중복을 허용하지 않는 컬렉션 클래스를 구현한다.

또한 LinkedHashSet 같은 경우를 제외하고 기본적으로는 저장 순서도 보장하지 않는다.

구현 클래스로는 HashSet, TreeSet 등이 있다.

 

HashSet

Set를 구현한 가장 대표적인 컬렉션이며, Set의 특징대로 중복된 요소를 저장하지 않는다.

새로운 요소를 추가할때 add(Object o) 메서드를 사용하는데

이때 중복된 요소를 추가하고자 하면 false를 반환해 실패했다는 것을 알린다.

 

해시코드를 이용해 객체를 저장하고 가져오며 중복이 있는지를 확인한다.

즉 저장 전 중복 확인시에 equals() 메서드와 hashCode() 메서드를 호출해 판별하므로

HashSet에 저장하려는 클래스는 equals()와 hashCode() 메서드를 오버라이딩해줘야 한다.

class Student{
    int age;
    String name;
    
    public boolean equals(Object other){
        if (other instanceof Student){
            Student o = (Student) other;
            return (this.age == o.age) && (this.name == o.name);    
        }
        return false;
    }
    
    public int hashCode(){
        return Objects.hash(this.age, this.name);
    }
}

 

오버라이딩된 hashCode()는 다음의 세 조건을 만족시켜야 한다.

• 실행 중인 어플리케이션 내의 동일한 객체에 대해 여러번 hashCode()를 호출해도 동일한 값을 반환해야한다.
• equals() 메서드에서 true가 나온 두 메서드의 hashCode() 값은 반드시 같아야 한다.
• equals() 메서드에서 false가 나온 두 메서드의 hashCode() 값이 같아도 괜찮지만, 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해선 다른 값을 반환하는 것이 좋다.

TreeSet

TreeSet은 이진 검색트리(binary search tree) 형태로 데이터를 저장하는 컬렉션 클래스이다.

(정확히는 이진 검색 트리의 성능을 향상시킨 ‘레드-블랙 트리’로 구현되어 있다)

 

이진 검색트리로 구현되어 있으므로 당연히 단일 값 검색, 범위 검색이 매우 빠르다는 장점을 가진다.

그러나 데이터를 순차적으로 저장하는 것이 아닌, 저장위치를 찾아 저장하고 재정렬하며,

데이터 삭제시에는 트리 일부를 재구성해야 하므로 링크드 리스트보다 데이터의 추가, 삭제 시간은 더 걸린다.

 

Map 인터페이스

Map 인터페이스는 키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는데 사용된다.

키는 중복을 허용하지 않지만, 값은 중복을 허용한다.

boolean containsKey(Object key) // 특정 키가 있는지 확인한다
boolean containsValue(Object value) // 특정 값이 있는지 확인한다

Set entrySet() // key-value 쌍을 Map.Entry타입 객체로 저장한 Set을 반환한다
Set keySet() // 모든 key 객체를 반환한다
Collection values() // 모든 value 객체를 반환한다

Object get(Object key) // key로 value 객체를 찾아 반환한다
Object put(Object key, Object value) // key-value 쌍을 추가한다
Object remove(Object key) // key와 일피하는 key-value를 삭제한다

다음과 같은 메서드들이 정의되어 있다.

 

구현 클래스로는 HashMap, LinkedHashMap, TreeMap, (Hashtable) 등이 있다.

 

Map.Entry 인터페이스란?

Map 인터페이스 내부 인터페이스이다.

Map에 저장되는 key-value 쌍을 다루기위해 내부적으로 정의해놓았다.

Map 인터페이스를 구현하는 클래스에서 함께 구현하고 있다.

Map을 구현하는 클래스들은 key와 value를 따로 배열로 저장하지 않고 Entry 객체 배열을 만들어 다룬다.

 

 

HashMap

Map을 구현한 클래스로 앞서 설명한 HashSet처럼 해싱을 이용해 데이터를 저장하고 탐색한다.

해싱을 이용하므로 저장하려는 key값에 클래스를 이용하려면

equals(), hashCode() 메서드를 오버라이딩해줘야 한다. (보통은 String을 사용한다)

 

JAVA에서 HashMap 구현에 대해 잘 정리해둔 글이 있어 가져와봤다.

https://d2.naver.com/helloworld/831311

 

요약하면 HashMap이 완전한 해시 테이블을 구현하는 것은 사실상 불가능하다.

 

왜냐하면 java의 hashCode() 메서드는 int 값을 반환하도록 되어있는데

데이터의 개수가 2^32개보다 많을 수 있으며, 길이가 2^32인 배열을 사용하는 것은 메모리 부담이 크다. 

 

그래서 JAVA에선 해시 값을 M으로 나눈 값을 사용하고, (기본값은 16)

데이터가 중복될 경우 링크드 리스트 형태로 연결해 저장하는 방식을 채택했다.

(JAVA 8부터는 링크드 리스트 요소가 일정 개수 이상일 경우 트리 형태로 전환한다.)

 

또한 특정 값 이상의 데이터가 쌓이면 M을 2배로 늘리고,

나머지 값을 적용하더라도 해시값 분포가 균등하도록 보조 해시 함수를 적용했다.

 

참고로 HashSet은 내부에 HashMap과 Object 하나를 생성해

들어오는 데이터를 <데이터, Object> key&value 쌍으로 HashMap에 저장한다.

 

TreeMap

이름에서 알 수 있듯이 이진검색트리의 형태로 데이터를 저장한다.

TreeSet과 동일한 장단점을 가진다.

 

HashMap이 Hash를 사용하기 때문에 단일 검색은 HashMap이 성능이 더 좋은 경우가 많다.

다만 범위검색이나 정렬이 필요한 경우는 TreeMap을 사용하는 것이 더 좋다고 이야기한다.

 

Iterator

컬렉션 프레임워크에선 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화하였는데

그 방법이 바로 Iterator 인터페이스이다.

 

Collection 인터페이스에는 Iterator를 구현한 클래스의 인스턴스를 반환하는 iterator() 메서드를 정의하고 있다.

이 메서드는 당연시 List와 Set에도 포함되어 있다.

boolean hasNext() // 읽어올 요소가 있는지 확인한다
Object next() // 다음 요소를 읽어온다
void remove() // next()로 읽어온 요소를 삭제한다.

컬렉션 클래스에서 iterator()를 호출하여 Iterator를 얻은 다음 메서드를 이용해 컬렉션의 요소를 읽어올 수 있다.

Colleciont c = new ArrayList();
		
Iterator it = c.iterator();
		
while(it.hasNext()){
		System.out.println(it.next());
}

다음과 같이 주로 while 반복문을 사용해 데이터를 순차적으로 읽어온다.

List c = new ArrayList();

for (Object st : c){
		System.out.println(st.toString());
}

for (int i = 0; i < c.size(); i++){
		System.out.println(c.get(i));
}

그런데 그냥 위 코드처럼 for문에 컬렉션 넣고 확인하면 되는거 아닌가? 라는 생각이 든다.

 

Iterator의 핵심은 Collection 프레임워크에서 공통으로 사용할 수 있다는 점이다.

위의 for문 코드는 만약 Collection의 구현체로 List가 아닌 Set를 사용한다면 코드를 전부 고쳐야한다.

 

그러나 Iterator를 사용한다면 Collection 인터페이스를 구현하는 어떤 클래스를 사용하더라도

저장된 요소를 확인하는 코드는 고치지 않아도 된다.

다형성이 구현된 것이다!

 

ListIterator?

Iterator를 상속받아 기능을 추가한 것으로, Iterator는 단방향으로만 접근 가능하지만

ListIterator는 hasPrevious(), previous() 메서드가 존재해 양방향으로 이동이 가능하다.

다만 ArrayList, LinkedList와 같은 List 인터페이스를 구현한 컬렉션에서만 사용이 가능하다.

 

Comparator과 Comparable

collction의 sort() 메서드 혹은 Arrays.sort() 메서드를 호출하면 알아서 요소들을 정렬하는것 처럼 보이지만,

사실은 Comparable 의 구현에 의해 정렬된 것이다.

 

너무 잘 정리해놓은 블로그가 있길래 가져와봤다.

자바 [JAVA] - Comparable 과 Comparator의 이해

자바 [JAVA] - Comparable 과 Comparator의 이해

 

요약하자면 Comparable과 Comparator은 둘 다 객체를 비교하기 위해 사용하는 인터페이스이며

Comparable을 구현하는 객체는 Comparable은 compare(Object o)를

Comparator는 compare(Object o1, Object o2)만 구현하면 된다.

 

보통 직접 만든 클래스를 기준에 따라 정렬하거나 비교해야할 필요가 있을 때 사용하며

Comparable의 compare 메서드를 내부에 구현하거나

Comparator을 구현하는 익명 클래스를 만들어 sort()시에 파라미터로 넣어준다.