Hash - 해시 알고리즘3 - 메모리 낭비

이번에는 입력값의 범위를 0~99까지 넓혀보자.

 

문제

• 입력 : 0~99 사이의 여러 값이 입력된다. 중복된 값은 입력되지 않는다.
• 찾기 : 0~99 사이의 값이 하나 입력된다. 입력된 값 중에 찾는 값이 있는지 확인해보자.

검색 속도를 높이기 위해 앞서 학습한 것 처럼 데이터의 값을 배열의 인덱스로 사용하자.

따라서 데이터가 0~99 까지 입력될 수 있다면 인덱스도 0~99까지 사용할 수 있어야 한다. 따라서 크기 100의 배열이 필요하다.

package collection.set;

import java.util.Arrays;

public class HashStart3 {
    public static void main(String[] args) {
        //입력 1,2,5,8,14,99

        Integer[] inputArray = new Integer[100];
        inputArray[1]=1;
        inputArray[2]=2;
        inputArray[5]=5;
        inputArray[8]=8;
        inputArray[14]=14;
        inputArray[99]=99;
        System.out.println("input array : " + Arrays.toString(inputArray));

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

    }
}

실행결과

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

 

한계

데이터의 값을 인덱스로 사용한 덕분에 O(1)의 매우 빠른 검색 속도를 얻을 수 있다. 그리고 이 코드는 정상적으로 수행된다. 하지만 낭비되는 메모리 공간이 너무 많다.

 

만약 입력 값의 범위를 0~99를 넘어서 int숫자의 모든 범위를 입력할 수 있도록 하려면 배열의 크기를 얼마로 잡아야 할까?

• 0~99까지 범위 입력
  
  • 사이즈 100의 배열이 필요 : 4byte * 100 (단순히 값의 크기로만 계산)
• int 범위 입력
  
  • int 범위 : -2,147,483,648 ~ 2,147,483,647
  • 약 42억 사이즈의 배열 필요( +,- 모두 포함)
  • 4byte * 42억 = 약 17 기가바이트 필요 (단순히 값의 크기로만 계산)

데이터의 값을 인덱스로 사용할 때, 입력할 수 있는 값의 범위가 int라면 한번의 연산에 최신 컴퓨터의 메모리가 거의 다 소모되어 버린다. 만약 사용자가 1,2,100,200000 네 개의 값만 입력한다면 나머지 대부분의 메모리가 빈 공간으로 낭비될 것이다. 뿐만 아니라 처음 배열을 생성하기 위해 메모리를 할당하는데도 너무 오랜 시간이 소모된다. 따라서 데이터의 값을 인덱스로 사용하는 방식은 입력 값의 범위가 넓다면 사용하기 어려워 보인다.

 

데이터의 값을 인덱스로 사용하는 방법은 매우 빠른 성능을 보장하지만, 입력 값의 범위가 조금만 커져도 메모리 낭비가 너무 심하다. 따라서 그대로 사용하기에는 문제가 있다.