Hash - 해시 알고리즘4 - 나머지 연산

앞에서 이야기한 것 처럼 모든 숫자를 입력할 수 있다고 가정하면, 입력값의 범위가 너무 넓어져서 데이터의 값을 인덱스로 사용하기는 어렵다. 하지만 입력 값의 범위가 넓어도 해당 범위의 값을 모두 다 입력하는 것은 아니다.

앞의 예에서 0~99 범위의 값 중에 1,2,5,8,14,99만 입력했다. 따라서 대부분의 공간은 낭비되었다.

 

공간도 절약하면서, 넓은 범위의 값을 사용할 수 있는 방법이 있는데, 바로 나머지 연산을 사용하는 것이다.

저장할 수 있는 배열의 크기(CAPACITY)를 10이라고 가정하자. 그 크기에 맞추어 나머지 연산을 사용하면 된다.

여기서 14,99는 10보다 큰 값이다. 따라서 일반적인 방법으로는 크기가 10인 배열의 인덱스로 사용할 수 없다.

하지만 나머지 연산의 결과를 사용하면 14는 4로, 99는 9로 크기가 10인 배열의 인덱스로 활용할 수 있다.

나머지 연산의 결과는 절대로 배열의 크기를 넘지 않는다. 예를 들어 나머지 연산에 10을 사용하면 결과는 0~9 까지만 나온다. 절대로 10이 되거나 10을 넘지 않는다. 따라서 연산 결과는 배열의 크기를 넘지 않으므로 안전하게 인덱스로 사용할 수 있다.

 

해시 인덱스

이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(hash index)라 한다.

14의 해시 인덱스는 4,99의 해시 인덱스는 9이다.

• 저장할 값에 나머지 연산자를 사용해서 해시 인덱스를 구한다
  • 1 % 10 = 1
  • 2 % 10 = 2
  • 5 % 10 = 5
  • 8 % 10 = 8
  • 14 % 10 = 4
  • 99 % 10 = 9
• 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 저장한다
  • 예 ) inputArray[hashIndex] = value
  • 인덱스만 해시 인덱스를 사용하고, 값은 원래 값을 저장한다.
• 배열의 인덱스를 사용하기 때문에 하나의 값을 저장하는데 O(1)로 빠른 성능을 제공한다
  • 해시 인덱스 생성 O(1) + 해시 인덱스를 사용해 배열에 값 저장 O(1) -> O(1)

package collection.set;

public class HashStart4 {
    static final int CAPACITY = 10;
    public static void main(String[] args) {
        System.out.println("hashIndex(1) = " + hashIndex(1));
        System.out.println("hashIndex(2) = " + hashIndex(2));
        System.out.println("hashIndex(5) = " + hashIndex(5));
        System.out.println("hashIndex(8) = " + hashIndex(8));
        System.out.println("hashIndex(14) = " + hashIndex(14));
        System.out.println("hashIndex(99) = " + hashIndex(99));
        
        Integer[] inputArray = new Integer[CAPACITY];
        add(inputArray,1);
        add(inputArray,2);
        add(inputArray,5);
        add(inputArray,8);
        add(inputArray,14);
        add(inputArray,99);

        //검색
        int searchValue = 14;
        int hashIndex = hashIndex(searchValue);
        System.out.println("searchValue hashIndex = " + hashIndex);
        Integer result = inputArray[hashIndex];
        System.out.println("result = " + result);

    }



    private static void add(Integer[] inputArray,int value) {
        int hashIndex = hashIndex(value);
        inputArray[hashIndex]=value;
    }

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

실행결과

hashIndex(1) = 1
hashIndex(2) = 2
hashIndex(5) = 5
hashIndex(8) = 8
hashIndex(14) = 4
hashIndex(99) = 9
searchValue hashIndex = 4
result = 14

 

한계 - 해시 충돌