Hash - 해시 알고리즘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}
        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("bucket.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]]
bucket.contains(9) =true

 

배열 선언

        LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];

먼저 배열의 이름을 buckets 즉 바구니들이라고 지었다. 배열 안에 단순히 값이 들어가는 것이 아니라, 해시 충돌을 고려해서 배열 안에 또 배열이 들어가야 한다. 그래야 해시 충돌이 발생했을 때 여러 값을 담을 수 있다.

여기서는 배열 안에 배열 대신에 편리하게 사용할 수 있는 연결 리스트를 사용했다. LinkedList는 하나의 바구니이다. 이런 바구니를 여러개 모아서 배열을 선언했다. 즉 배열 안에 연결 리스트가 들어있고, 연결 리스트 안에 데이터가 들어가는 구조이다.

쉽게 이야기해서 바구니들(배열) 안에 각각의 바구니(연결 리스트)가 있고, 바구니(연결 리스트) 안에 데이터가 들어가는 구조이다.

 

데이터 등록

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

• 데잍를 등록할 때 먼저 해시 인덱스(hashIndex)를 구한다.
• 해시 인덱스로 배열의 인덱스를 찾는다. 배열에는 연결 리스트가 들어있다.
  • 해시 인덱스를 통해 바구니들 사이에서 바구니인 연결 리스트를 하나 찾는 것이다.
• 셋은 중복된 값을 저장하지 않는다 .따라서 바구니에 값을 저장하기 전에 contains()를 사용해서 중복 여부를 확인한다. 만약 바구니에 같은 데이터가 없다면 데이터를 저장한다.
  • 연결 리스트의 contains() 는 모든 항목을 다 순회하기 때문에 O(n)의 성능이다.
  • 하지만 해시 충돌이 발생하지 않으면 데이터가 1개만 들어있기 때문에 O(1)의 성능을 제공한다.

 

데이터 검색

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)
    }

• 해시 인덱스로 배열의 인덱스를 찾는다. 여기에는 연결 리스트가 들어있다.
• 연결 리스트의 bucket.contains(searchValue)메서드를 사용해서 찾는 데이터가 있는지 확인한다.
  • 연결 리스트의 contains()는 모든 항목을 다 순회하기 때문에 O(n)의 성능이다.
  • 하지만 해시 충돌이 발생하지 않으면 데이터가 1개만 들어있기 때문에 O(1)의 성능을 제공한다.

 

해시 인덱스 충돌 확률

해시 충돌이 발생하면 데이터를 추가하거나 조회할 때, 연결 리스트 내부에서 O(n)의 추가 연산을 해야 하므로 성능이 떨어진다. 따라서 해시 충돌은 가급적 발생하지 않도록 해야 한다.

해시 충돌이 발생할 확률은 입력하는 데이터의 수와 배열의 크기와 관련이 있다. 입력하는 데이터의 수와 비교해서 배열의 크기가 클수록 충돌 확률은 낮아진다.

배열의 크기인 CAPACITY 값을 변경하면서 실행해보자.

아주 간단한 예제로 알아보았지만, 통계적으로 입력한 데이터의 수가 배열의 크기를 75% 넘지 않으면 해시 인덱스는 자주 충돌하지 않는다. 반대로 75%를 넘으면 자주 충돌하기 시작한다.

배열의 크기를 크게 만들면 해시 충돌은 줄어서 성능은 좋아지지만, 많은 메모리가 낭비된다. 반대로 배열의 크기를 너무 작게 만들면 해시가 자주 충돌해서 성능이 나빠진다. 상황에 따라 다르겠지만 보통 75%를 적절한 크기로 보고 기준으로 잡는 것이 효과적이다.

 

정리

해시 인덱스를 사용하는 경우

 

해시 인덱스를 사용하는 방식은  사실 최악의 경우는 거의 발생하지 않는다. 배열의 크기만 적절하게 잡아주면 대부분 O(1)에 가까운 매우 빠른 성능을 보여준다.

이제 O(n)을 O(1)로 바꿀 수 있는 매우 효율적인 해시 알고리즘에 대해서 배웠다.

지금까지 설명한 내용을 바탕으로 MyHashSetV0를 개선해보자.