[Data Structure] Set

Set

---

set은 array나 list 처럼 순열 자료구조 (collection)이다.

하지만 set은 '순서'라는 개념이 존재하지 않다. set의 특징은 다음과 같다.

 

• 데이터를 비순차적(unordered)로 저장할 수 있는 순열 자료구조(collection)
• 삽입 순서대로 저장되지 않는다. 즉, 특정한 순서를 기대할 수 없는 자료구조
• 수정 가능함.(mutable)
• 동일한 값을 여러번 삽입 불가능. 동일한 값이 여러번 삽입되면 하나의 값만 저장된다.
• Fast Lookup이 필요할 때 주로 쓰인다.

 

 

set의 구조

• Array와 달리 set은 요소들을 순차적으로 저장하지 않습니다.
• Set에서 요소들이 저장될 때 순서는 다음과 같습니다.
  1. 저장할 요소의 값의 hash 값을 구한다.
  2. 해쉬값에 해당하는 공간(bucket)에 값을 저장한다.
• 이렇게 set는 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없다. 순서가 없기 때문에 indexing도 없다.
• 그리고 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없는것이다.
• 해쉬값을 기반으로 저장하기 때문에 look up 이 굉장히 빠름.
  • Look up: 특정 값을 포함하고 있는지를 확인 하는것 ==> 5 in my_set
  • Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 됨으로 O(1)

 

hash는 단방향 (one way) 암호화이다. 단방향이란 한번 암호화하면 복호화가 안된다는 뜻이다. 실제 값의 길이와 상관없이 hash 값을 일정한 길이를 가진다. 그렇기에, hash는 주로 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑할 때 사용된다.

 

언제 set을 사용하는가

• 중복된 값을 골라야 할 때
• 빠른 look up을 해야 할때
• 그러면서 순서는 상관없을 때

 

Set 자료구조는 그럼 어떤 경우에 유용하게 사용할 수 있을까 ?

set를 사용하면 다음과 같이 배열의 중복 항목을 간단하게 확인하는 함수를 구현할 수 있다.

그리고 여러 배열들로 부터 유일한 값을 가지는 배열을 재생성 할 수 있다.