[자료구조] Set과 HashSet: 개념, List vs Set (메모리와 iteration 속도 관점에서)

반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

💋 Set ADT

✔️ 개념

• 데이터를 저장하는 추상 자료형
• 순서 보장 X
• 데이터 중복 X

 

✔️ 주요 동작

1. 삽입(Insertion)
• 새로운 원소를 집합에 추가하는 동작
• 집합에 이미 존재하는 원소는 중복으로 삽입되지 않는다.
2. 삭제(Removal)
• 주어진 원소를 집합에서 제거하는 동작
3. 포함 여부(Containment)
• 주어진 원소가 집합에 속하는지 여부를 확인하는 동작
4. 교집합(Intersection)
• 두 집합 간의 공통된 원소들을 모은 새로운 집합을 생성하는 동작
5. 합집합(Union)
• 두 집합의 모든 원소를 포함한 새로운 집합을 생성하는 동작
6. 차집합(Difference)
• 한 집합에서 다른 집합의 원소를 제거한 새로운 집합을 생성하는 동작
7. 부분 집합 여부(Subsetting)
• 한 집합이 다른 집합의 모든 원소를 포함하는지 여부를 확인하는 동작

 

✔️ 언제 사용할까?

• 중복된 데이터를 제거해야 할 때
• 데이터의 존재 여부를 확인해야 할 때

 

✔️ 구현

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

 

이중 오늘 살펴볼 것은 hash set이다!

 

💋 Hash Set

✔️ 개념

 

• 해시 테이블을 사용해 구현 ⇒ 크기 상관없이 데이터 조회가 빠르다! 
• 탐색에 특화된 자료구조로 평균 O(1)의 시간복잡도로 데이터를 탐색, 삽입, 삭제가 가능해, List보다 빠르다.
  • 단순하게 해시 함수에 키 값을 넣어 나온 해시 값으로 인덱스를 알고 접근할 수 있기 때문
  • 해시 충돌이 발생하여 하나의 인덱스에 데이터가 몰려있을 경우 시간복잡도는 O(N)으로 증가할 수 있다.

public HashSet() {
	this.map = new HashMap();
}

 

 

✔️ 특징

• 데이터 삽입 시 해시값을 키로 사용해서 저장한다.

public boolean add(E e) {
	return this.map.put(e, PRESENT) == null;
}

 

• 데이터 존재 여부 확인 시 해시값을 키로 사용해서 데이터에 접근한다.

public boolean contains(Object o) {
	return this.map.containsKey(o);
}

 

 

✔️ Python Set vs Java HashSet

 

 

 

💋 List vs Set

✔️ 메모리 측면

• Set은 해시값을 저장해야 하기 때문에, 메모리를 많이 차지한다.
• List는 해시값이나 포인터 없이 값만 순차적으로 저장해, 메모리를 적게 쓴다.

 

✔️ iteration 속도

• List가 구현 특성 상 단순해서 더 빠르다.
• HashSet은 내부 배열에 빈 공간이 존재해 데이터 iteration 시에 오버헤드가 발생한다.
• Java의 LinkedHashSet는 이 점을 보완하기 위해서, 존재하는 데이터끼리 LinkedList로 이어 놓았지만, 여전히 포인터가 필요하게 되어 여전히 메모리를 더 사용해야 한다는 단점이 있다.
• Java의 TreeSet의 경우에도 데이터를 순차적으로 순회하는데 비용이 발생한다.
• iteration 속도가 비슷하다고 할지라도, 메모리 측면에서 리스트가 더 좋다!

 

 

✔️ 결론

• Set이 적절한 상황이 아니라면, 대부분 List를 사용하는 것이 좋다.

 

💋 참고자료

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

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!