[D+65] 자바프로그래밍8 (Set<E> 인터페이스, 해쉬, TreeSet<E> 인터페이스)

 

 

국비지원 D+65

-  자바프로그래밍8 -

 

---

 

Set<E> 인터페이스

- 수학의 집합의 특징을 가지고 있다.

- 순서가 없다. (원소의 무순서)

- 중복이 없다. (원소의 유일성)

 

• 동일데이터의 판단

set인터페이스는 중복이 없는 유일성이라는 특징을 가지고 있기 때문에 equals()와 hashCode()를 오버라이딩을 통해서 통일데이터를 판단한다.

즉, 먼저 데이터에대한 hashCode를 구한다음 equals로 해쉬값을 비교해 동일데이터를 판단한다.

 

• hashCode의 등장배경

set인터페이스는 유일성을 만족해야하기 때문에 데이터가 들어갈 경우 만약 n번째의 데이터가 들어갈때 n-1번 데이터를 비교해야 한다.

적은 양의 데이터경우 큰 문제가 되지는 않지만 수많은 데이터가 들어가 있을 경우엔 오버헤드가 발생될 수 있는 것이다.

 

또한, 데이터가 짧은 경우엔 단순값을 비교해 동일데이터를 판단할 수 있지만 각각의 데이터의 크기가 클 경우에 비교루틴 자체에 대한 오버헤드가 발생될 수 있다.

 

이렇게 비교횟수와 데이터의 비교에 대한 문제점을 해결하기 위해 등장한 것이 hashCode이다.

 

먼저 비교횟수와 관련된 문제점은 분류를 통해서 비교횟수를 줄일수 있는데 hashCode의 구현부에 모듈러연산이라고 불리는 나머지연산을 통해 나누는 값만큼 분류하게 되면 탐색의 속도가 빨라지기 때문에 존재의 유무 확인이 매우 빠르다.

 

또한 데이터의 비교는 해쉬알고리즘을 통해서 각각의 다른 크기의 데이터를 고정값(해쉬값)으로 설정해준 다음 데이터를 비교해 주면 문제가 해결된다.

(자세한 정보는 아래에 설명하는 해쉬의 개념에 대해 참고할 것)

 

이를 통해 알 수 있는 것은 모듈러 연산에서 나누는 값이 클 경우 나누는 값의 개수만큼 바구니가 생기게 되는데 만약 데이터의 개수만큼 바구니를 만들게 되면 이는 각 바구니마다 유니크한 값을 가지기에 hashCode는 Hash가 아닐까 하는 생각을 가질 수 있다.

하지만 지금 우리가 구현하고 있는 hashCode는 검색속도를 줄이기위해 바구니 안에 데이터를 분류해주는 것으로 완벽한 Hash라고 보기엔 어렵다.

즉, 완벽한 Hash라고 보기는 어렵지만 나누는 값을 크게 설정해줄 경우에 Hash의 유니크한 성격을 가질 수 있기 때문에 hashCode라는 이름을 가지게 되는 것이다.

 

 

---

해쉬

임의의 길이를 가진 비트열을 입력받아서 고정된 크기의 유니크한 비트열을 만들어내는 알고리즘이다.

 

• Hash Algorithm

해쉬는 임의의 다른 두개의 데이터가 Hash Algorithm에 들어가게 될 경우, 고정된 길이의 데이터를 내보내게 되는데 이때 각각의 해쉬값은 유니크한 값을 가진다.

또한 Hash Algorithm에 들어가기 전에 두 데이터가 비슷한 값을 가지고 있었을지라도 해쉬알고리즘을 통해 나온 해쉬값은 완전 다른 비트열을 내보내게 된다.

그렇기 때문에 Hash Algorithm을 통과한 비트열은 고정된 비트열과 유니크한 값을 내보내기 때문에 데이터를 비교할때 편리하다.

 

• Hash 특징

- 역상저항성 : 해시값이 주어졌을 때, 그 해시 값을 생성하는 입력값을 알아내기가 불가능하다.

- 제2 역상 저항성 : 어떤 입력값과 동일한 해시값을 가지는 다른 입력값을 찾을 수 없다. (해시 값을 알고 있을 때 원래 값을 찾아내는 것이 문제이다)

- 충돌 저항성 : 해시값이 같은 입력 값 두 개를 찾을 수 없다. (해시 값이 무엇이든 그 값을 알던 모르던 특정하게 같은 해시 값을 생성하는 값 두 개를 찾는 과정이 문제이다)

 

 

---

TreeSet<E> 인터페이스

- Set의 기본적인 성격을 가지고 있다.

- 트리구조를 사용하여 정렬상태를 유지하면서 저장하는 인터페이스 이다. (단순히 들어간것으로 정렬에 대한 기준이 없는 상태)

- 정렬상태를 만들기 위해 저장되는 클래스는 comparable<T> 인터페이스를 implement해야한다.

- 별도의 정렬기준을 제시하기 위해서는 comparator<T> 인터페이스를 사용한다.

 

• 장단점

- 장점 : 검색이 빠르다.

- 단점 : 정렬기준에 맞게 구조를 변경하기 때문에 입력이 느리다.

 

• 정렬기준을 바꾸고 싶은 경우

TreeSet에 대한 정렬기준을 만들고 싶은 경우 Comparator를 구현하는 별도의 Class를 생성해야하며, TreeSet을 생성할 경우 TreeSet의 생성자 안에 정렬기준에 대한 객체를 생성해 넣어주면 된다.