🥪 List와 Set
List와 Set 자료 구조는 데이터를 저장하고 관리하는데 약간의 차이가 있다.
-
List: 요소들의 순차적인 컬렉션(ex. 장바구니 목록)- 순서 유지: 리스트에 추가된 요소는 특정한 순서를 유지한다.
- 중복 허용: 리스트는 동일한 값이나 객체의 중복을 허용한다.
- 인덱스 접근: 리스트의 각 요소는 인덱스를 통해 접근 가능하다.
-
Set: 유일한 요소들의 컬렉션(ex. 회원 ID 목록)- 유일성:
Set에는 중복된 요소가 존재할 수 없다. 이미 존재하는 요소라면 무시된다. - 순서 미보장: 요소들의 순서를 보장하지 않는다.
- 빠른 검색: 요소의 유무를 빠르게 확인할 수 있다.
- 유일성:
그럼 Set 자료 구조를 한번 구현해보자. Set은 인덱스가 없기 때문에 데이터를 넣고, 해당 데이터가 있는지 체크하고, 데이터를 삭제하기만 하면 된다. 여기서 포인트는 데이터를 넣을 때, 중복되는 데이터가 있는지 확인하는 작업을 해줘야 한다.
package collection.set;
import java.util.Arrays;
public class MyHashSetV0 {
private int[] elements = new int[10];
private int size = 0;
// O(n)
public boolean add(int value) {
if (contains(value)) { // 중복되는 데이터가 있는지 체크
return false;
}
elements[size] = value;
size++;
return true;
}
// O(n)
// Set에 해당 데이터가 있는지 체크
public boolean contains(int value) {
for (int element : elements) {
if (element == value) {
return true;
}
}
return false;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyHashSetV0{" +
"elementData=" + Arrays.toString(Arrays.copyOf(elements, size)) +
", size=" + size +
'}';
}
}package collection.set;
public class MyHashSetV0Main {
public static void main(String[] args) {
MyHashSetV0 set = new MyHashSetV0();
set.add(1); // O(1)
set.add(2); // O(n)
set.add(3); // O(n)
set.add(4); // O(n)
set.add(5); // O(n)
System.out.println(set);
boolean result = set.add(4); // 중복 데이터를 저장한다면...?
System.out.println("중복 데이터 저장 결과: " + result);
System.out.println(set);
System.out.println("set.contains(2): " + set.contains(2)); // O(n)
System.out.println("set.contains(100): "+ set.contains(100)); // O(n)
}
}
/*
MyHashSetV0{elementData=[1, 2, 3, 4, 5], size=5}
중복 데이터 저장 결과: false
MyHashSetV0{elementData=[1, 2, 3, 4, 5], size=5}
set.contains(2): true
set.contains(100): false
*/현재 add() 메서드 안에 있는 contains() 메서드로 인해, 데이터를 추가할 때는 중복 데이터가 있는지 확인하는 과정에서 모든 데이터를 뒤져봐야 하므로 성능이 O(n)으로 느리다. 지금이야 데이터가 많지 않아 문제가 없지만, 데이터가 많아지면 효율은 매우 떨어질 것이다. 중복 데이터를 체크하는 부분을 개선할 필요성이 커졌다.
⚙️ 해시 알고리즘
검색 성능을 O(1)로 한껏 끌어올릴 수 있는 획기적인 방법이 있다. 바로 해시 알고리즘을 사용하는 것이다. 먼저 아래의 간단한 코드를 살펴보자.
package collection.set;
import java.util.Arrays;
public class HastStart1 {
public static void main(String[] args) {
Integer[] arr = new Integer[4];
arr[0] = 1;
arr[1] = 3;
arr[2] = 5;
arr[3] = 7;
System.out.println("입력된 배열: " + Arrays.toString(arr));
int searchValue = 7;
for (Integer integer : arr) {
if (integer == searchValue) {
System.out.println(integer);
}
}
}
}
/*
입력된 배열: [1, 3, 5, 7]
7
*/일단 위의 코드처럼 배열에 들어 있는 데이터와 일일이 비교하면 성능은 여전히 O(n)으로 느리다. 이 부분이 문제라는 것이다. 데이터를 검색할 때도 인덱스를 활용할 수만 있다면 얼마나 좋을까? 방법은 아주 간단하다. 데이터의 값 자체를 배열의 인덱스로 사용하면 된다. 이러면 인덱스 번호가 데이터 자체가 될 것이다.
바로 구현해보자.
package collection.set;
import java.util.Arrays;
public class HastStart2 {
public static void main(String[] args) {
Integer[] arr = new Integer[10];
arr[1] = 1;
arr[3] = 3;
arr[5] = 5;
arr[7] = 7;
System.out.println("입력된 배열: " + Arrays.toString(arr));
int searchValue = 7;
Integer result = arr[searchValue];
System.out.println("result = " + result);
}
}
/*
입력된 배열: [null, 1, null, 3, null, 5, null, 7, null, null]
result = 7
*/바로 바로 값을 찾을 수 있어서 좋긴 한데… 이러면 메모리 공간이 지나치게 낭비되는거 아닌가? 아래처럼 범위를 넓혀보면...
package collection.set;
import java.util.Arrays;
public class HastStart3 {
public static void main(String[] args) {
Integer[] arr = new Integer[100];
arr[1] = 1;
arr[3] = 3;
arr[5] = 5;
arr[7] = 7;
arr[14] = 14;
arr[98] = 98;
System.out.println("입력된 배열: " + Arrays.toString(arr));
int searchValue = 98;
Integer result = arr[searchValue]; // O(1)
System.out.println("result = " + result);
}
}지금 사이즈가 100인 배열을 처음 생성할 때도 시간이 소요되는데, 심지어 데이터 6개를 제외한 모든 공간이 낭비되고 있는 상황이다. 이처럼 의도는 좋지만, 데이터의 값 자체를 인덱스로 사용하는 방법은 매우 빠른 성능을 가졌지만, 입력 값의 범위가 조금만 넓어져도 메모리가 지나치게 낭비된다. 추가적인 대책이 필요하다.
이때 저장할 수 있는 배열의 크기에 맞춰 나머지 연산을 사용하면 된다. 나머지 연산의 결과는 절대로 배열의 크기를 넘을 수 없기 때문에 안전하게 인덱스로 사용 가능하다. 이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(Hash Index)라고 한다.
package collection.set;
import java.util.Arrays;
public class HashStart4 {
static final int CAPACITY = 10;
public static void main(String[] args) {
// [1, 2, 5, 8, 14, 99]를 입력값으로 받았다고 가정
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[] arr = new Integer[CAPACITY];
add(arr, 1);
add(arr, 2);
add(arr, 5);
add(arr, 8);
add(arr, 14);
add(arr, 99);
System.out.println("arr = " + Arrays.toString(arr));
// 검색
int searchValue = 14;
int hashIndex = hashIndex(searchValue);
Integer result = arr[hashIndex];
System.out.println(result);
}
// 해시 인덱스를 사용하여 배열에 삽입
private static void add(Integer[] arr, int index) {
int hashIndex = hashIndex(index);
arr[hashIndex] = index;
}
// 해시 인덱스 생성
static int hashIndex(int value) {
return value % CAPACITY;
}
}
/*
hashIndex(1): 1
hashIndex(2): 2
hashIndex(5): 5
hashIndex(8): 8
hashIndex(14): 4
hashIndex(99): 9
arr = [null, 1, 2, null, 14, 5, null, null, 8, 99]
14
*/1, 2, 5, 8, 14, 99라는 데이터를 해시 인덱스를 이용하여 배열에 저장한 간단한 코드다. 그림을 통해 더 자세히 살펴보자.
💾 해시 인덱스를 활용한 데이터 저장
인덱스만 해시 인덱스를 사용하고, 값은 원래 값을 저장하는 것이다. 배열의 인덱스를 활용하고 있기 때문에 하나의 값을 저장하는데 O(1)로 아주 빠른 성능을 제공한다.
🔎 해시 인덱스를 이용한 데이터 조회
조회할 때도 마찬가지로, 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 조회한다. 인덱스를 사용하기 때문에 O(1)로 아주 빠른 성능을 제공한다.
이처럼 입력 값의 범위가 넓어도 실제 모든 값이 들어오지는 않기 때문에 배열의 크기를 제한하고, 나머지 연산을 통해 메모리가 낭비되는 문제를 해결할 수 있다. 하지만… 잘 생각해보면 꺼림칙한 부분이 있다. 해시 인덱스를 사용해서 제한된 배열에 값을 쑤셔 넣는거? 그래 좋다. 근데 같은 해시 인덱스를 가진 데이터들의 경우, 기존 인덱스에 있던 데이터를 날려 버리는거 아닌가?
💥 해시 충돌
예를 들어보자. 위의 예시처럼 배열의 크기가 10이라고 가정해보자. 만약 9를 추가하려 한다면 기존에 있던 99와 충돌할 것이다. 10으로 나누었을 때, 계산되는 해시 인덱스가 같기 때문이다. 이걸 해시 충돌이라고 부른다.
이 그림처럼 99의 값이 먼저 저장된 상태에서 같은 해시 인덱스로 계산된 9라는 데이터가 들어 왔을 때, 99가 지워질 것이다. 이 문제를 해결하기 위해 CAPACITY를 값의 입력 범위까지 늘리는 방법이 있지만, 그럴거면 뭐하러 여기까지 왔나… 보나마나 무지막지한 메모리 낭비가 수반될 것이다. 가장 좋은 해결책은 그냥 “인정” 하는 것이다.
"해시 충돌이 일어날 수 있다고 가능성을 인정하자는 말이다. 그리고 그냥 같은 해시 인덱스의 값을 같은 인덱스에 저장해버리는 것이다."
배열 안에 배열이든 리스트든 어떤 자료 구조를 만들어서, 값들을 저장할 수 있도록 하자는 것이다. 그럼 해시 충돌이 생겨도 그 안을 다시 뒤져보면 된다. 해시 인덱스로 찾는 과정은 O(1), 하지만 해시 충돌이 났을 때 특정 자료 구조 내부를 또 뒤져야 하니까 느릴 수 있다. 근데 그냥 이런 부분을 쿨하게 인지하고 넘어가자는 것이다.
보다시피, 최악의 경우라고 할지라도 O(n)이다. 평균적으로는 데이터가 어느 정도 넓게 퍼지기 때문에 이처럼 최악의 경우만 아니라면 O(1)의 성능을 제공한다. 사용하지 않을 이유가 전혀 없다.
해시 충돌이 일어난 상황을 코드로 한번 구현해보자.
package collection.set;
import java.util.Arrays;
import java.util.LinkedList;
public class HashStart5 {
static final int CAPACITY = 10;
public static void main(String[] args) {
// [1, 2, 5, 8, 14, 99]를 입력값으로 받았다고 가정
// LinkedList를 담을 수 있는 배열 생성
LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
System.out.println("buckets = " + Arrays.toString(buckets));
for (int i = 0; i < CAPACITY; i++) {
// 각 배열 공간에 LinkedList 생성
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(1)
if (!bucket.contains(value)) { // 중복 체크: O(n) 소요
bucket.add(value);
}
}
// 데이터 검색
private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)
return bucket.contains(searchValue); // O(n)
}
static int hashIndex(int value) {
return value % CAPACITY;
}
}
/*
buckets = [null, null, null, null, null, null, null, null, null, null]
buckets = [[], [], [], [], [], [], [], [], [], []]
buckets = [[], [1], [2], [], [14], [5], [], [], [8], [99, 9]]
buckets.contains(9) = true
*/
🤔 해시 인덱스 충돌 확률
당연한 소리지만, 해시 충돌은 가급적 일어나지 않는 것이 좋다. 해시 충돌이 발생할 확률은 입력하는 데이터의 개수와 배열의 크기와 관련 있다. 입력하는 데이터의 개수 대비 배열의 크기가 커질 수록 충돌할 확률은 낮아진다. 위의 예시에서 입력하는 데이터는 그대로 하고, CAPACITY를 조절하면서 확률이 어떻게 변하는지 알아보자.
- CAPACITY = 1 →
[[1, 2, 5, 8, 14, 99, 9]] - CAPACITY = 5 →
[[5], [1], [2], [8], [14, 99, 9]] - CAPACITY = 10 →
[[], [1], [2], [], [14], [5], [], [], [8], [99, 9]] - CAPACITY = 11 →
[[99], [1], [2], [14], [], [5], [], [], [8], [9], []] - CAPACITY = 15 →
[[], [1], [2], [], [], [5], [], [], [8], [99, 9], [], [], [], [], [14]]
보다시피, CAPACITY가 1인 경우에는 모든 해시가 충돌한다. 5의 경우, 배열의 크기가 입력하는 데이터 개수보다 작은 경우 충돌이 자주 발생한다. CAPACITY가 10인 경우, 70% 정도로 약간 여유 있게 데이터가 저장돼 충돌이 가끔 발생한다. 11인 경우에는 충돌이 발생하지 않았고, 15인 경우, 충돌이 한번 발생했다.
간단한 예시이지만, 보통 입력한 데이터의 개수가 배열의 크기의 75%를 넘지 않으면 해시 인덱스는 자주 충돌하지 않는다. 그 이상일 경우, 자주 충돌한다. 그렇다고 배열의 크기를 무작정 크게 만들면 해시 충돌이 적어 성능적으로 좋아지지만, 메모리가 지나치게 낭비될 우려가 있다. "75%를 기준으로 잡도록 하자!"
