Hash - 해시 알고리즘2 - index 사용

배열은 인덱스의 위치를 사용해서 데이터를 찾을 때 O(1)로 매우 빠른 특징을 가지고 있다.

반면에 데이터를 검색할 때는 배열에 들어있는 데이터 하나하나를 모두 비교해야 하므로 인덱스를 활용할 수 없다.

그런데 만약에 데이터를 검색할 때도 인덱스를 활용해서 데이터를 한 번에 찾을 수 있다면 어떻게 될까?

이렇게만 할 수 있다면 O(n) -> O(1)로 바꾸어서 성능을 획기적으로 끌어올릴 수 있을 것이다.

 

물론 인덱스와 데이터의 값은 서로 다르기 때문에 이것은 불가능하다.

인덱스 0에는 데이터 1이 들어있고, 인덱스 3에는 데이터 8이 들어있다.

결국 여기에 8이라는 데이터가 있는지 찾으려면 순서대로 모든 데이터를 비교해야 한다.

 

여기서 생각의 틀을 완전히 뒤집어보자.

데이터의 값 자체를 배열의 인덱스와 맞추어 저장하면 어떨까? 그러니까 데이터의 값 자체를 배열의 인덱스로 사용하는 것이다!

 

 

데이터의 값과 배열의 인덱스를 맞추어 입력 - 시도

인덱스 1에는 데이터 1이 들어있고, 인덱스 8에는 데이터 8이 들어있다.

저장하는 데이터와 인덱스를 완전히 맞춘 것이다. 이제 인덱스 번호가 데이터가 되고, 데이터가 인덱스 번호가 되었다.

 

이제 데이터를 검색해보자.

• 데이터 1을 찾으려면 array[1]을 입력하면 된다.
• 데이터 2을 찾으려면 array[2]을 입력하면 된다.
• 데이터 5을 찾으려면 array[5]을 입력하면 된다.
• 데이터 8을 찾으려면 array[8]을 입력하면 된다.

이제 데이터가 인덱스 번호가 된다. 따라서 배열의 인덱스를 활용해서 단번에 필요한 데이터를 찾을 수 있다.

데이터의 값을 인덱스 번호로 사용하는 아주 간단한 아이디어 하나로 O(n)의 검색 연산을 O(1)의 검색 연산으로 바꿀 수 있다.

 

package collection.set;

import java.util.Arrays;

public class HashStart2 {
    public static void main(String[] args) {
        //입력 1,2,5,8
        //input array : [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("input array : " + Arrays.toString(inputArray));


        int searchValue = 8;
        Integer result = inputArray[searchValue]; //O(1)
        System.out.println("result = " + result);
    }
}

 

실행 결과

input array : [null, 1, 2, null, null, 5, null, null, 8, null]
result = 8

 

데이터를 입력할 때 배열에 순서대로 입력하는 것이 아니라, 데이터의 값을 인덱스로 사용해서 저장했다.

 

데이터를 조회할 때 데이터의 값을 인덱스로 사용해서 조회한다.

int searchValue = 8;
Integer result = inputArray[searchValue]; //O(1)

배열에서 인덱스로 조회하는 것은 O(1)로 매우 빠르다.

 

 

정리

데이터의 값 자체를 배열의 인덱스로 사용했다. 배열에서 인덱스로 데이터를 찾는 것은 매우 빠르다. 그 덕분에 O(n)의 검색 성능을 O(1)로 획기적으로 개선할 수 있었다.

 

문제

입력값의 범위 만큼 큰 배열을 사용해야 한다. 따라서 배열에 낭비되는 공간이 많이 발생한다. 이 문제를 더 알아보자.