Java Collection 해시 도입 - 성능 개선

해시 알고리즘(Hash Algorithm)을 사용하면 데이터를 찾는 검색 기능을 평균 O(1) 속도로 끌어올리는 알고리즘이 있다.

검색시 for문 으로 하나하나 찾게 되면 O(n) 속도가 발생하는데 해시 알고리즘을 결합하면 높은 성능을 제공할 수 있다.

Main.class

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Integer[] input = new Integer[8];
        input[0] = 1;
        input[1] = 3;
        input[2] = 5;
        input[3] = 7;
        input[4] = 9;
        input[5] = 11;
        input[6] = 13;
        input[7] = 15;
        System.out.println("Array: " + Arrays.toString(input));

        int whereNumber = 11;

        for (Integer i : input) {
            if (i == whereNumber) {
                System.out.println("find Number: " + i);
            }
        }
    }
}

• 숫자 배열로 8개를 담을 수 있는 input 선언 후 각 값을 할당하였다.
• for문으로 찾는 값(11) 검색에는 모든 데이터를 찾아서 if문으로 비교해봐야 한다. 특정 데이터를 찾는 시간에는 평균적으로 O(n) 성능으로 느리다.
• 데이터가 많을 수록 더더욱 느려진다.

느린 검색 기능 개선 - 인덱스 사용하기

배열은 인덱스 위치를 사용해 O(1) 속도로 매우 빠르게 데이터를 입력할 수 있다.
검색에는 배열의 모든 데이터를 찾아 인덱스를 사용해 if문으로 비교하였다.

이러한 검색을 개선해 O(n) 성능을 O(1) 끌어올리는 방법이 여러 종류 있다.

+-----+-----+-----+-----+-----+-----+
|  1  |  3  |  5  |  7  |  9  | 11  | ...
+-----+-----+-----+-----+-----+-----+
[0]   [1]   [2]   [3]   [4]   [5]     <- Index

• 인덱스 0번에는 데이터 1이 들어있고, 인덱스 5번에는 11이 들어 있다.
• 상단의 코드에서 11 값 데이터를 찾으려면 모든 인덱스를 찾아가 요소들을 비교하고 찾았었다.

생각을 바꿔 데이터가 숫자인데 숫자와 인덱스의 위치로 사용하면 어떨까? 다음과 같은 구성이 될 것이다.

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|     |  1  |     |  3  |     |  5  |     |  7  |     |  9  |     | 11  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
[0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]   [8]   [9]   [10]   [11]     <- Index

• 인덱스 1번에는 숫자 1이 들어가고, 인덱스 11에는 11 데이터가 들어간다.

코드로 표현하면 다음과 같다.

Main.class

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Integer[] input = new Integer[12];
        input[1] = 1;
        input[3] = 3;
        input[5] = 5;
        input[7] = 7;
        input[9] = 9;
        input[11] = 11;
        System.out.println("Array: " + Arrays.toString(input));

        int whereNumber = 11;

        System.out.println("find Number: " + input[whereNumber]);
    }
}

Array: [null, 1, null, 3, null, 5, null, 7, null, 9, null, 11]
find Number: 11

for문이 제거되어 훨씬 빠른 O(1) 성능을 보장한다.
데이터를 순서대로 입력한 것이 아닌 값을 인덱스로 사용해 저장한 것이다.
조회할 때도 인덱스에 값을 통해 넣어 바로 검색할 수 있게 한다.

배열에서 인덱스로 데이터를 찾는 것은 매우 빠르게 개선할 수 있었고, O(1) 속도로 개선되었다.

그러나 입력 값의 범위 만큼 매우 큰 배열을 사용해야하므로 낭비되는 고악ㄴ이 많아진다.