Set

• 데이터를 저장하는 ADT(추상자료형)
• 순서를 보장하지 않음
• 데이터 중복을 허용하지 않음
• 데이터 조회가 list보다 빠름(보통 O(1))

언제 사용하면 좋을까?

• 중복된 데이터를 제거해야 할 때
• 데이터의 존재 여부를 확인해야 할 때(데이터 조회가 list보다 빠르므로 유리함)

Set구현체

• hash set
• linked hash set (java)
• tree set (java)

Java의 hash set

• hash table을 사용해 구현(java의 hash table이 아닌 자료구조 hash table)
• 자바에서 hashSet은 내부적으로 hashMap을 사용함. 즉 자바에선 hashSet과 hashMap은 동일함
• hashMap의 key에 hashSet의 data를 넣고 value엔 더미데이터를 넣음

HashMap에 대한 포스팅

ArrayList vs HashSet

• 중복된 데이터를 제거하거나, 데이터 존재 여부를 확인하는 목적일 땐 HashSet을 사용하는게 좋음
• 이 외에는 ArrayList를 사용하는게 좋음. list가 메모리도 적게 쓰고(HashSet은 value(더미데이터), hash값을 추가로 저장), iteration에서 더 유리함(hashSet은 배열에 데이터가 띄엄띄엄 저장되있음)

Tree set (java)

저장된 데이터의 값에 따라 정렬됨.
Red-black tree로 구현되어 있으며 hash set보다 성능이 느림

Linked hash set (java)

연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 저장된 순서에 따라서 값이 정렬된다. 성능은 tree set보다 더 나쁘다.
유효한 데이터끼리 linked list로 연결되어 있음
하지만 linked list를 추가로 유지해야 하기 때문에 전반적인 성능이 조금 떨어지고, 메모리도 더 많이 사용함

출처
https://www.youtube.com/watch?v=IkImFugfFQk
자바의 신 2권