컬렉션 프레임워크 - 해시(Hash)

 

List vs Set

 

List

- 순서 유지 : 리스트에 추가된 요소는 특정한 순서를 유지한다.

- 중복 허용 : 동일한 값이나 객체의 중복을 허용한다.

- 인덱스 접근 : 각 요소는 인덱스를 통해 접근할 수 있다.

순서가 중요하거나 중복된 요소를 허용해야할 경우에 사용한다.

 

Set

유일한 요소들의 컬렉션이다.

- 유일성 : 중복을 허용하지 않는다. 이미 중복된 요소라면 무시된다.

- 순서 미보장 : Set 구현에선 순서를 보장하지 않는다. 출력 시 입력 순서와 다를 수 있음

- 빠른 검색 : 요소의 유무를 빠르게 확인할 수 있도록 최적화되어있다. 이는 데이터 중복을 방지, 빠른 조회 가능하게 한다.

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

 

Set 구현

 

Set을 구현하는 것은 단순하다. 인덱스가 없기 때문에 단순히 데이터를 넣고, 데이터가 있는지 확인하고, 데이터를 삭제하는 정도이다.

그리고 데이터를 추가할 때 중복 여부만 체크해주면 된다.

- add(value) : 중복을 허용하지 않고 추가

- contains(value) : 검색

- remove(value) : 삭제

 

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 size() {
        return size;
    }

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(3) = " + set.contains(3)); // O(n)
        System.out.println("set.contains(99) = " + set.contains(99)); // O(n)
    }

 

첫번째 추가에선 O(1)로 확인할 수 있다. 왜냐하면 첫번째 요소이기 때문에 전체 데이터에서 중복을 확인할 필요가 없다.

두번째 부턴 O(n)이다. 이제부터 데이터에 중복이 있는지 확인해야하기때문에 전체 데이터를 체크하기 때문이다.

 

검색도 O(n), 추가도 중복체크로 검색하기 때문에 O(n). 성능이 좋지 않다. 데이터가 많을수록 더 나빠질 것이다.

중복을 찾는 부분이 성능 저하의 주 요인이다. 이 부분을 어떻게 개선할 수 있을까?

 

해시 알고리즘 

 

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

package collection.set;

import java.util.Arrays;

public class HashStart2 {

    public static void main(String[] args) {
        // input 1,2,5,8
        // inputArray = [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];
        System.out.println("result = " + result);
    }
}

 

{1, 2, 5, 8}의 배열에서 8의 값을 검색했을 때, 총 4번의 반복이 발생한다. 운이 좋으면 한번만에 찾겠지만 그러긴 힘들다.

어쩃건 O(n)으로 실행되는데, O(1)로 성능 개선할 수 있는 방법이 있다.

데이터의 값과 인덱스의 값을 맞추는 것이다.

 

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

 

아래 inputArray[searchValue]; 를 보면, 해당 인덱스에 바로 접근하는 것을 확인할 수 있다.

그럼 성능개선은 되었다. 하지만 지금은 배열이 10개밖에 없지만, 그 숫자가 커진다면 메모리 낭비가 매우 심할 것이다.

이 방법으로 했을 경우 발생하는 메모리 낭비는 어떻게 해결해야할까?

 

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

 

위에서 언급했던것처럼 모든 숫자를 입력할 수 있다고 가정한다면 엄청난 메모리 낭비가 발생한다.

1, 2, 5, 8, 14, 99 의 값을 해시 알고리즘을 적용한다면 실제 사용하는 배열은 6개이지만 90개가 넘는 메모리가 낭비된다.

 

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

저장할 수 있는 크기의 CAPACITY를 10이라고 가정하면, 그 크기에 맞춰 나머지 연산을 사용하면 된다.

 

1 % 10 = 1

2 % 10 = 2

5 % 10 = 5

8 % 10 = 8

14 % 10 = 4

99 % 10 = 9

 

14와 99는 CAPACITY보다 큰 수이기 때문에 크기가 10인 배열에서는 인덱스로 사용할 수 없다.

하지만 나머지 연산을 사용하면 10보다 작은수가 되기 때문에 크기가 10인 배열에서 14와 99를 사용할 수 있게 된다.

 

해시 인덱스

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

 

1. 저장할 값에 나머지 연산자를 사용해서 해시 인덱스를 구한다.

2. 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 저장한다

  - 예) inputArray[hashIndex] = value;

 

배열의 인덱스를 사용하기 때문에 하나의 값을 저장하는데 O(1)로 빠른 성능을 제공한다.

- 해시 인덱스 생성 O(1) + 해시 인덱스를 사용해 배열에 값 저장 O(1)   --->   O(1)

 

 

조회도 마찬가지이다. 해시 인덱스를 구한 후 배열의 인덱스로 사용해서 데이터를 조회한다.

예) int value = inputArray[hashIndex];

마찬가지로 O(1) + O(1) = O(1) 이다.

 

 

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[] 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;
    }

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

 

add(Integer[] inputArray, int value) : hashIndex 메서드로 value의 값을 해시 인덱스를 구하고,

                                                               구한 해시 인덱스 위치에 데이터 (value)를 저장했다.

hashIndex(int value) : 해시 인덱스를 구하는 방법은 value % CAPACITY 이다. 그 값을 리턴한다.

//검색 부분 : 해시 인덱스를 구하고, 배열에 해시 인덱스륻 대입해서 값을 조회한다.

 

 

나머지 연산을 통해 메모리 낭비를 획기적으로 줄일 수 있었다. 그리고 저장하고 조회하는 속도를 O(1)로 비약적으로 향상시켰다.

 

해시 충돌

그러나 문제가 있다.  99의 해시인덱스도 9이고, 9의 해시 인덱스도 9이다. 그럼 9번 인덱스에 여러 값이 들어가 충돌할 수 있다.

 

 

위와같은 상황에선 처음엔 99가 저장되지만, 그 이후에 9번 인덱스에 99에서 9로 값이 바뀌게 되는 상황이 발생한다.

단순하게 CAPACITY를 늘리는 방법도 있지만, 옳다고 할 수 없다. 그러면 해시인덱스를 쓰는 이유도 고민을 해봐야한다.

 

해시 충돌 해결

 

 

해결을 하기 위해선 9번 인덱스에 99와 9의 값을 둘 다 저장하는 방법이 있다.

물론 한 인덱스에 두개의 값을 저장할 순 없기때문에 9번 인덱스 안에 또 다른 배열(자료구조)를 만들면 된다.

조회를 한다고 가정했을 때를 보면

- 9번 인덱스로 접근한다
- 9번 인덱스 안의 또 다른 배열(자료구조)에 있는 모든 값을 찾고자 하는 값과 하나씩 비교한다.

최악의 경우엔 2번 순서에서 9번 인덱스에 많은 데이터가 들어있을 경우 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<Integer>[] buckets = new LinkedList[CAPACITY];
        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]; // buckets[..]를 참조하는 bucket이 되는것. 레퍼런스 타입
        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]; // O(1)
        return bucket.contains(searchValue); // O(n)
    }

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

 

1. 배열 선언

- LinkedList<Integer>[] 타입의 배열 선언. CAPACITY는 10이므로 10개의 LinkedList 타입을 가진 배열이 생성 됨

 

2. 각 인덱스마다 연결 리스트 생성

- 한개의 인덱스에 여러값을 저장할 수 없으니 각 인덱스마다 LinkedList를 생성함. (큰 바구니 안에 작은 바구니를 생성)

 

3. add 메서드

- 해시 인덱스를 구해옴

- buckets[hashIndex]를 참조하는 LinkedList<Integer>타입의 bucket

- 해당 버킷에 입력하려고 하는 value가 있는지 검색

- 해당 value가 저장되어 있지 않으면 (중복이지 않으면) 그 buckets[hashIndex]에 value를 저장.

 

4. contains 메서드

- 해시 인덱스를 구해옴

- buckets[hashIndex]를 참조하는 LinkedList타입의 bucket

- searchValue를 buckets[hashIndex]에서 검색한 후 리턴

 

정리

- 해시충돌은 CAPACITY를 잘 설정하면 잘 일어나지 않음

- 충돌이 발생해서 O(n)이 된다해도 CAPACITY가 잘 설정되어있다면 O(1)에 가까운 O(n)의 성능이 됨

- CAPACITY는 보통 75%정도가 적당함

- 해시 충돌은 확률이라 막을수는 없음

 

---

 

막판에 갑자기 집중력이 떨어졌는지 LinkedList인데 이게 왜 배열인가 ArrayList가 아닌데? 이러면서

한참 고민함.. 또 레퍼런스 타입인데 값을 어떻게 복사했지 부터 뇌정지 오기 시작함

집중안되면 쉬었다 하던지 하자 별거아닌걸로 한참 코드 보고있었네