(CH11) 1.7 Comparator와 Comparable ~ 1.14 컬렉션 클래스 정리 & 요약
Compartor와 Comparable
Arrays.sort()와 같은 정렬 메소드는 컴퓨터가 배열을 정하는 것처럼 보였지만, 실제로는 Comparator와 Comparable 인터페이스 구현에 의해 정의되고 있었던 것이다. 같은 타입의 인스턴스끼리 비교할 수 있는 것들(Wrapper, String, Date, File 등등)이 오름차순으로 정렬되도록 구현되어 있다.
HashSet
HashSet은 Set인터페이스를 구현한 것으로, Set의 대표적인 특성을 따라 중복된 요소를 저장하지 않는다. 만일 중복된 요소를 저장하려고 시도한다면 false가 반환되어 저장에 실패하게 된다. 또한 저장 순서를 고려하지 않기 때문에 저장순서를 고려할 때는 LinkedHashSet을 사용해야 한다.
HashSet에 새로운 요소를 추가가할 때 클래스를 구현하여 인스턴스로 요소를 추가하게 되면 사용자가 보기엔 같은 값임에도 컴퓨터는 다른 값으로 인식하여 두 인스턴스 모두 저장하게 된다.
HashSet set = new HashSet();
// 사용자가 보기엔 두 인스턴스가 같지만 컴퓨터는 다르다고 인식
set.add(new Person("Daniel",10));
set.add(new Person("Daniel",10));
...
class Person
...
이러한 경우에 새로 추가되는 요소가 기존 요소와 같은지 확인하기 위해 equals()와 hashCode()메소드를 사용하기 때문에 적절히 오버라이딩 하여야 한다.
hashCode()를 오버라이딩 할 때는 몇가지 조건을 만족해야 한다.
- 실행 중인 어플리케이션 내의 동일한 객체에 여러번 hashCode()를 호출해도 동일한 int값을 반환해야 한다. 실행시마다 동일한 int값일 필요는 없다.
- equals메소드로 비교한 결과로 true가 나온 두 객체에 대해 각각 hashCode()를 호출해서 얻은 결과는 반드시 같아야 한다.
- equals메소드를 호출했을 때 false를 반화하는 두 객체는 hashCode() 호출에 대해 같은 int값을 반환해도 괜찮지만, hashing을 사용하는 컬렉션의 성능 향상을 위해 다른 값을 반환하는 것이 좋다.
TreeSet
TreeSet은 이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 정렬, 검색, 범위검색에 높은 성능을 보인다.
Binary Tree는 LinkedList처럼 여러 개의 노드가 연결된 구조이며, 각 노드에 최대 2개의 노드를 연결할 수 있다. 각 노드간의 관계는 부모-자식의 관계로 이해할 수 있고, 상위에 있는 노드를 부모, 하위에 있는 노드를 자식이라고 부른다. 자식 노드를 가질 때 부모노드의 왼쪽에는 부모노드보다 작은 값이, 오른쪽에는 부모노드보다 큰 값을 저장한다. 따라서 왼쪽 노드에서 오른쪽 노드까지 순차적으로 값을 읽으면 정렬된 순서를 얻을 수 있다.
HashMap과 Hashtable
HashMap과 Hashtable은 Vector와 ArrayList의 관계와 같아 HashMap을 사용하는 것이 권장된다. HashMap은 Map을 구현한 것이므로 key, value값을 묶어 하나의 데이터로 저장한다는 특징을 갖는다. 또한 hashing을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어 뛰어난 성능을 자랑한다.
HashMap에 데이터를 저장할 때 기존 데이터와 중복된 데이터를 저장하는 경우가 있다. 이 경우 어떤 값을 저장할 것인지 결정해야하는데, default로는 나중에 입력한 데이터를 저장하도록 되어있다.
해싱과 해시함수
해싱이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 의미한다. 해시함수가 저장된 데이터의 위치를 알려주기 때문에 다량의 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있다.
TreeMap
TreeMap은 이진검색트리 형태로 key, value가 쌍으로 이루어진 데이터를 저장한다. 그렇기에 검색과 정렬에 적합한 컬렉션 클래스이다. 검색 성능을 HashMap과 비교하면 HashMap이 더 좋은 성능을 보이지만, 범위검색이나 정렬이 필요한 경우에는 TreeMap을 사용하는 것이 바람직하다.
Reference
