리스트(List) VS 세트(Set)
List(리스트)
정의 : 리스트는 요소들의 순차적인 컬렉션으로, 요소들은 특정 순서를 가지며 같은 요소가 여러번 나타날 수 있다.
특징
- 순서유지 : 리스트에 추가된 요소는 특정한 순설를 유지한다.
- 중복허용 : 리스트는 동일한 값이나 객체의 중복을 허용한다.
- 인덱스 접근: 리스트의 각 요소는 인덱스를 통해 접근할 수 있다.
- 순서가 중요하거나 중복된 요소를 허용해야 하는 경우에 주로 사용한다.
Set(세트)
정의: 세트는 유일한 요소들의 컬렉션이다.
특징
- 유일성: 셋에는 중복된 요소가 존재하지 않는다. 셋에 요소를 추가할 때 이미 존재하는 요소면 무시된다.
- 순서 미보장: 대부분의 셋 구현에는 순서를 보장하지 않는다. 즉 요소를 출력할 때 입력 순서가 다를 수 있다.
구현으로 알아보는 Set
Set0
add(value):셋에 값을 추가한다. 단 중복 데이터는 추가하지 않는다.contains(value): 셋에 값이 있는지 확인한다.remove(value): 셋에 있는 값을 제거한다.
import java.util.Arrays;
public class MyHashSetV0 {
private int[] elementData = new int[10];
private int size = 0;
public boolean add(int value) {
if (contains(value)) {
return false;
}
elementData[size] = value;
size++;
return true;
}
public boolean contains(int value) {
for (int data : elementData) {
if (data == value) {
return true;
}
}
return false;
}
public int getSize() {
return size;
}
add(value): 셋에 중복된 값이 있는지 체크하고, 중복된 값이 있으면false를 반환한다.
중복된 값이 없으면 값을 저장 후size의 길이를 늘인 . 후true값을 반환한다.contains(value): 셋에 값이 있는지 여부를 파악한다.add()와contains()에서 항상 중복된 값이 있는지를 체크하니 O(n)으로 성능이 나쁘다.
해시 알고리즘의 시작
해시 알고리즘을 사용하면 데이터를 찾는 검색 성능을 평균 O(1)로 끌어올릴 수 있다.
index의 사용
배열은 인덱스의 위치를 사용해서 데이터를 찾을 때 O(1)로 매우 빠른 특징을 가지고 있다.반면에 데이터를 검색할 때는 배열에 들어있는 값 하나하나 비교하므로 인덱스를 활용 할 수 없다.
만약, 데이터를 검색할 때도 인덱스를 활용해서 데이터를 찾을 수 있다면 O(1)로 성능을 획기적으로 끌어올릴 수 있을 것이다.
발상의 전환
데이터의 값 자체를 배열의 인덱스에 맞추어 저장하면 위의 방식대로 진행 할 수 있다.
- 인덱스 1에는 데이터 1이 있고 인덱스 8에는 데이터 8이 있다고 가정해보자.
- 1을 찾으려면 인덱스 1번에 접근하면 된다.
- 2~7의 값을 찾으려면 각 데이터에 맞는 인덱스로 접근하면 된다.
- 하지만 이 방식은 입력값의 범위만큼 큰 배열을 사용해야해서 낭비되는 공간이 많이 발생한다.
나머지 연산 적용
공간을 절약하면서 넓은 범위의 값을 사용할 수 있는 방법으로 나머지 연산을 사용하는 것으로 해결이 가능해졌다. 저장할 수 있는 배열의 크기를 10이라 가정 후, 그 크기에 맞게 나머지 연산을 사용하면 된다.
1%10=12%10=25%10=514%10=499%10=9
여기서 14, 99는 10보다 큰 값이다. 따라서 일반적인 방법으로는 크기가 10인 배열의 인덱스로 사용할 수 없다. 하지만 나머지 연산의 결과를 사용하면 14는 4로, 99는 9로 크기가 10인 배열의 인덱스로 활용할 수 있다.
해시 인덱스
배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스라 한다.
14의 해시 인덱스는 4, 99의 해시 인덱스는 9이다.
해시 인덱스의 성능과 한계
성능: 해시 인덱스를 사용해서 O(1)의 성능으로 데이터를 조회할 수 있게 되었으며, 자료 구조의 조회 속도를 비약작으로 향상할 수 있게 되었다.
한계 - 해시 충돌
예를 들어 1,11 두 값은 10으로 나누면 같은 값 1이 된다. 이처럼 같은 인덱스가 나오면 해시 인덱스가 충돌하여 처리가 곤란해진다.
해시 충돌의 해결
해시 충돌의 해결방안은 해시 충돌이 일어났을 때 단순하게 같은 해시 인덱스의 값을 같은 인덱스에 저장해 버리는 것이다. 물론 여러 데이터를 배열의 하나의 공간에 함께 저장할 수는 없어,배열안에 배열을 만들면 된다.
- 99의 해시 인덱스는 9로, 배열에서 9번 인덱스를 찾는다.
- 배열안에는 또 배열이 있어, 여기에 있는 모든 값을 검색할 값과 하나씩 비교한다.
- 확률적으로 보면 어느 정도 넓게 퍼지기 때문에 평균적으로는 대부분 O(1)의 성능을 제공한다.
- 하지만 최악의 경우 배열에 저장된 데이터의 수만큼 반복해서 O(n)의 성능을 보일 수 도 있다.
