C++에서 배우는 자바-컬렉션 클래스
자바의 자료구조
자바에서는 자료구조들이 C++에 비해 체계화 되어있고 정리가 잘 되어있는 것 같다.
각 자료구조들이 서로 관계가 없었고 파편화되어있던 C++과 달리 자바는 map을 제외한 모든 자료구조들을 Collection 클래스의 자손으로 두어 공통적인 메서드를 가짐으로써 서로 다른 자료구조들이 같은 사용 방식을 갖도록 하였다.
가장 놀랐던건 자료구조에 모든 형이 들어갈 수 있다는 것이었다. C++에서는 템플릿 등을 이용하여 타입을 먼저 캐스팅하고 자료구조를 만들었지만, 자바에서는 따로 캐스팅하지 않고 자료구조에 여러 형이 한번에 들어갈 수 있었다.
캐스팅 하는 기능은 제네릭스(Generics)라고 따로 있었는데 이는 나중에 포스팅하도록 하겠다.
자료구조들에 대해 대충은 알고있는 만큼 겹치는 부분은 패스하고 자바에만 있는 부분, 내가 몰랐던 부분을 중심으로 정리해보도록 하겠다.
컬렉션 클래스
자바의 자료구조는 전체적으로 Collection 인터페이스의 자손인 List와 Set 그리고 형태가 다르기에 Collection에 들어가지 않은 Map 인터페이스가 있다. 각각의 특징은 다음과 같다.
- List : 순서가 있는 자료구조. 데이터의 중복을 허용한다.(Arraylist, stack 등)
- Set : 순서를 유지하지 않는 자료구조. 데이터의 중복을 허용하지 않는다.(Hashset, Treeset 등)
- Map : key와 value의 쌍으로 이루어진 자료구조. 순서는 유지되지 않고, 키의 중복은 허용하지 않고 값의 중복은 허용한다.(Hashmap,Treemap 등)
Collection 인터페이스를 구현함으로써 기본적인 부분은 공유하면서 각 자료구조마다 따로 필요한 부분은 따로 가질수 있도록 하는 구조이다. 또한 대부분의 생성자가 Collection을 매개변수로 받음으로써 자료구조끼리의 변환도 매우 용이한 장점이 있다.
컬렉션 인터페이스는 기본적으로 저장된 데이터를 읽고, 쓰고, 제거하는 기본적인 메서드를 정의하고 있다. 기본적인 메서드들은 다음과 같다.
- boolean add(Object o) : 객체를 자료구조에 추가한다.
- void clear() : 자료구조를 비운다.
- boolean contains : 지정된 객체가 자료구조에 포함되어 있는지 확인한다.
- boolean remove(Object o) : 지정된 객체를 삭제한다.
- int size() : 저장된 객체의 개수를 반환한다.
List 인터페이스에 정의된 기본적인 메서드들은 다음과 같다.
- void add(int index, Object o) : 지정된 위치에 객체를 추가한다.
- Object get(int index) : 지정된 위치의 객체를 반환한다.
- int indexof(Object o) : 지정된 객체의 위치를 반환한다.(정방향 순회)
- void sort(Comparator c) : 비교자로 리스트를 정렬한다.
Map 인터페이스의 기본적인 메서드느 다음과 같다.
- boolean containsKey(Object o) : 지정된 객체와 일치하는 key 객체가 있는지 확인한다.
- boolean containsValue(Object value) : 지정된 객체와 일치하는 value 객체가 있는지 확인한다.
- Object get(Object key) : 지정한 key객체에 대응하는 value 객체를 반환한다.
- Object put(Object key, Object value) : key와 value 객체를 연결하여 Map에 저장한다.
- Object remove(Object key) : 지정된 key 객체와 일치하는 key-value 쌍을 삭제한다.
Map은 key-value 쌍을 다루기 위해 내부에 Entry 인터페이스를 추가로 가지고있다. 즉 Map은 여러 개의 Entry로 이루어진 자료 구조이다. Entry의 내부 메서드는 다음과 같다.
- boolean equals(Object o) : 동일한 Entry인지 비교한다.
- Object getKey() : Entry의 key객체를 반환한다.
- Object getValue() : Entry의 value 객체를 반환한다.
ArrayList
ArrayList는 vector를 개선한 자료구조이다. 아마 가장 자주 쓰게 될 자료구조이고 실제로 C++에서 가장 많이 사용했던 vector와 거의 동일한 자료구조이다.
데이터를 순차적으로 저장하고 size가 capacity보다 늘어나면 다른 배열을 생성하여 복사한다.
간단한 사용례는 다음과 같다.
import java.util.*;
class Array {
public static void main(String args[]) {
ArrayList list=new ArrayList(10);
list.add(new Integer(5));
list.add(new Integer(4));
list.add(new Integer(2));
Collections.sort(list);
list.remove(2);
System.out.println(list);
}
}정렬 후 끝의 객체를 삭제하였으므로 2,4가 출력된다.
LinkedList
C++의 list에 대응하는 링크드 리스트이다. C++에서는 벡터만 사용하고 list는 거의 사용해보질 않아 면접에서 제대로 대답을 하지 못했던 경험이 있다. 이참에 제대로 알아보도록 하자.
LinkedList의 하위 메서드는 ArrayList와 거의 동일하므로 생략하였다. LinkedList는 더블 링크드 리스트로 이루어져 있다.
ArrayList는 리스트 중간의 객체를 삭제 및 추가할 경우 뒤의 객체들을 전부 한 칸씩 땡기거나 밀어야 하므로 시간이 오래 걸린다. 이러한 단점을 해결하기 위한 링크드 리스트 자료구조로 index를 통한 랜덤 접근이 불가능한 대신 중간의 자료를 추가 혹은 삭제하더라도 앞뒤 노드가 가리키는 주소만 바꿔주면 되므로 성능이 좋다.
하지만 만약 끝에서부터 추가, 혹은 삭제한다면 ArrayList가 더 성능이 좋다.
stack, queue
stack과 queue 부분은 top()이 아닌 peek()인 점 등 세세한 차이가 있긴 하지만 거의 동일하므로 넘어가겠다. 다행히 priority_queue, deque 등의 자료구조도 모두 존재하였다.
iterator
순회자이다. 역할은 알고 있으니 넘어가도록 하고 C++에서는 iterator를 +1씩 연산해주며 사용했다. 예를 들면 이렇게
for(auto iter=v.begin(); iter!=v.end(); iter++) {}사용하였는데, java에서는 좀 다르다. java에서는 iterator의 하위 메서드들을 사용하여 연산한다. 하위 메서드들은 다음과 같다.
- boolean hasNext() : 읽어올 다음 요소가 남아있는지 확인한다.
- Object next() : 다음 요소를 읽어온다.
- void remove() : next()로 읽어온 요소를 삭제한다. next() 후에 호출해야 한다.
iterator에 대한 직접적 연산 대신 하위 메서드를 사용하여 상대적으로 더 간단해졌다. 여기에 previous()를 추가하여 이전으로도 돌아갈 수 있는 Listiterator도 있다. 이 Listiterator는 List 인터페이스를 구현한 자료구조에서만 사용 가능하다. java에서 iterator의 사용례는 다음과 같다.
class Array {
public static void main(String args[]) {
Collection list=new ArrayList(10);
Iterator it=list.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
}
}순회자라는 역할에 더 충실하면서 간단해진 모습이다.
Comparator & Comparable
sort 등을 사용하는 정렬은 기본적으로 오름차순으로 정렬된다. 따로 자신이 원하는 방식대로 정렬하고 싶다면 C++에서는 bool을 반환하는 함수를 따로 작성하여 sort 함수에 매개변수로 넣어주었다.
java에서는 조금 다른데 Comparator 인터페이스가 따로 지정되어 있어 이 Comparator 인터페이스를 구현한 클래스만이 구분자로 쓰일 수가 있다.
비교가 가능한 모든 객체들은 Comparable 인터페이스를 구현하여 sort등의 정렬 함수는 기본적으로 이것을 통해 정렬을 진행한다. Comparator 인터페이스 내부에는 int compare(Object o1, Object o2)라는 추상메서드가 선언되어 있어 이를 원하는 방식대로 오버라이딩하여 사용한다. 사용례는 다음과 같다.
class Array {
public static void main(String args[]) {
String strarr[]={"cat", "dog", "lion", "tiger"};
Arrays.sort(strarr, new descending());
System.out.println(Arrays.toString(strarr));
}
}
class descending implements Comparator {
public int compare(Object o1, Object o2) {
if(o1 instanceof Comparable && o2 instanceof Comparable) {
Comparable c1=(Comparable) o1;
Comparable c2=(Comparable) o2;
return c1.compareTo(c2)*-1;
}
return -1;
}
}sort 메서드를 이용하여 배열을 내림차순으로 정렬하는 코드이다. Comparator 인터페이스를 구현하는 descending 클래스에서 compare 메서드를 오버라이딩 하였다. 두 객체가 비교 가능한지, 즉 Comparable 인터페이스를 구현했는지 확인한 후 원래의 값에 -1을 곱해 내림차순을 구현했다.
HashSet
C++의 set과 달리 정렬이 되지 않지만 unordered_set과 대부분 동일하므로 개요는 넘어가고, HashSet의 작동구조에 대해 잠깐 살펴보자.
import java.util.*;
class hashsetex {
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);
}
}
class Person {
String name;
int age;
Person(String name, int age) {
this.name=name;
this.age=age;
}
public String toString() {
return name+":"+age;
}
}분명 HashSet은 중복을 허용하지 않는다. 하지만 위의 코드를 실행하면 abc, David:10, David:10이 출력된다. 왜일까?
먼저 HashSet의 작동구조에 대해 알아보자. HashSet은 중복을 다음과 같은 과정으로 판별한다.
- 두 객체에 대하여 equals() 메서드를 사용하여 true인지 확인한다.
- 두 객체에 대하여 hashCode() 메서드를 사용하여 도출된 해시코드가 같은지 확인한다.
따라서 위의 코드에서 이름과 나이가 같다면 중복으로 판별되길 바란다면 equals와 hashCode 메서드를 오버라이딩할 필요가 있다.
import java.util.*;
class hashsetex {
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);
}
}
class Person {
String name;
int age;
Person(String name, int age) {
this.name=name;
this.age=age;
}
public String toString() {
return name+":"+age;
}
public boolean equals(Object obj) {
if(obj instanceof Person) {
Person tmp=(Person)obj;
return name.equals(tmp.name) && age==tmp.age;
}
return false;
}
public int hashCode() {
return (name+age).hashCode();
}
}위와 같이 수정한다면 코드는 원하는대로 작동한다.
이외에 set의 값이 정렬되기를 바란다면 C++의 set에 대응하는 TreeSet을 사용하면 된다.
TreeSet은 이진검색트리를 사용함으로써 정렬과 검색이 용이하다.
C++의 set과 map은 이진 검색트리를 사용함으로써 범위 검색이 용이함이 핵심이었는데 나는 그냥 해시 테이블과 같이 사용하고 있었다. 이번에 java를 공부하면서 알게 되었는데 이럴때마다 자료구조의 공부가 부족함을 실감한다.
HashMap과 TreeMap은 key와 value로 이루어져 있는 것을 제외하곤 위의 내용과 대부분 같으니 생략하겠다.
C++에서 사용할 때에는 map과 unordered_map을 구분 없이 무분별하게 사용했지만 이진 검색트리를 사용하는 TreeMap보다 해시 테이블을 사용하는 HashMap이 검색 성능이 더 좋고 범위 검색엔 TreeMap이 더 좋음을 꼭 유의하고 사용하도록 하자.
Collections
Arrays가 배열과 관련한 메서드들을 제공하는 것처럼, Collections도 컬렉션들과 관련된 다양한 메서드들을 제공한다.
- 컬렉션의 동기화 구버전의 Vector,Hashtable 등의 자료구조는 기본적으로 멀티쓰레딩의 동기화를 제공했다. 하지만 이 동기화가 멀티쓰레딩 환경이 아닐 때는 성능을 저하시키는 문제가 있었다.
따라서 지금과 같이 동기화가 제공되지 않는 ArrayList, HashMap 등의 컬렉션을 사용하는 대신, Collections가 제공하는 동기화 메서드를 사용하여 멀티쓰레딩 환경의 동기화를 진행한다. Collections 클래스는 다음과 같은 여러 동기화 메서드를 제공한다.
static Collection synchronizedCollection(Collection c)
static List syncronizedList(List list)
static Set syncronizedSet(Set s)
....사용례는 다음과 같다.
List synclist=Collections.syncronizedList(new ArrayList(...));- 변경 불가 컬렉션
컬렉션 내부의 데이터를 보호하기 위해 컬렉션을 읽기 전용으로 만들 수도 있다. 주로 멀티쓰레딩 환경에서 상호배제가 이루어지지 않아 데이터가 손상되는 것을 막기 위해 사용한다.
static Collection unmodifiableCollection(Collection c)
static List unmodifiableList(List list)
static Set unmodifiableSet(Set s)
....- 싱글톤 컬렉션 디자인 패턴 중 싱글톤은 단 하나만의 객체가 존재함을 뜻한다. Collections는 이와 같이 단 하나의 객체만을 저장하는 컬렉션을 제공한다.
static List singletonList(List list)
static Set singletonSet(Set s)
....이외에도 한 종류의 객체만을 저장할 수 있는 컬렉션을 만드는 등의 기능이 있는데 이는 보통 후에 배울 제네릭스(Generics)를 사용하여 구현하니 생략하도록 하겠다.
지금까지 java의 여러 컬렉션, 즉 자료구조들을 살펴보았다.
면접까지 가지를 못해 딱 한번밖에 보지 못한 면접이었고 몇 번 보지못했던 코테지만 자료구조들의 특성을 확실하게 알지 못해 제대로 대답하지 못한 것이 많이 아쉬웠던 만큼 이번에 정리하며 개념을 확실히 하면 좋을 것 같다.