🏷️리스트(List) vs 세트(Set)
리스트는 요소들의 순차적인 컬렉션이다. 요소들은 특정 순서를 가지며, 같은 요소가 여러 번 나타날 수 있다.
- ✔️특징
- 순서 유지 : 리스트에 추가된 요소는 특정한 순서를 유지한다. 이 순서는 추가된 순서를 반영할 수 있다.
- 중복 허용 : 리스트는 동일한 값이나 객체의 중복을 허용한다. 예를 들어, 같은 숫자나 문자열을 리스트 안에 여러 번 저장할 수 있다.
- 인덱스 접근 : 리스트의 각 요소는 인덱스를 통해 접근할 수 있다. 이 인덱스는 보통 0부터 시작한다.
- 용도 : 순서가 중요하거나 중복된 요소를 허용해야 하는 경우
세트는 유일한 요소들의 컬렉션이다. 참고로 세트보다는 셋으로 많이 불린다.
- ✔️특징
- 유일성 : 셋에는 중복된 요소가 존재하지 않는다. 셋에 요소를 추가할 때 이미 존재하는 요소면 무시된다.
- 순서 미보장 : 대부분의 셋 구현에서는 요소들의 순서를 보장하지 않는다. 요소를 출력할 때 입력 순서와 다를 수 있다.
- 빠른 검색 : 셋은 요소의 유무를 빠르게 확인할 수 있도록 최적화되어있다. 이는 데이터의 중복을 방지하고 빠른 조회를 가능하게 한다.
- 용도 : 중복을 허용하지 않고 요소의 유무만 중요한 경우
🏷️직접 구현하는 셋
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 i = 0; i < elementData.length; i++) {
if (elementData[i] == value) {
return true;
}
}
return false;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyHashSetV0{" +
"elementData=" + Arrays.toString(elementData) +
", size=" + size +
'}';
}
}public class MyHashSetV0Main {
public static void main(String[] args) {
MyHashSetV0 myHashSetV0 = new MyHashSetV0();
myHashSetV0.add(1);
myHashSetV0.add(2);
myHashSetV0.add(3);
myHashSetV0.add(4);
myHashSetV0.add(5);
System.out.println(myHashSetV0);
boolean result = myHashSetV0.add(3);
System.out.println("중복 데이터 저장 결과 : " + result);
System.out.println(myHashSetV0);
System.out.println("myHashSetV0.contains(3) : " + myHashSetV0.contains(3));
System.out.println("myHashSetV0.contains(99) : " + myHashSetV0.contains(99));
}
}- ✔️정리
add(value): 셋에 중복된 값이 있는지 체크하고, 중복된 값이 있으면false를 반환한다. 중복된 값이 없으면 값을 저장하고true를 반환한다.contains(value): 셋에 값이 있는지 확인한다. 값이 있으면true를 반환하고, 값이 없으면false를 반환한다.add(value)의 경우contains(value)를 사용하는데 이 때,contains(value)의 경우 for문을 통해 탐색하는데 이 때 시간 복잡도는O(N)이다. 중복 데이터 검색O(N)+ 데이터 추가O(1)이므로 최종 시간 복잡도는O(N)이다.contains(value)로 데이터를 찾을 때는 배열에 있는 모든 데이터를 찾고 비교해야 하므로 평균적으로O(N)이 걸린다.
🏷️해시 알고리즘 - 인덱스 사용
public class HashStart1 {
public static void main(String[] args) {
Integer[] inputArray = new Integer[10];
inputArray[1] = 1;
inputArray[2] = 2;
inputArray[5] = 5;
inputArray[8] = 8;
System.out.println("inputArray = " + Arrays.toString(inputArray));
int searchValue = 8;
Integer result = inputArray[searchValue]; // O(1)
System.out.println(result);
}
}- ✔️정리
- 데이터의 값을 인덱스 번호로 사용하는 아이디어로 검색 연산을
O(1)의 시간 복잡도로 설계할 수 있다. - 데이터를 입력할 때 배열에 순서대로 입력하는 것이 아니라 데이터 값을 인덱스로 사용해서 저장했다.
- 데이터의 값을 인덱스 번호로 사용하는 아이디어로 검색 연산을
🏷️해시 알고리즘 - 메모리 낭비
public class HashStart2 {
public static void main(String[] args) {
Integer[] inputArray = new Integer[100];
inputArray[1] = 1;
inputArray[2] = 2;
inputArray[5] = 5;
inputArray[8] = 8;
inputArray[14] = 14;
inputArray[99] = 99;
System.out.println("inputArray = " + Arrays.toString(inputArray));
}
}- ✔️정리
- 데이터의 값을 인덱스 번호로 사용한 덕분에
O(1)의 빠른 검색을 얻었으나 입력 값의 범위가 넓어지게 된다면 낭비되는 메모리 공간이 그에 비례해 많아지게 된다.
- 데이터의 값을 인덱스 번호로 사용한 덕분에
🏷️해시 알고리즘 - 나머지 연산
모든 숫자를 입력할 수 있다고 가정하면 입력값의 범위가 너무 넓어져서 데이터의 값을 인덱스로 사용하기는 어렵다. 공간도 절약하면서 넓은 범위의 값을 사용할 수 있는 방법으로 나머지 연산이 있다.
✔️해시 인덱스
배열의 인덱스로 사용할 수 있도록 원래의 값을 계산(여기선 나머지 연산)한 인덱스를 해시 인덱스라 한다. 기본 용량을 10으로 가정할 때 14의 해시 인덱스는 4, 99의 해시 인덱스는 9인 것이다.
public class HashStart3 {
private static final int CAPACITY = 10;
public static void main(String[] args) {
System.out.println("hashIndex(1) = " + hashIndex(1));
System.out.println("hashIndex(2) = " + hashIndex(2));
System.out.println("hashIndex(5) = " + hashIndex(5));
System.out.println("hashIndex(8) = " + hashIndex(8));
System.out.println("hashIndex(14) = " + hashIndex(14));
System.out.println("hashIndex(99) = " + hashIndex(99));
Integer[] inputArray = new Integer[CAPACITY];
add(inputArray, 1);
add(inputArray, 2);
add(inputArray, 5);
add(inputArray, 8);
add(inputArray, 14);
add(inputArray, 99);
System.out.println("inputArray = " + Arrays.toString(inputArray));
//검색
int searchValue = 14;
int hashIndex = hashIndex(searchValue);
System.out.println("searchValue hashIndex = " + hashIndex);
Integer result = inputArray[hashIndex]; // O(1)
System.out.println(result);
}
private static void add(Integer[] inputArray, int value) {
int hashIndex = hashIndex(value);
inputArray[hashIndex] = value;
}
private static int hashIndex(int value) {
return value % CAPACITY;
}
}✔️코드 문제점 : 해시 충돌
예를 들어, 99를 10으로 나눈 나머지는 9고 19를 10으로 나눈 나머지 역시 9다. 이렇게 되면 같은 해시 인덱스를 가지게 되어 해시 충돌이 발생하게 된다.
🏷️해시 알고리즘 - 해시 충돌 설명
해시 충돌의 해결 방안은 바로 해시 충돌이 일어났을 때 단순하게 같은 해시 인덱스의 값을 같은 인덱스에 함께 저장하는 것이다. 아래와 같이 배열 안에 배열을 만드는 것이다.
빅오 표기법은 최악의 경우를 기준으로 시간 복잡도를 제공한다. 위와 같이 예를 들어, 9, 19, 29, 99만 저장한다고 가정하면 이 경우 모든 해시 인덱스가 9가 된다. 따라서 9번 인덱스에 데이터가 모두 저장된다. 데이터를 찾을 때 9번에 가서 저장한 데이터의 수만큼 반복해서 값을 찾아야 한다. 따라서 최악의 경우 O(N)의 성능을 보인다.
🏷️해시 알고리즘 - 해시 충돌 구현
public class HashStart4 {
private static final int CAPACITY = 10;
public static void main(String[] args) {
// 전체의 큰 연결 리스트 하나
LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
System.out.println("buckets : " + Arrays.toString(buckets));
// 그 안에 각 해시 인덱스 값에 속하는 세분화된 연결 리스트 하나
for (int i = 0; i < CAPACITY; i++) {
buckets[i] = new LinkedList<>();
}
System.out.println("buckets : " + Arrays.toString(buckets));
add(buckets, 1);
add(buckets, 2);
add(buckets, 5);
add(buckets, 8);
add(buckets, 14);
add(buckets, 99);
add(buckets, 9);
System.out.println("buckets : " + Arrays.toString(buckets));
int searchValue = 9;
boolean contains = contains(buckets, searchValue);
System.out.println("buckets.contains(" + searchValue + ") = " + contains);
}
private static void add(LinkedList<Integer>[] buckets, int value) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex];
// 중복되는지의 여부를 확인하는 과정에서 O(N)
if (!bucket.contains(value)) {
bucket.add(value);
}
}
private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Integer> bucket = buckets[searchValue];
return bucket.contains(hashIndex);
}
private static int hashIndex(int value) {
return value % CAPACITY;
}
}- ✔️해시 인덱스 충돌 확률
- 해시 충돌이 발생하면 데이터를 추가하거나 조회할 때 연결리스트 내부에서
O(N)의 연산이 필요하다. 따라서 성능을 위해서 가급적이면 해시 충돌이 발생하지 않도록 해야 한다. - 해시 충돌이 발생할 확률은 입력 데이터 수와 배열 크기와 관련이 있다. 입력하는 데이터 수와 비교해서 배열의 크기가 클수록 충돌 확률은 낮아진다.
- 배열의 크기를 크게 만든다면 해시 충돌은 줄어들어 성능이 좋아지겠지만 많은 메모리가 낭비된다. 반대로 배열의 크기를 너무 작게 만들면 해시가 자주 충돌해 성능이 나빠진다. 상황에 따라 다르겠지만 보편적으로 75%를 적절한 크기로 보고 기준을 잡는 것이 효과적이다.
- 해시 충돌이 발생하면 데이터를 추가하거나 조회할 때 연결리스트 내부에서
