[Data Structure] Set

Set

순열자료 구조이지만 순서라는 개념이 존재하지않는 순열자료입니다.

• 데이터를 비순차적(unordered)으로 저장할 수 있는 순열자료구조(collection)
• 삽입(insertion) 순서대로 저장되지 않습니다. (특정한 순서를 기대할 수 없는 자료구조)
• 수정이 가능합니다(mutable)
• 동일한 값을 여러번 삽입이 불가능합니다(동일한 값이 여러번 삽입되면 하나의 값만 저장됩니다)

Set의 구조

** 잠깐!! 해쉬함수란?!

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.

즉, 어떠한 값이 들어와도 동일한 길이의 데이터로 나옵니다.

해시는 기본적으로 단방향 암호화 이며 각각의 키에 대해 모두 다른 해시값을 가집니다. 

만약 다른 키에 대래 해시값이 중복된다면, 이를 해시 충돌(Collision)이라고 합니다.

또한 같은 데이터가 들어왔을때는 동일한 해쉬값으로 나옵니다!

• Array와 달리 요소들을 순차적으로 저장하지 않습니다.
• Set에서 요소들이 저장되는 과정
  1. 저장할 요소의 값의 hash 값을 구합니다.
  2. 해쉬값에 해당하는 공간(bucket)에 값을 저장합니다.
• 이렇게 set은 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없습니다.
  - 순서가 없다 = indexing이 없다.
• 해쉬값 기반으로 저장하기 때문에 중복된 값을 저장할 수 없습니다.
• Look up 이 굉장히 빠릅니다!
  - Look up : 특정 값을 포함하고 있는지를 확인하는것
  - 해쉬값과 버켓주소(해쉬값으로되어있음)을 직접 비교하기에 빠르다!
  - Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 됩니다 O(1)

그렇다면! Set는 언제 사용해야할까?!

• 중복된 값을 골라내야 할때
• 특정 요소(element)의 존재 여부에 관해 빠른 look up을 해야 할때
• 그러면서 순서는 상관없을때
• 합집합,교집합들 집합에 대한 연산을 할때

실사용 예