[ADT Set] && [Set의 구현체인 HashSet] && [List와 Set의 차이]

 

ADT Set(집합)의 특징 2가지

1. 순서를 보장하지 않음

2. 데이터 중복을 허용하지 않음

 

Set은 언제 사용하면 좋을까?

1.중복된 데이터를 제거해야 할 때!

 

중복된 단어들을 Set에 넣게 되면, 서로 다른 단어들만 남게 된다. 

 

2. 데이터의 존재 여부를 확인해야 할 때(교집합)

 

용인시 사업 지원자의 주민번호와 경기도 사업 지원 수혜자의 주민번호의 교집합(Intersection) 원소들을 구하면 된다. 

 

Set(집합)의 구현체(in JAVA)

1. HashSet( 오늘 다룰 것 )

2.LinkedHashSet

3.TreeSet

 

HashSet

-> Hash Table을 사용하여 Set을 구현

일반적으로,  Hash Function 덕분에 Hash Table의 크기에 상관없이, key를 통하여 상수 시간에 빠르게 데이터에 접근 가

능하다는 점을 이용하여Hash Table을 이용하여 데이터를 빠르게 조회하도록 한 것이 HashSet이다. 

 

위 그림은 JAVA의 HashSet 구현체의 내부 구현 코드이다.

일단, HashSet 객체의 생성자가 new HashMap()이다. 

HashSet은 <VALUE,더미 객체> Pair의 HashMap 객체와 같다. 

HashSet에 데이터를 추가(add)하는 것은 HashMap 객체의 key 값에 Value를 집어 넣고, value 부분에는 내부적으로 더미 

객체인 PRESENT를 집어 넣고 있다. 

또한, HashSet에서 데이를 조회(contains)할 때에는, 내부적으로 HashMap 객체에서 key값을 조회하는 것과 같다. 

 

 

Q. 데이터의 중복도 없고, 데이터의  순서도 상관이 없다고 했을 때, iteration(loop를 돌면서 한 번씩만 접근)목적으로

만, 즉 모든 데이터에 한 번씩 접근하여 아래와 같이 뭔가를 수행하고 싶을 때, List와 Set중 무엇이 더 효율적인가?

 

 

A.

a) List가 메모리를 덜 쓰고,

-> Set은 대부분 HashTable로 구현을 한다. 고로, resizing 작업으로 인하여 list에 비하여 똑같은 데이터의 양임에도 불구하

고, 메모리에 할당되는 배열의 크기가 매우 크다.( 해쉬 테이블의 3/4이 차면, capacity를 2배로 늘림 ). 

b) 구현 특성 상 list가 상대적으로 더 단순하기에 iteration이 더 빠르다. 

->  ArrayList 같은 경우, 배열에다가 데이터를 단순히 순서대로 넣은 것이고, LinkedList의 경우에도 노드를 순서대로 넣은

것에 불과한 것이다. 

그러나, Set의 핵심인 HashTable의 경우, 중간 중간 버킷에 아무 것도 없는 경우가 있을 수가 있다. 

iteration을 할 경우, HashTable의 전체를 다 탐색해줘야 하므로, 버킷에 아무것도 없어도 그 버킷을 확인해 줘야 한다. 

List의 경우, 빈 공간이라는 것이 생길 수 없는 단순한 구조이므로 이러한 비용이 발생하지는 않는다. 

고로 List를 추천(그 중에서도 구현체는 당연히 ArrayList를 추천)