Set - HashSet

Set 이란

특징

List와는 다르게, 중복을 허용하지 않고, 순서를 보장하지 않는 자료구조임.

데이터를 담는 자료 구조로서 '배열'을 사용함.

 

한계

입력 성능이 구림

기존에 저장된 값 중 중복값이 있다면, 추가적으로 배열에 저장되지 않음.

즉. 기존에 있던 모든 값들과 대조(탐색)해야 하기 때문에 O(n) 의 구린 성능을 자랑함.. 

 

극복

Hash 알고리즘 채택.

 

Hash 알고리즘이란?

자료의 클래스, 필드 정보들을 섞어 공식을 통해 Hash화(숫자) 하여, 이를 인덱스로 활용하는 알고리즘이다.

 

자료를 해쉬화하여 array[hashIndex] 에 접근. O(1)

배열의 해당 위치에 동일한 자료가 있는지 확인 O(n).

여기서 탐색에 O(n)이 발생하게 되지만, 중복되는 일이 그렇게 많지 않아 전체 탐색 수(n)이 크지 않아 성능 상 문제가 되지 않는다.

 

여기서 발생하는 한계점

메모리 낭비가 심각함.

인덱스화하여 사용하는 것까진 좋았는데, 배열에 담을 가짓수가 많으면 결국 메모리 낭비로 이어짐.

 

극복

나머지 연산

 

원리

필요한(혹은 부여받은) 용량(CAPACITY) 의 배열을 생성 후, 나머지 연산 % 진행

해쉬화한 숫자를 한번 더 큰 폭으로 줄여 인덱스로 사용한다. 이를 통해 불필요한 메모리 할당을 막을 수 있다.

 

자료의 해쉬화 + 나머지 연산까지 진행하여 자료 접근을 용이하게 해주는 것이 hash알고리즘이다.