[자료구조] Set과 자바에서의 HashSet

Set이란?

데이터를 저장하는 추상자료형이다.

순서를 보장하지 않고, 데이터의 중복을 허용하지 않는다.

데이터 조회속도가 List보다 빠르다.

 

 

자바에서의 Set

자바에는 Hash Set, Linked Hash Set, Tree Set이 있다. 

자주 쓰이는 Hash Set에 대해 중점적으로 살펴보자

 

Hash Set

 

Hash Table을 사용하기 때문에, 크기 상관없이 데이터 조회가 빠르다.

Hash Set은 어떻게 구현되어있나 살펴본다면, Hash Map을 사용하는것을 알 수 있다.

따라서 자바에서는 HashMap과 HashSet은 동일하다고 볼 수 있다.

 

Hash Set의 삽입

Hash Set에서 데이터를 삽입(add)할때를 보자, 

다음과 같이 Key값으로 e를 넣고, Value를 통해 PRESENT라는 객체를 넣어 데이터를 추가하는 것을 알 수 있다.

 

참고로 PRESENT는 더미 데이터이다. 그냥 객체 한개일 뿐이다.

 

 

Hash Set의 조회

map에 key가 있는지를 조회하는 것과 똑같은 작업이다.

Hash Set의 기본 용량, resize  기준, resize 규모.

기본 hashMap과 같다. 자세한 건 이전 글을 참고하면 내부구조가 나와있다.

기본용량:16

resize 기준 : 75%이상 데이터 존재시

resize 규모 : 2배

 

List와 Set 무엇을 써야할까?

중복제거 및 조회를 해야하는, Set을 쓰는게 이점이 있는 상황이 아니면

List를 사용하는것이 좋다.

데이터가 중복이 없고, 순서가 상관없고, Iteration을 돌아야 하는 상황이여도

List가 해쉬나 트리를 저장하지 않기에 메모리도 더 적게 쓰고, 

List가 단순하여 Iteration 속도가 더 빠르다.

 

HashSet 활용 시 헤시테이블을 전체 확인하면 비어있는 공간이 많기떄문에 비용이 많이든다!

 

이걸 보완하고자 Linked Hash Set을 사용한다면, Iteration 속도는 비교적 빠르지만 연결리스트가 구현되어있기때문에

메모리도 많이 먹게 된다.

 

TreeSet은 이름처럼 Tree를 활용하므로 순회비용이 발생한다.

 

 

 

 

 

 

 

 

참고자료

https://www.youtube.com/watch?v=IkImFugfFQk&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=7