반응형
반응형
Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS
GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip
주니어 개발자를 위한 전공 지식 모음.zip. Contribute to seoul-developer/CS development by creating an account on GitHub.
github.com
💋 Set ADT
✔️ 개념
- 데이터를 저장하는 추상 자료형
- 순서 보장 X
- 데이터 중복 X
✔️ 주요 동작
- 삽입(Insertion)
- 새로운 원소를 집합에 추가하는 동작
- 집합에 이미 존재하는 원소는 중복으로 삽입되지 않는다.
- 삭제(Removal)
- 주어진 원소를 집합에서 제거하는 동작
- 포함 여부(Containment)
- 주어진 원소가 집합에 속하는지 여부를 확인하는 동작
- 교집합(Intersection)
- 두 집합 간의 공통된 원소들을 모은 새로운 집합을 생성하는 동작
- 합집합(Union)
- 두 집합의 모든 원소를 포함한 새로운 집합을 생성하는 동작
- 차집합(Difference)
- 한 집합에서 다른 집합의 원소를 제거한 새로운 집합을 생성하는 동작
- 부분 집합 여부(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를 사용하는 것이 좋다.
💋 참고자료
도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!
반응형
