[Java - Hash] HashTable / HashCollision(해시 충돌)

HashTable

---

일반적인 List나 배열의 경우 연속된 데이터를 조회할 때 인덱스를 기반으로 검색한다.

// 아래와 같은 int 배열이 있을 때 숫자 3은 index 값으로 2를 갖게된다.
// 숫자3을 출력하기 위해 = arr[2]를 사용할 수 있다. ;
int[] arr = {5,1,3};

HashTable의 경우 한 쌍의 Entry인 Key : Value 로 저장하는데, 위의 arr배열을 Hash로 저장하면 아래와 같다.

  HashTable<Integer, Integer> table = new HashTable<>();
[{0 : 5}, {1 : 1}, {2 : 3}]

각 요소를 출력하기 위해 아래와 같은 함수를 사용할 수 있다.
table.get()

Hash Function

---

HashTable에 데이터를 추가하거나 조회할 때, Hash Function(해시 함수)을 사용한다. 해시 함수는 입력된 Key를 table의 크기에 적합한 인덱스 값으로 변환하는 것이 목적이며, 인덱스 범위(출력 크기)는 Hash Table 크기에 의존적이다. 예를 들어, 크기가 10인 해시 테이블에서 사용하는 해시 함수의 출력 범위는 0부터 9까지이다.

아래에서 설명할 코드는 각 문자열의 문자를 ASCII코드로 변환하여 hashCode로 저장한다.

1. 먼저 HashTable에 10개의 데이터를 저장하기 위해 ("가"* 10) 총 10개의 문자열을 만든다

2. 각 문자열의 hashCode를 만든다

3. (hashCode%table 길이) 연산하여 index를 구한다

public static void main(String[] args) {
   int capacity = 10;
   Hashtable<Integer, String> map = new Hashtable<>(capacity);
   String a = "가";
   int hashCode = 0;
   int i = 1;

   while(i <= capacity) {
       String value = "";
       for(int j = 0; j < i; j++) {
           value += a + " ";
       }
       if(i > 0) {
           hashCode += value.charAt(i-1);
           System.out.println("index = " + hashCode % capacity);
       }
       System.out.println("value = " + value);
       System.out.println("hashCode = " + hashCode + "\n");
       i++;
   }
}

위 코드를 실행하면 index는 구해지지만 중복 인덱스가 발생하게된다. 아래는 위의 코드 실행 결과이다

index = 2
value = 가 
hashCode = 44032

index = 4
value = 가 가 
hashCode = 44064

index = 6
value = 가 가 가 
hashCode = 88096

index = 8
value = 가 가 가 가 
hashCode = 88128

index = 0
value = 가 가 가 가 가 
hashCode = 132160

index = 2
value = 가 가 가 가 가 가 
hashCode = 132192

index = 4
value = 가 가 가 가 가 가 가 
hashCode = 176224

index = 6
value = 가 가 가 가 가 가 가 가 
hashCode = 176256

index = 8
value = 가 가 가 가 가 가 가 가 가 
hashCode = 220288

index = 0
value = 가 가 가 가 가 가 가 가 가 가 
hashCode = 220320

중복 인덱스가 있다면 기존에 존재하는 value값은 사라지고 새로운 index의 value값으로 대체된다. 결론은 먼저 들어온 값 대신 아래와 같이 마지막에 들어온 index 값이 저장되게 된다

이렇게 되면 데이터에 문제가 생길 수 있고 추후 해시 충돌이 일어날 수 있어 적절한 처리가 필요한데, 여기서는 두 가지 방법 중 하나를 예시로 설명한다

1.Separate Chaning(체이닝)
간단히 설명하자면 Linked List를 이용하고 엔트리를 저장할 때 각각 노드값을 갖는 것이다.

2.Open Addressing(개방 주소법)
데이터가 저장될 때 이미 키값이 존재한다면 키값에 +1을 반복하여 빈 자리를 찾는 것이다.

package com.example.practice.stack.hashtable;

import java.util.Hashtable;

public class HashTable {
    public static void main(String[] args) {
        int capacity = 10;
        Hashtable<Integer, String> map = new Hashtable<>(capacity);
        String a = "가";
        int hashCode = 0;
        int i = 1;

        while(i <= capacity) {
            String value = "";

            for(int j = 0; j < i; j++) {
                value += a + " ";
            }

            if(i > 0) {
                hashCode += value.charAt(i-1);
                int index = hashCode % capacity;
                while(map.containsKey(index)) { // Linear probing logic
                    index = (index + 1) % capacity;
                }

                map.put(index, value);
            }
            System.out.println("value = " + value);
            System.out.println("hashCode = " + hashCode);
            System.out.println("index = " + hashCode%capacity);
            System.out.println("map = " + map);
            i++;
        }

    }

}

처음에 저장된 Hash를 확인했을 때와 다른 모습이며 모든 문자열이 인덱스별로 저장된 것을 확인할 수 있다.

하지만 한 곳에 데이터가 몰렸을 경우 계속해서 인덱스 위치가 밀려가며 탐색하는 과정이 생기게되어 시간적으로 효율이 좋지 않을 수 있다.