Java 데이터 구조(2) Set 세트.

세트(Set) 은 List 의 자식크라스(subclass) 로 역시 linerdata stucture 이며,  Array(배열) 형태 랑 Linked(Node) 형태  가 존재 합니다.

Set 특징

1. 중복을 허용하지 않는데

2. 데이터를 비순차적(unordered)으로 저장할 수있음 (대표적으로 HashSet )(order가 필요한 경우에는 LinkedHashSet 혹은 SortedSet 사용).

 

List 하고 다른점.

1. 중복이 없을때만 데이타 추가. add() : boolean

Array 방식일 경우

for 루프로 중복이 있나 확인후 넣기.

public boolean add(E o)
{
    if(contains(o)){
        return false;
    }
    if(size >= elements.length){
        expandcapacity();
    }
    elements[size] = o;
    size++;
    return true;
}

 

Node 방식일 경우

역시 중복 확인후 집어넣기

    public boolean add(E o)
    { if (!(contains(o)))
    { Node<E> newNode = new Node<E>(o);
// add the new node to the front of the list
        newNode.next = firstNode;
        firstNode = newNode;
        numElements++;
        return true;
    }
    else
        return false;
    }

 

Set 세트 종류

1.HashSet

1.HashSet은 Hash 테이플의 사용으로 ,데이터 의 존재 여부를 효율적으로 확인할 수 있다. 이는 데이터 검색이나 필터링 작업에 유용하게 사용될 수 있다

2.순서가 중요하지 않은 경우에 사용되며, 이로 인해 데이터를 빠르게 처리할 수 있습니다.

3.기본 작업인 요소의 추가, 삭제 및 포함 여부 확인이 평균적으로 상수 시간(O(1))에 이루어짐. 이는 해시 테이블을 기반으로 구현되어 빠른 성능을 제공합니다

2.linkedHashSet

1. 데이터가 삽입된 순서를 유지합니다. 이를 위해 이중 연결 리스트(doubleLinked, node 앞뒤로 연결)를 사용합니다.

2. 예측 가능한 반복 순서를 제공합니다.

3.해시 테이블과 연결 리스트를 혼합하여 사용합니다. 해시 테이블은 빠른 검색을 제공하고, 연결 리스트는 요소의 순서를 유지합니다.

3.treeSet

1. 자기 균형 이진 검색 트리(레드-블랙 트리)를 사용하여 집합을 구현. 

2. 데이터가 정렬된 순서로 필요한 경우, TreeSet은 정렬에 대한 추가적인 작업 없이도 정렬된 순서로 데이터를 관리.

3. 추가, 제거 및 포함 작업에 대한 시간 복잡도는 log(n).

4.Comparable 또는 Comparator를 구현한 객체를 저장할 수 있습니다. 이를 통해 정렬 순서를 사용자가 제어할 수 있습니다