자바의 자료구조 - Set

원소 간 순서가 없고, 데이터 유일성을 가지는 자료구조.

( 데이터 유일성으로 인해 null 값도 하나만 가질 수 있다. )

주머니 형태의 저장공간이라고 상상하면 좋다. 

인덱스역시 존재하지 않으며, 값을 추가하거나 삭제할 때에는 추가 혹은 삭제하고자 하는 값이

Set 내부에 있는지 검색 한 뒤 추가나 삭제를 해야 하므로 속도가 List구조에 비해 느리다.

 

Set은 List와 공간을 증가시키는 방식이 다르다.

List는 한칸씩 index를 증가시키며 공간을 증가시키지만,

Set은 저장용량을 약 2배씩 증가시키게 된다. 그렇기 때문에 과부하를 일으킬 수 있어서

저장할 크기을 알고있다면 미리 크기를 지정해주는 것이 좋다. 

 

구현체로는 HashSet, TreeSet, LinkedHashSet 3가지가 있다.

 

     

 : HashSet

     해쉬 테이블에 원소를 저장하여 성능 면에서 가장 우수하다.

     가장 빠른 임의 접근 속도

     순서를 예측할 수 없음

 

    HashSet은 객체를 저장하기 전에

    객체의 hashCode()메소드를 호출해서 해시 코드를 얻어내고,

    저장되어 있는 객체들의 해시 코드와 비교한 뒤 같은 해시 코드가 있다면,

    equals() 메소드로 두 객체를 비교해서 true가 나오면

    동일한 객체로 판단하고 중복 저장을 하지 않는다.

    문자열을 HashSet에 저장할 경우,

    같은 문자열을 갖는 String객체는 동일한 객체로 간주되고 다른 문자열을 갖는 String객체는 다른 객체로 간주되는데,

    그 이유는 String클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열일 경우

    hashCode()의 리턴 값을 같게, equals()의 리턴 값은 true가 나오도록 했기 때문이다.

     ( 즉, HashSet은 삽입에는 연산이 더 소요된다. )

   

     이렇게 hashcode(), equals()를 알아볼 수 있겠다.

 

메소드

     add() : hashcode를 비교하여 기존 데이터에 값이 없어 입력이 되는 경우에는

     true를 반환하고, 입력이 되지 않는 경우에는 false를 반환한다.

    간단한 값체크의 용도로도 사용될 수 있겠다.

 

     remove() : 해당 값의 데이터를 삭제하는데 동일하게 true, false를 반환한다. 

     

     size() : hashSet의 크기를 리턴한다. 공간의 크기가 아닌 원소의 갯수를 리턴한다가 정확한 표현이다.

     

     .contains() : hashSet내부에 원하는 값이 있는지 확인하는 메소드. 값이 있다면 true, 없다면 false를 리턴한다.

 

 

 

 : TreeSet

     Set 인터페이스를 구현한 클래스로서, 객체 유일성과 저장 순서가 유지되지 않는다는 성질은 동일하다.

     HashSet과는 달리 이진 탐색 트리 ( Binary Search Tree ) 구조로 이루어져 있다.

     추가와 삭제에는 시간이 좀 더 걸리지만, 정렬과 검색에는 좀 더 높은 성능을 보이는 자료구조 이다.

     생성자의 매개변수로 Comparator 객체를 입력해 정렬 방법을 임의로 지정할 수 있다.

     

     레드-블랙 트리 ( Red-Black Tree) 로 구현되어 있다. 

     일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 소요된다. 데이터의 값이 트리에 잘 분산되어 있다면 효율성에

     큰 문제는 없으나 데이터가 들어올때 값이 편향되게 들어올 경우 한쪽으로 크게 치우쳐진 트리가 되어

     비효율적인 자료구조가 될 수 있다.

     이를 보완하기 위한 레드-블랙 트리로 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는

     오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞춘다.

 

     이진 탐색 트리와, 레드 블랙 트리는 다른 포스트로 좀 더 자세히 다뤄보겠다.

 

     TreeSet은 생성자에서 HashSet에서처럼 set을 그대로 가져올 수도 있다. 다만, 공간의 크기를 지정할 수는 없다.

     같은 Set인터페이스이기 때문에

		HashSet<Integer> set6 = new HashSet<>();
		TreeSet<Integer> tree = new TreeSet<>(set6);

 

     이런 식으로 이용 할 수도 있다. 이 또한 다형성의 장점이라 할 수 있겠다.

 

 메소드

     .add() : HashSet과 동일하다. 다만 추가되는 방식은 상이한데

     이처럼 값의 비교를 통해 넣게된다. 

     

     .remove() : HashSet과 동일하다.

     .set() : HashSet과 동일하다.

     .first(), .last() : 최소값, 최대값을 출력한다.

     .higher(), lower() : 인자보다 큰 값과 작은 값을 출력한다.

 

     속도를 떠나 메소드에서부터 저장방식에 따른 검색, 정렬의 용이함을 엿볼 수 있다. 

 

 

 : LinkedHashSet

     HashSet과 동일한 구조를 가지지만, 순서를 관리하는 자료구조이다. 
     순서를 관리하지만, 인덱스가 있는 것은 아니고 하나의 노드가 다른 노드의 주소값을 갖고 있는 형태기 때문에

     특정 순서의 값을 가져올 수는 없다. 이외의 메소드는 HashSet과 동일하다. 

    

     또한 순서대로 값을 나타내고 싶을때, 각 원소를 지칭할 수 있는 index가 없기때문에 iterator 타입으로

     변환해 순서대로 호출해야 한다.

 

 : Set 구현체들의 순서 비교 

     HashSet은 기존의 값과 hashCode를 비교해서 넣고,

     TreeSet은 기존의 값과 크기 비교를 해서 넣고

     LinkedHashSet은 기존의 값들의 순서를 따라 마지막 주소를 찾아 값을 넣기때문에

     입력에 시간소요는 HashCode < TreeSet < LinkedHashSet 순이다. 

     이러한 특성을 알고 있다면, 다른 연산에따른 시간 소요도 알 수 있을 것이다.