자바 자료구조

컴퓨터는 현실 세계에 존재하는 반복적이거나 복잡한 자료 처리를 효율적으로 처리하기 위한 전자 장치이다. 컴퓨터를 이용한 자료 처리를 위해서는 무엇보다도 먼저 자료를 컴퓨터가 다룰 수 있도록 컴퓨터 내에 표현해 주어야만 한다. 그리고 이렇게 표현된 자료를 컴퓨터는 일정한 절차를 통해 처리하게 된다. 자료구조란 처리하고자하는 자료들 사이의 관계를 고려하여 컴퓨터 내부에 표현하는 방법들을 총칭하는 말이다. 이는 자료 처리의 성능과 효율에 직접적인 영향을 미친다. 따라서 자료구조는 현실 세계의 실제 자료들의 관계를 잘 반영할 수 있어야 하고, 필요할 때 자료 처리를 효율적으로 수향할 수 있도록 간단명료해야만 한다. 그리고 이렇게 자료구조로 표현된 자료들을 이용하여 자료들을 처리하는 절차들의 모임을 알고리즘이라 할 수 있다. 대부분의 언어는 일정 수준의 모듈개념을 가지고 있으며, 이는 자료구조가 검증된 구현은 감춘 채 인터페이스만을 이용하여 다양한 프로그램에서 사용되는 것을 가능하게 해준다. C++나 자바와 같은 객체지향 프로그래밍 언어는 특별히 이러한 목적으로 객체를 사용한다. 이러한 자료 구조의 중요성으로 말미암아, 최근의 프로그래밍 언어 및 개발 환경은 다양한 표준 라이브러리를 제공하고 있다. 예로, C++의 표준 템플릿 라이브러리나 자바의 자바 API, 마이크로소프트 .NET과 같은 것을 들 수 있다.

자바에서는 java.util패키지 안에 이러한 자료구조의 기반이 되는 컬렉션 프레임웍이 있다. 컬렉션 프레임웍이란 데이터 군을 저장하는 클래스들을 표준화한 설계를 뜻한다. Java API문서에서는 이를 데이터 군을 다루고 표현하기 위한 단일화된 구조라고 정의하고 있다. 컬렉션은 다수의 데이터, 즉 데이터 그룹을, 프레임웍은 표준화된 프로그래밍 방식을 의미한다. 컬렉션 프레임웍은 컬렉션을 다루는 데 필요한 다양하고 풍부한 클래스들을 제공하기 때문에 프로그래머의 짐을 상당히 덜어 주고 있으며, 또한 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있기 때문에 사용법을 익히기에도 편리하고 재사용성이 높은 코드를 작성할 수 있다는 장점이 있다.

컬렉션 프레임웍은 여러 인터페이스들을 제공한다. 컬렉션 프레임웍에서는 컬렉션을 크게 세 가지 타입이 존재한다고 인식하고 각 컬렉션을 다루는데 필요한 기능을 가진 세 개의 인터페이스 즉 List, Set, Map을 정의하였다. 그리고 인터페이스 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의 하였다. List와 Set을 구현한 컬렉션 클래스들은 서로 많은 공통부분이 있기 때문에 공통된 부분을 다시 뽑아 Collection인터페이스를 정의할 수 있었지만, Map인터페이스는 이들과는 전혀 다른 형태로 컬렉션을 다루기 때문에 같은 상속계층도에 포함되지 못했다. 이러한 설계는 객체지향언어의 장점을 극명히 보여 주고 있다. 다음은 컬렉션 프레임웍의 핵심 인터페이스간의 상속계층도이다.

컬렉션 프레임웍의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나로 구현하고 있으며, 구현한 인터페이스의 이름이 클래스의 이름에 포함되어있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있도록 되어있다. 그러나 Vector, Stack, Hashtable, Properties와 같은 클래스들은 컬렉션 프레임웍이 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임웍의 명명법을 따르지 않는다.

지금부터 컬렉션프레임웍의 인터페이스들을 하나하나 살펴보겠다.

먼저Collection인터페이스를 보면, Collection인터페이스는 컬렉션 클래스에 저장된 데이터를 일고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의하고 있다.

다음으로 List인터페이스이다. List인터페이스는 순서가 있는 데이터의 집합이다. 이는 데이터의 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다. List인터페이스를 구현한 클래스로는 ArrayList, LinkedList, Vector, Stack 등이 있다. 예를 들어 은행에서 볼일을 보려고 은행창구에서 기다리는 손님들을 모아 놓았다면, 손님들의 "모임"이라는 측면에서 Collection이며, 좀 더 구체적으로는 손님들 간에 대기번호표를 기준으로 "모임"에는 순서가 있으므로 List라고 할 수 있다. 즉, 은행에서 볼일을 보려고 창구가 비기를 기다리는 손님들은 Collection이기도하며, List이기도 하다. 다음 그림은 List인터페이스의 상속계층도이다.

다음은 Set인터페이스이다. Set인터페이스는 순서를 유지하지 않는 데이터의 집합이다. 이는 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는 데 사용된다. Set인터페이스를 구현한 클래스로는 HashSet, TreeSet 등이 있다. 이 때 SortedSet은 인터페이스이지 Set인터페이스를 구현한 클래스가 아니다. 예를 들어 로또 당첨 번호 6개는 Collection 이면서 Set 이라고 생각할 수 있다. 또한 양의 정수 집합, 소수의 집합 같은 것도 Set의 예가 될 수 있다. 다음은 Set의 상속계층도이다.

다음은 Map인터페이스이다. Map인터페이스는 키(key)와 값(value)을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용된다. Map이란 개념은 어떤 두 값을 연결한다는 의미에서 붙여진 이름이다. 여기서 키는 중복될 수 없지만 값은 중복을 허용한다. 이는 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다. 즉, 기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다. Map인터페이스를 구현한 클래스로는 Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap 등이 있다. Map인터페이스의 메서드 중 values()는 값(value)은 중복을 허용하기 때문에 반환타입이 Collection이고, keySet()은 키(key)는 중복을 허용하지 않기 때문에 반환타입이 Set인 것이다. Map의 예로는 우편번호, 지역번호 등을 들 수 있다. 다음은 Map의 상속계층도이다.

Map인터페이스의 내부 인터페이스인 Map.Entry인터페이스도 있다. 내부 클래스와 같이 인터페이스도 이처럼 인터페이스 안에 인터페이스를 정의하는 내부 인터페이스를 정의하는 것이 가능하다. Map에 저장되는 key-value쌍을 다루기 위해 내부적으로 Entry인터페이스를 정의해 놓았다. 이것은 보다 객체지향적으로 설계하도록 유도하기 위한 것으로 Map인터페이스를 구현하는 클래스에서는 Map.Entry인터페이스도 함께 구현해야 한다.

이제부터는 컬렉션 프레임웍의 구성요소들을 하나씩 살펴보겠다.

먼저 Vector와 ArrayList를 함께 비교하며 알아보자. Vector는 ArrayList와 함께 컬렉션 프레임웍에서 가장 많이 사용되는 컬렉션 클래스이다. ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다. 이 둘은 List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 공통점이 있다. 또한 데이터의 저장 공간으로 배열을 사용한다는 공통점이 있다. Vector와 ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장한다. 예를 들면, 첫 번째로 저장한 객체는 Object배열의 0번째 위치에 저장되고 그 다음에 저장하는 객체는 1번째 위치에 저장된다. 이런 식으로 계속 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다. 그러나 Vector는 멀티쓰레드에 대한 동기화가 되어 있으나 ArrayList는 그렇지 않다는 차이점이 있다. ArrayList는 동기화를 필요한 경우에만 java.util.Collections클래스의 동기화 메서드를 이용하여 처리 가능하다. Vector와 ArrayList 같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 상당히 효율이 떨어진다는 단점을 가지고 있다. 그래서 처음에 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋다.

몇 가지 예제를 통해 Vector와 ArrayList를 좀 더 살펴보겠다. 예제들은 교재의 예제 11-1, 11-2, 11-3, 11-4이다. 먼저 예제들에 대한 간략한 설명 후 예제를 보겠다.

[예제 11-1]은 ArrayList의 기본적인 메서드를 이용하여 객체를 다루는 방법을 보여 준다. ArrayList는 List인터페이스를 구현했기 때문에 저장된 순서를 유지한다는 것을 알 수 있다. 그리고 Collections클래스의 sort메서드를 이용해서 ArrayList에 저장된 객체들을 정렬하였다.

[예제 11-2]는 긴 문자열 데이터를 원하는 길이로 잘라서 ArrayList에 담은 다음 출력하는 예제이다. 단순히 문자열을 특정크기로 잘라서 출력할 것이라면, charAt(int i)와 for문을 이용하면 되겠지만 ArrayList에 잘라서 담아놓음으로써 ArrayList의 기능을 이용해서 다양한 작업을 간단하게 처리할 수 있다.

[예제 11-3]은 Vector의 용량(capacity)과 크기(size)에 관한 것이다. 각 실행과정을 그림과 함께 단계별로 살펴보겠다.

1. 다음 capacity가 5인 Vector인스턴스 v를 생성하고, 3개의 객체를 저장한 후의 상태를 그림으로 나타낸것이다.

2. v.trimToSize()를 호출하면 v의 빈 공간을 없애서 size와 capacity를 같게 한다. 배열은 크기를 변경할 수 없기 때문에 새로운 배열을 생성해서 그 주소값을 변수 v에 할당한다. 기존의 Vector인스턴스는 더 이상 사용할 수 없으며, 후에 가비지컬렉터에 의해서 메모리에서 제거된다.

3. v.ensureCapacity(6)는 v의 capacity가 최소한 6이 되도록 한다. 만일 v의 capacity가 6이상이라면 아무 일도 일어나지 않는다. 현재는 v의 capacity가 3이므로 크기가 6인 배열을 생성해서 v의 내용을 복사했다. 기존의 인스턴스를 다시 사용하는 것이 아니라 새로운 인스턴스를 생성하였음에 주의하자.

4. v.setSixe(7)는 v의 size가 7이 되도록 한다. 만일 v의 capacity가 충분하면 새로 인스턴스를 생성하지 않아도 되지만 지금은 capacity가 6이므로 새로운 인스턴스를 생성해야 한다. Vector는 capacity가 부족할 경우 자동적으로 기존의 크기보다 2배의 크기로 증가된다. 그래서 v의 capacity는 12가 된다.

5. v.clear();는 v의 모든 요소를 삭제한다. 아래의 왼쪽 그림의 상태에서 오른쪽 그림과 같은 상태가 되는 것이다

[예제 11-4]는 Vector클래스의 실제코드를 바탕으로 이해하기 쉽게 재구성한 것이다. (예제 11-4와 함께 Java API에서 제공하는 실제 Vector클래스 소스도 찾아보았지만 소스 코드의 길이 상의 문제로 첨부는 생략)

다음은 예제 11-1, 11-2, 11-3, 11-4 소스이다.

다음으로는 LinkedList에 대해 알아보자. 배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(접근시간)이 가장 빠르다는 장점을 가지고 있지만 크기를 변경할 수 없고, 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다는 단점을 가지고 있다. 크기를 변경할 수 없기 때문에 새로운 배열을 생성해서 데이터를 복사하는 작업이 필요하고, 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야하므로 메모리가 낭비된다. 또한 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야한다.

이러한 배열의 단점을 보완하기 위해서 링크드리스트(Linked List)라는 자료구조가 고안되었다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다. 다음 그림에서와 같이 링크드리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.

링크드리스트에서의 데이터 삭제는 간단하다. 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 단 하나의 참조만 변경하면 삭제가 이루어지는 것이다. 배ㅐ열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

링크드리스트에서의 데이터 추가는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다.

링크드리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 이 점을 보완한 것이 더블 링크드리스트이다. 더블 링크드리스트는 단순히 링크드리스트에 참조변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드리스트와 같다. 더블 링크드리스트는 링크드리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드리스트보다 더 많이 사용된다.

본론으로 들어가서 LinkedList클래스에 대해 알아보겠다. LinkedList 역시 List인터페이스를 구현했기 때문에 ArrayList와 내부구현방법만 다를 뿐 제공하는 메서드의 종류와 기능은 거의 같다. 다음 예제 11-6과 11-7을 통해 ArrayList와 LinkedList의 성능차이를 비교해 보겠다.

[예제 11-6]과 [예제 11-7]을 통해 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다는 것을 알 수 있다. 단순히 저장하는 시간만을 비교할 수 있도록 하기 위해서 ArrayList를 생성할 때는 저장할 데이터의 개수만큼 충분한 초기용량을 확보해서, 저장공간이 부족해서 새로운 ArrayList객체를 생성해야하는 상황이 일어나지 않도록 했다. ArrayList를 생성할 때 저장할 개수보다 작아서 새로운 객체를 생성하고 데이터를 복사하는 일이 발생한다면 순차적으로 데이터를 추가한다 할지라도 ArrayList보다 LinkedList가 더 빠를 수 있다. 순차적으로 삭제한다는 것은 마지막 데이터부터 삭제해나간다는 것을 의미하며, ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다는 것을 알 수 있다. 반면 중간데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다. 중간 요소를 추가 또는 삭제하는 경우, LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다. 반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야하기 때문에 처리속도가 늦다.

ArrayList와 LinkedList를 비교·요약해보자면, ArrayList는 접근시간이 빠르고, 추가/삭제는 느리다. 하지만 순차적인 추가삭제는 빠르다. 그리고 비효율적인 메모리사용이 있다. 반면, LinkedList는 접근시간이 느리고, 추가/삭제는 빠르다. 그러나 이는 데이터가 많을수록 접근성이 떨어진다. 즉, 다루고자 하는 데이터의 개수가 변하지 않는 경우라면, ArrayList가 최상의 선택이겠지만 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 될 것 이다.

다음은 예제 11-6, 11-7 소스이다.

다음으로는 Stack과 Queue에 대해 알아보겠다. Stack과 Queue에 대해 알아보기에 앞서 스택(stack)과 큐(queue)의 기본 개념과 특징에 대해 먼저 살펴보자.

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어 있고, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있다. 쉽게 말해 스택은 동전통과 같은 구조로 양 옆과 바닥이 막혀 있어서 한 방향으로만 뺄 수 있는 구조이고, 큐는 양 옆만 막혀있고 위아래로 뚫려 있어서 한 방향으로는 넣고 한 방향으로는 빼는 파이프와 같은 구조로 되어 있다. 예를 들어 스택에 a, b, c의 순서로 데이터를 넣으면 꺼낼 때는 c, b, a의 순서로 꺼내게 된다. 즉, 넣은 순서와 꺼낸 순서가 뒤집어지게 되는 것이다. 이와 반대로 큐에 a, b, c의 순서로 데이터를 넣었다면 꺼낼 때 역시 a, b, c의 순서로 꺼내게 된다. 즉, 순서의 변경 없이 먼저 넣을 것을 먼저 꺼내게 되는 것이다.

그렇다면 순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열기반의 컬렉션클래스가 적합할 것이지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

자바에서는 스택을 Stack클래스로 구현하여 제공하고 있지만 큐는 Queue인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue인터페이스를 구현한 클래스들이 있어서 이들 중 하나를 선택해 사용하면 된다.

스택과 큐의 활용 예를 알아보면, 스택은 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로 등에 사용될 수 있고, 큐는 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer) 등에 사용될 수 있다.

다음으로는 예제 11-8, 11-9, 11-10, 11-11, 11-12를 통해 스택과 큐를 좀 더 알아보았다. [예제 11-8]을 통해 스택과 큐의 FIFO구조와 LIFO구조를 확인하였다. [예제 11-9]를 통해 스택을 자바코드로 어떻게 구현하였는지 이해할 수 있었다. [예제 11-10]과 [예제 11-11]을 통해 스택과 큐의 활용을 알아보았다.

다음은 네가지 예제의 소스이다.

지금부터는 Set인터페이스 관련 컬렉션을 알아보겠다. HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다. HashSet에 새로운 요소를 추가할 때는 add메서드나 addAll메서드를 사용하는데, 만일 HashSet에 이미 저장되어 있는 요소와 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알린다. 이러한 HashSet의 특징을 이용하면, 컬렉션 내의 중복된 요소들을 쉽게 제거할 수 있다. ArrayList와 같이 List인터페이스를 구현한 컬렉션과 달리 HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.

몇 가지 예제를 통해 HashSet을 좀 더 알아보겠다. 예제 11-17, 11-18, 11-19, 11-20, 11-22, 11-23을 통해 HashSet을 살펴보았다. [예제 11-17]의 결과에서 알 수 있듯 중복된 값은 저장되지 않았다. Set을 구현한 컬렉션 클래스는 List를 구현한 컬렉션 클래스와 달리 순서를 유지하지 않기 때문에 저장한 순서와는 다르게 출력되었다. 중복을 제거하는 동시에 저장한 순서를 유지하고자 한다면 [예제 11-18]처럼 HashSet대신 LinkedHashSet을 사용해야 한다. [예제 11-19]는 중복된 값은 저장되지 않는 HashSet의 성질을 이용한 로또번호를 만드는 예제이다. [예제 11-20]은 1~50사이의 숫자 중에서 25개를 골라서 5X5크기의 빙고판을 만드는 예제이다. [예제 11-22]는 HashSet의 add메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 equals()와 hashCode()를 호출하기 때문에 equals()와 hashCode()를 목적에 맞게 오버라이딩해야 한다. 오버라이딩을 통해 작성된 hashCode메서드는 실행 중인 어플리케이션 내의 동일한 객체에 대해서 여러번 hashCode()를 호출해도 동일한 int값을 반환해야하고, equals메서드를 이용한 비교에 의해서 true를 얻은 두 인스턴스에 대해 각각 hashCode()를 호출해서 얻은 결과는 반드시 같아야 하며, equlas메서드를 호출했을 때 false를 반환하는 두 객체는 hashCode() 호출에 대해 같은 int값을 반환하는 경우가 있어도 괜찮지만, 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int값을 반환하는 것이 좋다. 마지막으로 [예제 11-23]은 두 개의 HashSet에 저장된 객체들을 비교해서 합집합, 교집합, 차집합을 구하는 방법을 보여주는 예이다.

다음은 예제 소스들이다.

다음으로는 TreeSet에 대해 알아보겠다. TreeSet은 이진검색트리라는 자료구조의 형태로 데이터를 저장하는 클래스이다. 이진검색트리는 정렬, 검색, 범위검색에 뛰어난 성능을 보이는 자료구조이며 TreeSet은 이진검색트리의 성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다. 그리고 Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

이진트리는 링크드리스트처럼 여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 '루트'라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다. 위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 하며 위의 노드를 부모노드, 아래의 노드를 자식노드라 한다. 부모-자식관계는 상대적인 것이며 하나의 부모노드는 최대 두 개의 자식노드와 연결될 수 있다. 다음 그림에서 A노드는 B노드와 C노드의 부모노드이고, B노드와 C노드는 A노드의 자식노드이다.

이진탐색트리는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진트리이다. 예를 들어 이진검색트리에 7, 4, 9, 1, 5의 순서로 값을 저장한다고 가정하면 다음과 같은 순서로 진행된다.

첫 번째로 저장되는 값은 루트가 되고, 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 작은 값은 왼쪽에 큰 값은 오른쪽에 저장한다. 이렇게 트리를 구성하면, 왼쪽 마지막 레벨이 제일 작은 값이 되고 오른쪽 마지막 레벨의 값이 제일 큰 값이 된다. 왼쪽 마지막 값에서부터 오른쪽 값까지 값을 '왼쪽노드->부모노드->오른쪽노드' 순으로 읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다. TreeSet은 이처럼 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색, 예를 들면 3과 7사이의 범위에 있는 값을 검색하는 것은 쉽고 빠르다. 저장된 값의 개수에 비례해서 검색시간이 증가하긴 하지만 값의 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교횟수가 3~4번만 증가할 정도로 검색효율이 뛰어난 자료구조이다.

트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드리스트보다 데이터의 추가삭제시간은 더 걸린다. 그 대신 배열이나 링크드리스트에 비해 검색과 정렬기능이 훨씬 뛰어나다.

예제를 통해 좀더 자세히 알아 보겠다. 예제 11-24, 11-25, 11-26, 11-27은 TreeSet 관련 예제이다. [예제 11-24]는 예제 11-19의 변형으로, TreeSet을 사용한 예이다. [예제 11-25]는 범위검색과 관련된 예제이다. [예제 11-26]은 문자열의 정렬순서에 관한 예제이다. 문자열의 경우 정렬순서는 문자의 코드값이 기준이 되므로, 오름차순 정렬의 경우 코드값의 크기가 작은 순서에서 큰 순서, 즉 공백, 숫자, 대문자, 소문자 순으로 정렬되고 내림차순의 경우 그 반대가 된다. [예제 11-27]은 TreeSet에 저장된 객체 중 지정된 기준 값보다 큰 값의 객체들과 작은 값의 객체들을 얻는 것을 보여주는 예제이다. 이를 가지고 이진검색트리를 구성해보면 다음과 같다.

다음으로는 Map인터페이스 관련 컬렉션인 Hashtable과 HashMap에 대해 알아보겠다. Hashtable과 HashMap의 관계는 Vector와 ArrayList의 관계와 같아서 Hashtable보다는 새로운 버전인 HashMap을 사용하는 것이 좋다. HashMap은 Map을 구현했으므로 앞에서 살펴본 Map의 특징, 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다. 그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다. 다음은 HashMap이 데이터를 어떻게 저장하는지 확인하기 위해 실제소스의 일부를 발췌한 것이다.

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

{

transient Entry[] table;

...

static class Entry implements Map.Entry {

final Object key;

Object value;

...

}

}

HashMap은 Entry라는 내부 클래스를 정의하고, 다시 Entry타입의 배열을 선언하고 있다. 키(key)와 값(value)은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각의 배열로 선언하기 보다는 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터의 무결성적인 측면에서 더 바람직하기 때문이다. HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉 (Object, Object)의 형태로 저장하기 때문에 어떠한 객체도 저장할 수 있지만 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다. 키는 저장된 값을 찾는데 사용되는 것이기 때문에 컬렉션 내에서 유일해야 한다. 즉, HashMap에 저장된 데이터를 하나의 키로 검색했을 때 결과가 단 하나이어야 함을 뜻한다. 만일 하나의 키에 대해 여러 검색결과 값을 얻는다면 원하는 값이 어떤 것인지 알 수 없기 때문이다.

예를 들어 사용자 ID가 키로, 비밀번호가 값으로 연결되어 저장된 데이터집합이 있다고 가정하자. 로그인 시에 비밀번호를 확인하기 위해서 입력된 사용자 ID에 대한 비밀번호를 검색했을 때, 단 하나의 결과를 얻어야만 올바른 비밀번호를 입력했는지 확인이 가능할 것이다. 만일 하나의 사용자 ID에 대해서 두 개 이상의 비밀번호를 얻는다면 어떤 비밀번호가 맞는 것인지 알 수 없다.

예제를 통해 좀 더 살펴보자. [예제 11-29]는 HashMap을 생성하고 사용자 ID와 비밀번호를 키와 값의 쌍으로 저장한 다음 입력된 사용자 ID를 키로 HashMap에서 검색해서 얻은 값(비밀번호)을 입력된 비밀번호와 비교하는 예제이다. [예제 11-30]은 기본적인 메서드를 이용해서 데이터를 저장하고 읽어오는 예제이다. [예제 11-31]은 전화번호를 키로 사용하고 하나의 키에 복수의 데이터를 저장하는 예제이다. [예제 11-32]는 문자열 배열에 담긴 문자열들의 빈도수를 구하는 예제이다.

다음은 소스이다.

다음으로는 HashMap과 HashSet 등에 사용되는 해싱(hasing)에 대해 알아보겠다. 해싱이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다. 해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable 등이 있다. 해싱에서 사용하는 자료구조는 배열과 링크드리스트의 조합으로 되어 있다. 저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 ㅗ디고, 다시 그 곳에 연결되어 있는 링크드리스트에 저장하게 된다.

예를 들어 한 간호사가 많은 환자들의 데이터 중에서 원하는 환자의 데이터를 쉽게 찾을 수 있는 방법을 고민하다가 주민등록 번호의 맨 앞자리인 생년을 기준으로 데이터를 분류해서 10개의 서랍(배열)에 나눠 담는 방법을 생각해냈다. 예를 들면 71년생, 72년생과 같은 70년대생 환자들의 데이터는 같은 서랍에 저장된다. 이렇게 분류해서 저장해두면 환자의 주민번호로 태어난 년대를 계산해서 어느 서랍에서 찾아야 할지를 쉽게 알 수 있다. 여기서의 서랍은 해싱에 사용되는 자료구조 중 배열의 각 요소를 의미하며, 배열의 각 요소에는 링크드리스트가 저장되어 있어서 실제 저장한 데이터는 링크드리스트에 담겨지게 된다.

다음으로는 TreeMap에 대해 알아보겠다. TreeMap은 이름에서 알 수 있듯이 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다. 그래서 검색과 정렬에 적합한 컬렉션 클래스이다. HashMap과 TreeMap의 검색 성능을 비교하면, 검색에 관한한 대부분의 경우에서 HashMap이 TreeMap보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다. 다만 범위검색이나 정렬이 필요한 경우에는 TreeMap을 사용한다. 예제 11-33을 통해 좀 더 알아 보았다. [예제 11-33]은 예제 11-32를 TreeMap을 이용해 변형한 것이다.

다음으로는 Properties에 대해 알아보겠다. Properties는 HashMap의 구버전인 Hashtable을 상속받아 구현한 것으로, Hashtable은 키와 값을 (Object, Object)의 형태로 저장하는데 비해 Properties는 (String, String)의 형태로 저장하는 보다 단순화된 컬렉션클래스이다. 주로 어플리케이션의 환경설정과 관련된 속성을 저장하는데 사용되며 데이터를 파일로부터 읽고 쓰는 편리한 기능을 제공한다. 그래서 간단한 입출력은 Properties를 활용하면 몇 줄의 코드로 쉽게 해결될 수 있다. [예제 11-34]는 Properties의 기본적인 메서드를 이용해서 저장하고 읽어오고 출력하는 방법을 보여주는 간단한 예제이다.

마지막으로 컬렉션 클래스의 특징과 관계를 그림으로 정리해 보았다.

출처 : http://csk2727.tistory.com/121