Hashset에 대해

참고 : https://www.youtube.com/watch?v=NEkxSTicSx8(남궁성 유튜브)

HashSet과 TreeSet

- TreeSet과 HashSet은 내부적으로 TreeMap을 이용하여 구현되어 있다.

- 순서가 없으며 중복이 없다.

- Set의 종류에는 루트에 Set이 있으며 두 갈래로 나뉘여 HashSet과 SortedSet이 있고, 각각 자식으로 LinkedHashSet과 TreeSet이 있다.

HashSet

- Set인터페이스를 구현한 대표적인 컬렉션 클래스

- Hashing기법을 사용한다.

- 순서를 유지하려면 LinkedHashSet클래스를 사용하면 된다.

TreeSet

- 범위 검색과 정렬에 유리한 컬렉션 클래스

- HashSet보다 데이터 추가와 삭제에 시간이 더 걸린다.

HashSet

- boolean add(Object o)

- 저장할 객체의 equals()와 hashCode()를 호출하기 때문에 두 메소드가 오버라이딩되어 있어야 한다.

*(Objectsvalues).hashCode()를 JDK1.8버전 이후부터는 Objects.hash(Objectsvalue)로 나타낼 수 있게 되었다.

- HashSet은 객체를저장하기 전에 기존에 같은 객체가 있는지 확인하고 없으면 저장(true)하며 있으면 저장하지 않는다.(false)

ex)

Object[] objArr = {"1", new Integer(1), "2", "2", "4", "3", "3", "4", "3"};

//ctrl+swift+o를 하면 오토 임포트를 할 수 있다.

Set set = new HashSet();

for (int i = 0; i < objArr.length; i++)

set.add(objArr[i]);

System.out.println(set);

=> [1, 1, 2, 3, 4] //여기서 1이 두개로 보이지만 객체형과 String형의 다른 타입이라 중복이 아니다.

-hashCode()의 오버라이딩 조건(JDK1.8부터는 Objects.hash()도 같은 효과를 줄 수 있다.)

- 동일 객체에 대해 hachCode()를 여러 번 호출해도 같은 값을 반환해야 한다.

- equals()로 비교해 true를 얻은 두 객체의 hashCode()값은 반드시 일치해야 한다.

- equals()로 비교한 결과가 false인 두 객체의 hashCode()값이 같을 수 있다. 하지만 성능 향상을 위해서 간으하면 서로 다른 값을 반환하도록 작헝하는 것이 좋다.

TreeSet

- 범위 검색과 정렬에 유리한 이진 탐색 트리(Binary Search Tree)로 구현되어 있다.

- 링크드 리스트처럼 각 요소(node)가 나무 형태로 연결된 구조이다.

- 이진 트리는 모든 노드가 최대 두 개의 하위 노드를 갖는다(부모-자식관계)

- 이진 검색 트리는 부모보다 작은 값을 왼쪽에, 큰 값은 오른쪽에 저장한다.

- 루트부터 시작하여 각 노드를 비교해가며 저장할 장소를 찾기 때문에 HashSet보다 데이터를 추가, 삭제하는 데 시간이 더 걸린다.(반복적인 비교 후 저장) 

TreeSet 데이터 저장과정

- boolean add(Object o)

- 만약 TreeSet에 7, 4, 9, 1, 5순서로 저장한다면 아래의 과정을 거치게 된다(루트부터 트리를 따라 내려가며 값을 비교하고, 작으면 왼쪽, 크면 오른쪽에 저장되게 된다.

TreeSet에서 자주 쓰이는 주요 생성자와 메소드

- TreeSet() : 기본 생성자

- TreeSet(Collection c) : 주어진 컬렉션을 저장하는 TreeSet을 생성

- TreeSet(Comparator comp) : 주어진 정렬기준으로 정렬하는 TreeSet을 생성

- Object first() : 정렬된 순서에서 첫 번째 객체를 반환한다

- Object last() : 정렬된 순서에서 마지막 객체를 반환한다.

- Object ceiling(Object o) : 지정된 객체와 같은 객체를 반환, 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null을 반환한다.

- Object floor(Object o) : 지정된 객체와 같은 객체를 반환, 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null.

- Object heigher(Object o) : 지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null.

- Object lower(Object o) : 지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null.

- SortedSet subSet(Object fromElement, Object toElement) : 범위 검색(fromElement와 toElement사이)의 결과를 반환한다.(끝 범위인 toElement는 범위에 포함되지 않는다.)

- SortedSet headSet(Object toElement) : 지정된 객체보다 작은 값의 객체들을 반환한다.

- SortedSet tailSet(Object fromElement) : 지정된 객체보다 큰 값의 객체들을 반환한다.

전위, 중위, 후위 순회

- 이진 트리의 모든 노드를 한 번씩 읽는 것을 트리 순회라고 한다.

- 전위, 중위, 후위 순회법이 있으며, 중위 순회하게 될 경우 오름차순으로 정렬되게 된다.

- 부모 노드가 위치하는 곳을 기준으로 생각하면 세 가지 순회법에 대해 쉽게 이해 가능하다.

ex) 10, 35, 45가 있을 때(35가 부모 노드)

전위 -> 35, 10, 45(부모 노드가 왼쪽 노드보다 앞에간다고 생각하자)

중위 -> 10, 35, 45(부모 노드가 자식 노드들 사이에 간다)

후위 -> 10, 45, 35(부모 노드가 오른쪽 노드보다 뒤에 간다)