[Java] 김영한의 자바 중급 2편 #6 - Set

1. List vs Set

자료구조에서 List와 Set은 각각 특정한 방식으로 데이터를 저장하고 관리하는데 사용된다.

 

1.1. List

순서가 중요하거나 중복된 요소를 허용할 때 주로 사용된다.

 

특징

• 순서 유지
• 중복 허용
• 인덱스 접근

1.2. Set

중복을 허용하지 않고 요소의 유무만 중요한 경우에 사용된다.

 

 

특징

• 유일성
• 순서 미보장
• 빠른 검색 (내부적으로 최적화되어 있다.)

 

1.3. List, Set 예시

• List : 장바구니 목록처럼 중요한 일련의 이벤트 목록
• Set : 회원 ID 집합처럼 고유한 항목의 집합

 

2. 직접 구현하는 Set0 - 시작

인덱스가 없기 때문에 데이터를 넣고, 데이터가 있는지 확인하고, 데이터를 삭제하는 정도면 충분하다. 그리고 데이터를 추가할 때 중복 여부만 체크해주면 된다.

• add(value)
• contains(value)
• remove(value)

 

2.1. Set 직접 구현하기

package collection.set;

import java.util.Arrays;

public class MyHashSetV0 {

    private int[] elementData = new int[10];
    private int size = 0;

    // O(n)
    public boolean add(int value) {
        if (contains(value)) {
            return false;
        }
        elementData[size] = value;
        size++;
        return true;
    }

    // O(n)
    public boolean contains(int value) {
        for (int data: elementData) {
            if (data == value) {
                return true;
            }
        }

        return false;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV0{" +
                "elementData=" + Arrays.toString(Arrays.copyOf(elementData, size)) +
                ", size=" + size +
                '}';
    }
}

 

Main

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)
        System.out.println(set);

        boolean result = set.add(4);
        System.out.println("중복 데이터 저장 결과 = " + result);
        System.out.println(set);

        System.out.println("set.contains(3): " + set.contains(3)); // O(n)
        System.out.println("set.contains(99): " + set.contains(99)); // O(n)
    }
}

// result
MyHashSetV0{elementData=[1, 2, 3, 4], size=4}
중복 데이터 저장 결과 = false
MyHashSetV0{elementData=[1, 2, 3, 4], size=4}
set.contains(3): true
set.contains(99): false

 

2.2. 정리

• MyHashSetV0의 구조는 단순하지만 데이터 추가, 검색 모두 O(n)으로 성능이 좋지 않다. 특히 데이터가 많을수록 데이터 효율성은 떨어진다.
• 데이터를 추가할 때마다 중복 데이터가 있는지 체크하기 위해 셋의 전체 데이터를 확인해야 한다.
• 중복 데이터를 찾는 부분의 성능이 떨어진다. 따라서 이 부분을 어떻게 개선할 수 있는가?

 

3. 해시 알고리즘1 - 시작

해시 알고리즘을 사용하면 데이터를 찾는 검색 성능을 O(1)로 비약적으로 끌어올릴 수 있다.

해시 알고리즘을 이해하기 위해 간단한 예제를 만들어보자.

 

 

3.1. 문제

• 입력 : 0 ~ 9 사이의 여러 값이 입력된다. 중복된 값은 입력되지 않는다.
• 출력 : 0 ~ 9 사이의 값이 하나 입력된다. 입력된 값 중에 찾는 값이 있는지 확인해본다.

package collection.set;

import java.util.Arrays;

public class HashStart1 {
    public static void main(String[] args) {
        Integer[] inputArray = new Integer[4];
        inputArray[0] = 1;
        inputArray[1] = 2;
        inputArray[2] = 5;
        inputArray[3] = 8;
        System.out.println("inputArray = " + Arrays.toString(inputArray));

        int searchValue = 8;

        //4번 반복 O(n)
        for (int inputValue : inputArray) {
            if (inputValue == searchValue) {
                System.out.println(inputValue);
            }
        }
    }
}

// result
inputArray = [1, 2, 5, 8]
8

→ 배열에서 특정 데이터를 찾는 성능은 O(n)으로 느리다.

 

4. 해시 알고리즘2 - index 사용

데이터의 값 자체를 배열의 인덱스와 맞추어서 저장을 한다면?

→ 데이터의 값을 인덱스 번호로 사용하는 아주 간단한 아이디어 하나로 O(n)의 검색 연산을 O(1)의 검색 연산으로 바꿀 수 있게 되었다.

• 인덱스1 → 데이터1
• 인덱스2 → 데이터2
• ..
• 인덱스8 → 데이터8

 

 

package collection.set;

import java.util.Arrays;

public class HashStart2 {
    public static void main(String[] args) {
        //입력: 1, 2, 5, 8
        //[null, 1, 2, null, null, 5, null, null, 8, null]
        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);
    }
}

// result
inputArray = [null, 1, 2, null, null, 5, null, null, 8, null]
8

데이터를 조회할 때 데이터의 값을 인덱스로 사용해서 조회했다. → O(1)

int searchValue = 8;
Integer result = inputArray[searchValue];

 

4.1. 정리

• 데이터의 값 자체를 배열의 인덱스로 사용했다. 배열에서 인덱스로 데이터를 찾는 것은 매우 빠르다. 그 덕분에 O(n)의 검색 성능을 O(1)로 획기적으로 개선할 수 있었다.
• 하지만 입력 값의 범위 만큼 큰 배열을 사용해야 했고 이로 인해 배열에 낭비되는 공간이 많이 발생했다.

 

5. 해시 알고리즘3 - 메모리 낭비

입력 값의 범위를 0 ~ 99로 넓혀본다고 가정해보자.

이런 경우에는 데이터가 0 ~ 99까지 입력될 수 있다면 인덱스도 0 ~ 99까지 사용할 수 있어야 하고 배열의 크기도 100이어야 한다.

그렇다면 inputArray는 다음처럼 나타날 수 있을 것이다.

inputArray = [null, 1, 2, null, null, 5, null, null, 8, null, null, null, null,
null, 14, null, null, null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, null, null, null, null, null,
null, null, null, null, null, null, null, null, 99]

 

5.1. 한계

O(1)의 검색 속도를 가질 수 있지만 메모리 공간이 너무 많이 낭비가 된다.

만약 0 ~ 99를 넘어서 int 숫자의 모든 범위를 입력할 수 있도록 하려면 배열의 크기를 얼마로 잡아야 할까?

• int 범위 : -2,147,483,648 ~ 2,147,483,647
  • 약 42억 사이즈의 배열 필요
  • 4byte * 42억 = 약 17기가바이트

 

6. 해시 알고리즘4 - 나머지 연산

공간도 절약하면서 넓은 범위의 값을 사용할 수 있는 방법이 바로 나머지 연산이다.

저장할 수 있는 배열의 크기(CAPACITY)를 10이라고 가정하자. 그 크기에 맞추어 나머지 연산을 사용할 수 있다.

나머지 연산

• 1 % 10 = 1
• ..
• ..
• 14 % 10 = 4
• 99 % 10 = 9

 

6.1. 해시 인덱스

배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스라고 한다.

 

 

 

1. 저장할 값에 나머지 연산자를 사용해서 해시 인덱스를 구한다.
   • 1 % 10 = 1
   • 2 % 10 = 2
   • 5 % 10 = 5
   • ..
   • 14 % 10 = 4
   • 99 % 10 = 9
2. 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 저장한다.
   • inputArray[hashIndex] = value
3. 배열의 인덱스를 사용하기 때문에 하나의 값을 저장하는데 O(1)로 빠른 성능을 제공할 수 있다.

데이터 조회

 

 

 

1. 조회할 값에 나머지 연산자를 사용해서 해시 인덱스를 구한다.
   • 2 % 10 = 2
   • 99 % 10 = 9
   • ..
2. 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 조회한다.
3. int value = inputArray[hashIndex]

 

6.2. 코드로 구현해보기

package collection.set;

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(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);

        // search
        int searchValue = 14;
        int hashIndex = hashIndex(searchValue);
        System.out.println("searchValue hashIndex = " + hashIndex);
        Integer result = inputArray[hashIndex];
        System.out.println("result = " + result);
    }

    static int hashIndex(int value) {
        return value % CAPACITY;
    }

    private static void add(Integer[] inputArray, int value) {
        int hashIndex = hashIndex(value);
        inputArray[hashIndex] = value;
    }
}

// result
hashIndex(1) = 1
hashIndex(2) = 2
hashIndex(8) = 8
hashIndex(14) = 4
hashIndex(99) = 9
searchValue hashIndex = 4
result = 14

 

6.3. 정리

위의 코드는 저장할 위치가 충돌할 수 있다는 한계가 있다. 예를 들어 1, 11 이 2개의 hashIndex는 1로 동일하기 때문에 같은 해시 인덱스 값이 나오게 된다.

 

7. 해시 알고리즘5 - 해시 충돌

99, 9의 두 값은 10으로 나누면 동일하게 9가 나온다. 따라서 다른 값을 입력했지만 같은 해시 코드가 나오게 되는데 이것을 해시 충돌이라고 한다.

 

해시 충돌 해결

해결 방안은 바로 해시 충돌이 일어났을 때 단순하게 같은 해시 인덱스의 값을 같은 인덱스에 함께 저장해버리는 것이다.

 

7.1. 해시 충돌과 저장

 

→ 여러 데이터를 배열의 하나의 공간에 함께 저장할 수는 없다. 대신에 배열 안에 배열을 만들면 된다. 물론 배열 안에 리스트 같은 다른 자료구조를 사용해도 된다.

 

7.2. 해시 충돌과 조회

 

1. 99의 해시 인덱스 값이 9인 것을 찾는다.
2. 그 이후 99, 9 모든 값을 비교하여 equals 메서드로 같은지 확인한다. (int이기 때문에 ==를 써도 되긴 한다.)

물론 여기서 최악의 경우에는 9, 19, 29, 39, .., 99의 값을 하나씩 루프 돌면서 조회해야 한다고 하면 O(n)의 성능과 가깝게 보일 수도 있긴 하지만 99번 루프를 돌지는 않기 때문에 그래도 기존 보다는 성능이 더 나아진 것을 확인할 수 있다.

 

8. 해시 알고리즘6 - 해시 충돌 구현

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, 9}
        LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
        for (int i = 0; i < CAPACITY; i++) {
            buckets[i] = new LinkedList<>();
        }

        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];
        // 중복 데이터 체크 로직
        if (!bucket.contains(value)) {
            bucket.add(value);
        }
    }

    private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }

    private static int hashIndex(int value) {
        return value % CAPACITY;
    }
}

// result
buckets = [[], [1], [2], [], [14], [5], [], [], [8], [99, 9]]
buckets.contains(9) = true

• 배열 선언 : 해시 충돌을 고려해서 배열 안에 또 배열이 들어가야 한다. 그래야 해시 충돌이 발생했을 때 여러 값을 담을 수 있다.배열 안에 연결 리스트가 들어있고, 연결 리스트 안에 데이터가 들어가는 구조이다. → 바구니들(배열)안에 각각의 바구니(연결 리스트)가 있고, 바구니(연결 리스트)안에 데이터가 들어가있는 구조
• LinkedList<Integer>[] buckets = new LinkedList[CAPACITY]
• 데이터 등록 : 해시 인덱스를 먼저 구하고 해시 인덱스로 배열의 인덱스를 찾는다. 해당 인덱스에는 연결 리스트가 들어가 있다. Set은 중복된 값을 저장하지 않기 때문에 contains() 메서드로 중복 체크를 한 뒤에 없으면 add 메서드로 값을 저장한다.
• 데이터 검색 : 해시 인덱스로 배열의 인덱스를 찾는다. 연결 리스트의 contains(searchValue) 메서드로 찾는 데이터가 있는지 확인한다. 연결 리스트의 contains()는 모든 항목을 다 순회하기 때문에 O(n)의 성능을 제공한다. 하지만 해시 충돌이 발생하지 않으면 데이터가 1개만 들어있기 때문에 O(1)의 성능을 제공한다.