Java Collection 해시 도입 - 나머지 연산, 해시 인덱스

Java Collection 해시 도입 전 - 메모리 낭비

이전 시간에 해시 도입 전 성능 개선으로 다음 코드를 작성하였다. 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.

kiioiokiio

앞에서 이야기한 모든 숫자를 입력할 경우 범위가 너무 넓어 값을 인덱스로 사용하기 어렵다고 이전 글에서 살펴보았다. 그렇지만 입력 값의 범위가 넓더라도 해당 범위의 값을 모두 입력하는 것이 아니라는 것을 우리는 알고 있다.

0~11 공간에서 1,3,5,7,9,11 숫자만 입력하였다. 나머지 공간은 입력하지 않아 공간 낭비가 발생하는 것을 볼 수 있다.

공간도 절약하며 넓은 범위의 값을 사용하는 방법 또한 존재하는데, 나머지 연산을 사용한다. 저장할 수 있는 배열의 크기(CAPACITY) 10으로 가정하고 그 크기에 맞춰 나머지 연산을 사용한다.

나머지 연산하기

• 1 % 10 = 1
• 3 % 10 = 3
• 5 % 10 = 5
• 7 % 10 = 7
• 9 % 10 = 9
• 11 % 10 = 1

숫자 11은 10보다 큰 값이므로 일반적으로 크기가 10인 배열의 인덱스에서는 사용할 수 없다.
나머지 연산을 사용한 결과는 11은 1로 나누어지며 14을 추가로 들어온 경우 4로 사용해 10인 배열의 인덱스로 활용할 수 있다.

나머지 연산은 배열의 10을 넘지 않으므로 0~9까지만 사용한다. 10이 되거나 10을 넘지 않는다는 이야기이다. 이로 인해 연산 결과는 배열의 크기를 넘지 않으므로 안전하게 인덱스로 사용하자.

해시 인덱스

본래 배열의 인덱스를 값으로 사용하도록 값을 계산하는 인덱스를 해시 인덱스(HashIndex)라 불려왔다.

11의 해시 인덱스는 1, 14의 해시 인덱스는 4이다.
나머지 연산을 통해 해시 인덱스를 구하고, 배열의 인덱스로 사용한다.

다음 배열에서 3, 5, 7, 9, 14, 16 데이터를 넣는 다고 가정해본다.

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|     |     |     |  3  | 14  |  5  | 16  |  7  |     |  9  |     |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
[0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]   [8]   [9]   [10]

hashIndex는 "value % CAPACITY(10)" 계산되어 배열의 인덱스로 사용하고 그 인덱스에 해당하는 요소를 넣게 된다.

코드로 풀어내면 다음과 같다.

HashIndex.class

import java.util.Arrays;

public class HashIndex {
    static final int CAPACITY = 10;

    public static void main(String[] args) {
        // 3, 5, 7, 9, 14, 16 데이터 입력
        System.out.println("Hash Index(3) = " + hashIndex(3));
        System.out.println("Hash Index(5) = " + hashIndex(5));
        System.out.println("Hash Index(7) = " + hashIndex(7));
        System.out.println("Hash Index(9) = " + hashIndex(9));
        System.out.println("Hash Index(14) = " + hashIndex(14));
        System.out.println("Hash Index(16) = " + hashIndex(16));

        Integer[] input = new Integer[CAPACITY];
        add(input, 3);
        add(input, 5);
        add(input, 7);
        add(input, 9);
        add(input, 14);
        add(input, 16);
        System.out.println(Arrays.toString(input));

        //검색하기
        int whereNumber = 14;
        int hashIndex = hashIndex(whereNumber);
        Integer res = input[hashIndex];
        System.out.println("배열에서 14 값 찾아보기\n인덱스:" + hashIndex + ", 값:" + res);

    }

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

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

Hash Index(3) = 3
Hash Index(5) = 5
Hash Index(7) = 7
Hash Index(9) = 9
Hash Index(14) = 4
Hash Index(16) = 6
[null, null, null, 3, 14, 5, 16, 7, null, 9]
배열에서 14 값 찾아보기
인덱스:4, 값:14

add 메소드까지 정상적으로 기입되는 것을 볼 수 있다. 다음을 이어서 검색하는 기능 또한 잘 동작한다.

해시 인덱스 정리

나머지 연산으로 해시인덱스를 만들어 배열의 문제를 해결되었다.

• 입력 값 범위가 넓어도 모든 값이 배열에 들어가지 않으므로 배열 크기를 제한하고 메모리 낭비 문제가 해결되었다.
• 해시 인덱스를 사용한 O(1) 성능으로 데이터를 저장, 조회에 속도를 향상시킬 수 있었다.

그러나 이러한 해시 인덱스의 한계로 해시 충돌이라는 문제점이 생긴다. 데이터는 서로 다르지만 저장할 위치가 충돌하는 한계까 있다.

• 1 % 10 = 1
• 11 % 10 = 1
• 3 % 10 = 3
• 13 % 10 = 3

이러한 해시 충돌을 어떻게 해결해나갈지 살펴보자.