Hash Table이란?

개념 정리

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

그렇다면 이를 정리하는 해시 함수가 존재할 것이다. 예를 들어, 나눗셈 결과의 나머지를 해시 함수로 사용할 수 있을 것이다. (이를 division Method라고도 부른다.) 그 외에도 다양한 함수들이 존재하는데, 여기서의 공통적인 문제는 해시함수가 같은 값을 출력하는 경우 어떻게 대처할 것인지다.

이렇게 값이 충돌하는 경우를 '해시충돌'이라고 부르며, 이 경우를 해결할 수 있는 방법이 많이 알려져 있다. 크게는 분리 연결법과 개방 주소법이 있는데 이에 대한 설명은 추후 진행할 예정이다.

Hash Map vs. HashTable

자바에는 Map Inferface를 구현한 자료구조로 HashMap과 HashTable가 존재하는데, 둘의 차이를 살펴보자.

public class myHashTableStudy {
    public static void main(String args[]){
        Hashtable<String, Integer> ht = new Hashtable();

        ht.put("key1", 10);
        ht.put("key2", 20);
        
        HashMap<Integer, Integer> hm = new HashMap<>();
        hm.put(0,10);
        System.out.println(hm.get(0));

        // ht.put(null, 999) : Error Occured.
        hm.put(null, -999);
        System.out.println(hm.get(null));


}

가장 단순한 차이로는 key 값에 null을 쓸 수 있는지에 있다. HashTable에는 null 값을 key로 사용할 수 없으며, Map에서는 가능하다. 그 외에도 Thread-Safe 여부에 따라 사용성이 달라지는데, 이는 더 공부한 이후에 추가로 작성할 예정이다. 이해한 만큼만 쓰자면, 병렬 처리를 하면서 자원의 동기화를 고려할 때는 해시테이블(HashTable)을, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않을 때는 해시맵(HashMap)을 사용하면 된다.

어디서 사용하는가?

예제1. Array 값 비교하기

    public static void solution(int[] arr1, int[] arr2){
        Hashtable<Integer, Integer> ht = new Hashtable<>();
        for (int i = 0; i < arr1.length; i++) {
            ht.put(arr1[i],arr1[i]);
        }

        for (int i = 0; i < arr2.length; i++) {
            if (ht.containsKey(arr2[i])){
                System.out.print("True ");
            } else {
                System.out.print("False ");
            }
        }
    }

HashTable에 arr1의 데이터를 저장한 후, for문을 통해 arr2에 arr1과 같은 값이 있는지를 containsKey()를 통해 확인한다.

예제2. 숫자 조합하기

    public static int[] targetCheck(int[] numbers, int target){
        int[] result = new int[2];
        Hashtable<Integer, Integer> ht = new Hashtable<>();

        for (int i = 0; i < numbers.length; i++){
            if (ht.containsKey(numbers[i])){
                result[0] = ht.get(numbers[i]);
                result[1] = i;
                return result;
            }
            ht.put(target - numbers[i], i);
        }
        return null;
    }

1. HashTable에 target - 처음 숫자 값을 키로 저장한다.
2. 만약 키 값과 일치하는 숫자를 찾는다면, 그 숫자와 함께 HashTable에 저장했었던 처음 숫자 값의 인덱스를 같이 반환한다.
   이를 통해 O(n)으로 문제를 해결할 수 있게 된다.