Today I Learned
자료구조 Set
1. 정의
순서가 없고, 중복을 허용하지 않는 자료구조.
수학으로 치면 유한집합.
2. Set의 특징
- 데이터를 비순차적으로 저장
- 순서가 없음 => index 사용 불가
- 수정 가능(mutable)
- 중복 삽입 불가능, 같은 값이 삽입 되어도 값은 하나만 저장됨
3. Set의 쓰임
- Fast Look up
- 집합 관련 문제
- 중복 값을 찾거나 중복처리를 고려해야 할 때
4. Set의 종류
1) HashSet
- Hash는 값을 저장하고 조회하는데 있어 가장 빠른 알고리즘
- 저장하고자 하는 값을 어떤 값과도 중복되지 않는 숫자 코드(해시코드)로 변환 -> 해시 코드를 인덱스로 한 bucket이라는 array에 해당 인덱스를 찾아 저장
2) TreeSet
- 이진트리의 향상된 버전인 Red-Black Tree를 기반으로 한 알고리즘
- Red-Black Tree : 자식 노드가 최대 2개가 될 수 있는 이진 트리 개념에 더하여, 한 노드를 기준으로 적은 값은 왼쪽에, 큰 값은 오른쪽에 저장하는 개념을 추가한 것
- 새로운 데이터가 들어오면 루트부터 비교 -> 비교의 결과에 따라 우측, 좌측으로 갈지 결정 -> 더 이상 비교를 할 수 없을 때까지 반복
- HashSet 특성 + 오름차순으로 데이터를 정렬
3) LinkedHashSet
- 중복X, 입력한 순서대로 데이터를 저장
- 저장 순서를 유지하고 관리할 때 사용
5. java에서 Set의 활용
₍ ᐢ. ̫ .ᐢ ₎