Set
List vs Set
각각 특정한 방식으로 데이터를 저장하고 관리한다
List
요소들의 순차적인 컬렉션으로 요소들은 특정 순서를 갖고, 중복을 허용한다
인덱스로 요소에 접근할 수 있다
Set
유일한 요소들의 컬렉션으로 요소들은 특정 순서를 갖지 않고, 중복을 허용하지 않는다
셋은 요소의 유무를 빠르게 확인할 수 있도록 최적화 되어 있다 (빠른 조회 가능)
구현
기본적인 형태는 배열을 필드로 갖고
중복 체크를 하는 contains() 와
contains() 를 사용하여 중복 체크 후 값을 추가하는 add() 로 구성
데이터 추가 메서드 add() 는 O(1) 이지만
데이터 추가 시마다 전체 데이터를 대상으로 중복 체크를 해야 하기 때문에
contains() 를 항상 실행해야 하기 때문에
입력 성능이 O(n)으로 좋지 않다
해시 알고리즘
해시 알고리즘을 사용하면 데이터 검색 성능을 O(1) 로 끌어올릴 수 있다
배열의 값 자체를 인덱스로 저장한다면
검색 성능은 O(1) 이 된다
하지만 사용되지 않는 곳의 메모리 낭비가 심하다
100까지의 숫자를 담는 배열이 필요하다면
크기가 100인 배열이 필요하고
데이터의 길이가 10이라면 90이 낭비가 된다
나머지 연산
나머지 연산으로 데이터의 길이만큼 나누고 남은
나머지 값을 사용한다면
배열의 크기를 초과하지 않아
안전하게 인덱스로 사용할 수 있게 된다
(나머지 연산만으로 해시 값 자체가 안전하지는 않음 - 해시 출돌)
해시 인덱스
배열의 인덱스로 사용할 수 있도록 원래 값을 계산한 인덱스를
해시 인덱스라고 한다
인덱스는 해시 값을 사용하고
값은 원래의 값을 사용한다
해시 충돌
값은 다르지만 같은 해시 값을 갖게 되는 경우를
해시 충돌이라고 한다
해시 충돌의 해결
해시 충돌을 피하기보다
언젠가 발생할 일로 생각하면 문제를 해결할 수 있다
해시 충돌이 낮은 확률로 일어날 것이라는 가정한다
해시 충돌 발생 시 같은 해시 인덱스 값을 같은 인덱스에 저장해버리는 것
-> 배열 내부에 중복을 가정하고 배열을 저장한다
이 때 최악의 경우는 O(n) 으로 일반 배열과 같지만
평균적인 속도가 훨씬 빠르다
대부분의 경우 O(1) 의 성능으로 값을 찾을 수 있다
해시 인덱스 충돌 확률
해시 충돌이 발생하면 데이터를 추가/조회 시
연결 리스트 내부에서 O(n) 의 추가 연산을 해야 하므로 성능이 떨어진다
가급적 해시 충돌이 발생하지 않는 편이 좋다
해시 충돌이 발생할 확률은 입력하는 데이터 수와 배열의 크기와 관련이 있다
입력 데이터 수와 비교해 배열의 크기가 충분히 크다면
충돌 확률은 낮아진다
입력 데이터 수가 75% 미만이면 해시 충돌은 자주 발생하지 않는다
자바의 hashCode()
해시 인덱스를 사용하는 자료 구조는 데이터 추가/검색/삭제 성능이 O(1)
따라서 많은 곳에서 사용된다
자바에서는 모든 객체가 자신만의 해시 코드를 표현할 수 있도록
Object 에 hashCode() 메서드를 제공한다
- 대체로 hashCode() 메서드를 오버라이딩 하여 사용
- hashCode() 를 오버라이딩 하지 않으면 참조값 기반 해시 코드를 생성한다
- equals() 또한 오버라이딩해야 한다
- equals() 도 기본적으로는 참조값 기반 비교를 하기 때문
자바에서 기본으로 제공하는 클래스 대부분은
hashCode() 를 오버라이딩 해 두었다
객체를 직접 만드는 경우에만 오버라이딩 하여 사용하면 된다
hashCode() 만 오버라이딩 하면 모든 종류의 객체에 대해 해시 자료구조를 사용할 수 있다
자바의 Set
중복을 허용하지 않고, 순서를 보장하지 않는 자료 구조
Set 인터페이스
자바의 Set 인터페이스는 java.util 패키지의 컬렉션 프레임워크에 속하는 인터페이스
수학의 집합 개념을 구현한 것으로
중복을 허용하지 않는 유일한 요소들의 순서가 없는 집합을 나타낸다
특정 요소가 집합 내에 있는지 여부를 확인하는 것에 최적화 되어 있다
Set 인터페이스는 HashSet, LinkedHashSet, TreeSet 등의 여러 구현 클래스를 가지고 있다
HashSet
- 해시 자료구조를 사용해 요소를 저장
- 특정 순서가 없이 저장됨
- 주요 연산인 추가/삭제/검색 은 평균 O(1) 의 시간 복잡드를 가진다
- 데이터의 유일성만 중요하고 순서가 중요하지 않은 경우에 적합
LinkedHashSet
-
HashSet 에 연결 리스트를 추가해 요소들의 순서를 유지한다
-
시간 복잡도는 HashSet 과 같다
-
데이터의 유일성과 함께 삽입 순서를 유지해야 하는 경우 적합하다
-
연결 링크를 유지해야 하기 때문에 HashSet 보다는 조금 무겁다
-
데이터 대신 node 를 넣어 각 인덱스끼리 연결하고, node 의 값으로 데이터를 갖는다
