Hash - 해시 알고리즘1 - 시작

해시(hash)알고리즘을 사용하면 데이터를 찾는 검색 성능을 평균 O(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("input array : " + Arrays.toString(inputArray));

        int searchValue = 8;
        for (Integer inputValue : inputArray) {
            if(inputValue == searchValue){
                System.out.println(inputValue);
            }
        }
    }
}

실행결과

input array : [1, 2, 5, 8]
8

 

입력 값은 1,2,5,8이다. 이 값을 배열에 넣고, 배열에서 검색 값 8을 찾아보자. 이 값을 찾으려면 배열에 들어있는 데이터를 모두 찾아서 값을 비교해야 한다. 따라서 배열에서 특정 데이터를 찾는 성능은O(n)으로 느리다. 물론 데이터가 많아질 수록 더 느려진다. 여기서 문제의 핵심은 찾기 성능이 O(n)으로 느리다는 점이다.