Set & HashSet

Set

1. Set은 중복값을 허용하지 않는 ADT
2. 일반적으로 Set은 순서를 보장하지 않는다.
3. 자료구조의 관점에서 데이터 조회(존재여부)를 확인하는데 List보다 빠르다.
4. add(), remove(), contains()

Set의 사용

1. 중복된 데이터를 제거하여 저장해야 할때
2. 데이터의 존재여부를 확인할때

Set은 중복된 데이터가 저장하기 위해 들어오면 저장하지않는다.

Set의 구현체

HashSet

HashSet : 순서를 보장하지 않는 자료구조

구현방식(Java)

HashSet의 구현은 HashMap을 활용하여 구현한다.
hash table에서 key에 데이터를 저장하고, value에는 더미데이터를 저장하여 구현한다.
즉, 일반적으로 테이블의 크기에 상관없이 key를 통해 상수시간으로 데이터에 접근한다.

public HashSet(){
	map = new HashMap<>();
}
// HashSet의 생성자에 map의 구현체로 HashMap을 사용한다.
// map.put(데이터,더미데이터) : Map형식으로 key에 데이터가 들어가고 
// value자리에 더미데이터가 들어간다.

unique.add("구독"); // hashfunction을 통해 hashtable에 저장된다.
unique.add("좋아요"); // hashfunction을 통해 hashtable에 저장된다.
unique.add("구독"); // hashfunction의 결과값과 key의 데이터가 같기때문에 저장되지 않는다.

System.out.println(unique.size()); //2
System.out.println(unique.contains("구독")); //true O(1)
System.out.println(unique.contains("알림설정")); //false O(1)

LinkedHashSet

LinkedHashSet : 순서를 보장하는 자료구조

List와 Set의 고민

데이터들 자체가 이미 중복이 제거되어있고, 순서 상관없이 모든 데이터를 조회하려고 할때 어떤 ADT가 더 효율적 일까?

List는 공간복잡도가 낮고, 구현 특성상 단순하여 단순 저장 및 조회가 빠르다.
(ex. ArrayList의 경우 index[0]부터 index[size]까지 순차적으로 가져오면된다.)
하지만, HashSet의 경우 hashfunction을 통한 결과값이 순차적이지 않아 공간복잡도가 높고, 메모리 공간이 순차적이지 않아 반복을통한 조회에서는 보다 느리다.

출처 : 쉬운코드 유튜브