Set 자료구조에 대해서

Set이란 무엇인가?

Set(집합)은 같은 타입의 서로 다른 값을 중복 없이 저장하고자 할 때 사용하는 자료구조형.

Set은 배열과 굉장히 비슷하지만,
1. 중복값을 허용하지 않고
2. 순서가 없다
는 부분에서 배열과 차이가 있다.

그렇다면 왜 Set은 중복값을 허용하지 않고 순서가 없는가?
그 이유는 Hash연산의 결과값을 이용하여 데이터를 저장하기 때문이다.

해시 연산(hash function)이란?

입력된 임의의 크기의 데이터를 고정된 크기의 데이터로 매핑하는 함수 또는 알고리즘

이해를 돕기 쉽게 설명하는 방법이 바로 나눗셈의 나머지 값을 구하는 연산인데

[10000,524509,79119491,10776] 

의 10을 나눈 나머지로 매핑하여 각각의 값은 아래의 값으로 각각 매핑한다.

[0, 9, 1, 6]

다시 내가 10000을 찾고자 할때 %10 연산을 통해 바로 0을 얻어서 0의 인덱스에 무엇이 저장되어있는지 확인할 수 있다.

이러한 연산은 배열처럼 반복문 돌리며 모든 데이터를 탐색하지 않고도 바로 데이터를 검색을 할 수 있도록 도와준다.

해시 충돌

다만 방금 예를 든 % 10의 해시 연산은 아주아주 좋지 못한 해시 연산이다.
왜냐면 10000 도, 10도 결국 다 0으로 매핑되기 때문이다.
이런 경우를 해시충돌 이라고 한다.

1. Set이 배열보다 좋은점

hash연산을 사용하므로 배열에 비해 빠른 탐색이 가능하다.
그러므로 집합 연산 역시 빠르게 처리할 수 있으며 중복 값을 제거할 수 있다.

2. Set에 사용되는 Hash란 무엇인가

입력된 임의의 크기의 데이터를 고정된 크기의 데이터로 매핑하는 함수 또는 알고리즘

3. Hash의 장점

1:1로 데이터를 매핑하기 때문에, 검색 및 데이터를 삽입하는데 있어서 빠르게 처리할 수 있다.
또한 데이터의 유일성을 보장하기 때문에, 데이터 중복 방지하는데 도움이 된다.

4. 왜 Set은 배열이 아닌 hash가 제공되는가. 배열에 비해 Hash가 좋은 점은?

Set과 배열의 가장 큰 차이점은 중복값을 허용하지 않는 다는 점인데,
만약 Set이 hash연산을 통해 값을 데이터를 저장하지 않는다면,
매번 새로운 데이터를 삽입할때마다 중복값이 없는지 탐색하고 저장해야 할 것이다.
이것은 Hash연산에 비해 훨씬 더 많은 시간이 소요되며 역시 배열 내 요소를 검색하는데도 더 많은 시간이 걸린다.
이는 즉 메모리 사용량이 늘어날 수 있다.