Java Collection 해시 도입 - 해시 충돌 구현하기

이전 작성글에서 이야기한 해시 충돌을 구현해보자.

Hash.class

import java.util.Arrays;
import java.util.LinkedList;

public class Hash {
    static final int CAPACITY = 10;

    public static void main(String[] args) {
        // 1, 3, 5, 7, 9, 13, 14, 16 데이터 입력
        LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
        System.out.println("(null) buckets = " + Arrays.toString(buckets));

        for (int i = 0; i < CAPACITY; i++) {
            buckets[i] = new LinkedList<>();
        }

        System.out.println("(init) buckets = " + Arrays.toString(buckets));

        add(buckets, 1);
        add(buckets, 3);
        add(buckets, 5);
        add(buckets, 7);
        add(buckets, 9);
        add(buckets, 13);
        add(buckets, 14);
        add(buckets, 16);

        System.out.println("(data) buckets = " + Arrays.toString(buckets));

        //검색하기
        int whereNumber = 3;
        boolean contains = contains(buckets, whereNumber);
        System.out.println("bucket.contains(" + whereNumber + ") = " + contains);

    }

    private static void add(LinkedList<Integer>[] buckets, int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex]; // O(1) 속도로 버킷 생성
        // Set 자료구조에서 중복 저장되지 않도록 구현
        if (!bucket.contains(value)) { // O(n) 발생
            bucket.add(value);
        }
    }

    private static boolean contains(LinkedList<Integer>[] buckets, int whereNumber) {
        int hashIndex = hashIndex(whereNumber);
        LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)

        return bucket.contains(whereNumber); // O(n) 발생

        /*for (Integer integer : bucket) {
            if (integer == whereNumber) {
                return true;
            }
        }
        return false;*/
    }

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

(null) buckets = [null, null, null, null, null, null, null, null, null, null]
(init) buckets = [[], [], [], [], [], [], [], [], [], []]
(data) buckets = [[], [1], [], [3, 13], [14], [5], [16], [7], [], [9]]
bucket.contains(3) = true

배열 선언

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

배열 이름은 buckets 바구니들이라고 자주 사용하는 용어이다. 단순한 값이 아닌 배열 안에 배열이 들어가는 것으로 여러 값을 담을 수 있다.

데이터 저장 - add 메소드

private static void add(LinkedList<Integer>[] buckets, int value) {
    int hashIndex = hashIndex(value);
    LinkedList<Integer> bucket = buckets[hashIndex]; // O(1) 속도로 버킷 생성
    // Set 자료구조에서 중복 저장되지 않도록 구현
    if (!bucket.contains(value)) { // O(n) 발생
        bucket.add(value);
    }
}

데이터 저장에는 해시 인덱스(hashIndex) 구한 다음 배열의 인덱스를 찾아낸다.
찾아낸 인덱스 안에는 또 다른 배열로 통해 값을 저장하도록 한다.
Set() 자료구조로도 사용할 것이므로 중복 시 저장되지 않도록 하고, contains() 메소드를 사용해 값이 이미 있는지 중복 여부를 파악한다. 단 contains() 메소드는 O(n) 성능인 것을 잊지 않도록 한다. 그리고 해시 충돌이 발생하지 않는다면 데이터가 1개만 저장하므로 O(1) 성능을 제공할 것이다.

데이터 검색 - contains 메소드

private static boolean contains(LinkedList<Integer>[] buckets, int whereNumber) {
    int hashIndex = hashIndex(whereNumber);
    LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)

    return bucket.contains(whereNumber); // O(n) 발생

    /*for (Integer integer : bucket) {
        if (integer == whereNumber) {
            return true;
        }
    }
    return false;*/
}

해시 인덱스를 통해 먼저 배열의 인덱스를 찾아내 내부의 연결리스트를 꺼내도록 한다.
이어서 LinkedList.contains 메소드를 사용해 데이터가 이미 존재하는지 파악한다.
데이터 저장과 검색 모두 contains() 메소드는 O(n) 성능이며, 충돌이 발생되지 않는 다면 O(1) 속도를 보장한다.

해시 인덱스의 충돌 확률

충돌 확률은 입력하는 데이터량과 배열의 크기와 연관이 크며 서로 반비례 한다. 데이터 량이 많고 배열의 크기가 작다면 충돌 확률은 높아진다. 충돌 확률이 높아졌다는 것은 데이터 저장과 데이터 검색에 O(n) 추가 연산할 가능성이 크다는 것이다. 가급적 충돌나지 않도록 한다.

통계적으로 해시 인덱스 충돌 확률이 75% 넘지 않는다면 자주 발생되지 않는다고 한다. 75% 초과할 경우 충돌이 많아지므로 데이터량과 배열 크기를 신경쓰자.

충돌 확률 계산은 배열의 크기가 10, 저장할 데이터가 8개인 경우 8/10 계산으로 80% 계산되므로 자주 충돌한다고 볼 수 있다.

해시 인덱스를 통한 성능

• 데이터 저장
  • 평균 O(1)
  • 최악 O(n)
• 데이터 조회
  • 평균 O(1)
  • 최악 O(n)

해시 인덱스를 사용하는 방식에는 최악의 경우가 발생되지 않는데, 배열의 크기만 잘 잡아 O(1) 가까운 성능을 제공할 수 있다.