해시 테이블로 매우 빠른 룩업

유방현·2022년 9월 14일

자료구조와 알고리즘

목록 보기

8/17

menu = new Map([["french fries", 0.75], ["hamburger", 2.5], ["hot dog", 1.5], ["soda", 0.6]]);

배열이 정렬되어 있지 않다면 선형 검색, 정렬 되어 있다면 이진 검색을 수행 할 수있다. 하지만 이보다 더욱 빠르게 배열을 검색 할 수 있다. 바로 해시테이블을 사용하는 방법이다. 해시 테이블의 효율성은 O(1)이다.

해시 테이블

Hashtable<String,Double> ht = new Hashtable<>();
ht.put("french fries",0.75);
System.out.println(ht.get("french fries"));
해시 테이블은 키,값 쌍으로 이루어진 리스트이다. 첫 번째 항목을 키라고 부르고, 두 번째 항목을 값이라 부른다. 위 코드는 자바로 만들었다.
해시 테이블의 검색은 단 한단계만 걸리므로 효율성은 O(1)이다.

해시 함수로 해싱

A=1, B=2, C=3 ... 이라는 비밀 코드를 만든다고 가정하자. 가령, BAD는 214로 변환된다.
위 과정에서, 문자를 가져와 숫자로 변환하는 과정을 해싱이라 부른다.
글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수라 부른다.

해시 함수는 이밖에도 많다. 비밀 코드로 문자를 숫자로 변환해 모든 숫자를 합치거나 곱해서 반환할 수도 있다. BAD의 예시에서 합치면 7이 될 것이고, 곱하면 8이 될 것이다.

해시 함수가 유효하려면, 동일한 문자열을 해시 함수에 적용할 때마다 동일한 숫자로 변환돼야 한다.
그런 점에서 현재 시간이나 난수를 사용하는 해시 함수는 유효하지 않다. 적용할 때마다 다른 결과가 나올 것이기 때문이다.
곱셈 해시 함수를 스면 BAD는 항상 8이다. 단, DAB 역시 8이 될 수도 있다는 점을 유의해야 한다.

재미와 이익, 특히 이익을 남길 유의어 사전 만들기

        Hashtable<String, String> ht2 = new Hashtable<>();
        ht2.put("bad","evil");
        ht2.put("cab","taxi");
        ht2.put("ace","star");
위와 같은 자바 코드가 있다. 이 때 곱셈 해시 함수를 적용한다면 어떻게 동작할까??
1. 우선 bad = 2 1 4 = 8로 해싱되므로, 컴퓨터는 값 "evil"을 셀 8에 넣는다.
2. cab = 6에 해싱되고 "taxi"를 셀 6에 넣는다.
3. ace는 15에 해싱되고 컴퓨터는 "star"를 셀 15에 넣는다.

해시 테이블 룩업

ht2.get("bad");
위와 같은 자바 코드에서 어떻게 해시 테이블에서 값을 검색 하는지 보자.

1. 컴퓨터는 룩업하는 있는 키를 해싱한다. bad = 8
2. 결과가 8이므로 셀 8을 찾아가서 값을 반환한다. 여기서 값은 "evil"이다.

해시 테이블에서 값을 룩업 하는 과정을 확인했다. 이를 통해 키가 값의 위치를 결정한다는 걸 알수 있다.
즉, 키 자체로 값을 어디서 찾을 수 있는지 알 수 있다. 키를 해싱해서 이전에 값을 넣었던 곳을 찾을 수 있기 때문이다.
키를 해싱하는 과정은 상수 시간이 걸릴 것이므로, 해시 테이블의 값 룩업은 O(1) 이다.
배열에서 메뉴 항목의 값을 룩업하려면 항목을 찾을 때까지 각 셀을 순회해야 한다.
정렬되지 않은 배열이라면 최대 O(N)이고, 정렬된 배열이라면 최대 O(logN)이 걸린다.
해시 테이블이라면 메뉴 항목을 키로 해서 O(1)만에 할 수 있다.

단방향 룩업

해시 테이블에서 키를 모른채 값을 찾으려면 O(N)이다. 키를 모르면 모든 해시 테이블을 검색 하는 방법 말고는 없다.
같은 원리로 해시 테이블은 키를 사용해서 값을 찾을 때만 O(1)이다. 해시 테이블은 키는 중복 될 수 없지만, 값은 중복 될 수 있다.
즉, 해시 테이블의 빠른 룩업은 키→값의 단방향으로만 동작한다.

충돌 해결

해시 테이블에서 곱셈 해시 함수를 사용 할 때 똑같은 셀에 값을 추가하는 경우가 생길 수 있다. 이 때 해시 테이블이 어떻게 동작 하는지 알아 보자.
위에서 자바로 만든 해시 테이블에 ht2.put("dab","pat")란 명령을 내리게 되면,dab = 8이므로 컴퓨터는 8번 셀이 "pat" 추가하려 한다. 하지만 우리는 이미 bad = 8,evil 값을 가지고 있다.
이러한 충돌을 해결하는 고전적인 방법 하나가 분리 연결법이다. 충돌이 발생했을때, 컴퓨터는 기존 셀에 하나의 값을 넣는 대신 배열로의 참조를 넣는다. 이 경우 ["bad","evil"]을 { ["bad", "evil"], ["dab", "pat"] }로 대체한다. 각 하위 배열의 인덱스 0은 키, 인덱스 1은 값이다.

이렇게 값이 바뀌었을 경우 해시 테이블에서 값을 어떻게 불러 올 수 있을까??
만약 컴퓨터가 ht2.get("dab","pat")이라는 명령을 받는다면 이러한 단계를 따른다.

1. 컴퓨터는 키를 해싱한다 dab = 8
2. 셀 8을 룩업한다. 컴퓨터는 셀 8이 하나의 값이 아닌 배열을 포함하고 있음을 알게 된다.
3. 각 하위 배열의 인덱스 0을 찾다보며 룩업하고 있는 단어인"dab"을 찾을 때까지 배열을 차례대로 검색한다. 일치하는 하위 배열의 인덱스 1에 있는 값을 반환한다.

만약 모든 데이터가 해시 테이블의 한 셀에 들어가게 된다면 해시 테이블은 배열보다 비슷하게 동작한다. 따라서 최악의 경우 해시 테이블 룩업 성능은 사실상 O(N)이다.
이렇기 때문에 우리는 해시 테이블에 충돌이 거의 없도록, O(1) 시간 내에 룩업을 수행하도록 디자인 해야한다.

효율적인 해시 테이블 만들기

해시 테이블의 효율성의 세 요인
1. 얼마나 많은 데이터를 저장하는가
2. 얼마나 많은 셀을 사용 할 수 있는가
3. 어떤 해시 함수를 사용하는가?

적은 셀에 많은 데이터를 저장하면 충돌이 많이 발생 할 수 밖에 없다. 그렇기에 해쉬 테이블 효율성은 떨어질 것이다.
그렇다면 어떻게 해시 함수가 해시 테이블에 여향을 미칠 수 있을까???
해시 테이블에 16개의 셀이 할당 되었고 이러한 해시 함수를 사용한다고 가정하자.
put = 16 + 21 + 20 = 57 -> 5 + 7 = 12 -> 1 + 2 -> 3
이 경우 키를 해싱할 경우 1~9 사이의 값을 반환한다. 그렇다면 나머지 셀인 10~16이 낭비되는 것이다.
따라서 좋은 해시 함수란 모든 셀에 데이터를 분산 시키는 함수다. 데이터를 넓게 퍼트릴 수록 충돌이 적어진다.

훌륭한 충돌 조정

이론상 충돌을 피하는 최선의 방법은 해시 테이블에 많은 셀을 두는 것이다. 하지만 데이터 5개를 저장하겠다고 셀 1000개를 사용하는 것은 메모리 낭비다.

좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.

저장할 데이터와 저장 가능한 셀의 비율을 부하율이라고 하며, 이상적인 부하율은 0.7이다.

해시 테이블 내부는 대부분 사용자가 쓰고 있는 컴퓨터 언어가 관리한다. 프로그래밍 언어가 최고의 성능을 내도록 해시 테이블을 구현했다고 가정해도 무방하다.

해시 테이블로 데이터 조직

정치 후부자와 각 득표수 같은 집계 데이터 역시 쌍으로 되어 있기 때문에 해시 테이블을 사용한다면 효율성을 높일 수 있다.
해시 테이블로 조건로 로직도 간소화 할 수 있도 있다.
일반적인 HTTP 상태 코드 번호의 의미를 반환하는 코드가 있다가 하자
    public static String statusCodeMeaning(int number){
        if(number == 200) return "OK";
        else if(number == 301) return "Moved Permanently";
        else if(number == 401) return "Unauthorized";
        else if(number == 404) return "Not found";
        else if(number == 500) return "Internal Server Error";
        return null;
    }
위 코드를 해시 테이블을 사용하면 다음과 같이 조건부 로직을 완벽히 없앨 수 있다.
   public static String statusCodeMeaning(int number){
        Hashtable<Integer,String> statusCodes = new Hashtable<>();
        statusCodes.put(200,"OK");
        statusCodes.put(301,"Moved Permanently");
        statusCodes.put(401,"Unauthorized");
        statusCodes.put(404,"Not found");
        statusCodes.put(500,"Internal Server Error");
        return statusCodes.get(number);
    }
또한 해시 테이블은 다양한 속성을 갖는 객체를 표현할 때도 흔히 쓰인다. 예를 들어 개를 표현하는 해시 테이블이 있다면, 배열 안에 여러 해시 테이블을 넣음 으로써 개 목록을 만들 수 있다.
        Hashtable<String,String>[] arr = new Hashtable[20];
        arr[0] = new Hashtable();
        arr[0].put("Name","Fido");

해시 테이블로 속도 올리기

arr = [11,72,33]와 같은 정리 되지 않은 배열이 있다. 여기서 72라는 값을 찾으려면, 선형 검색의 단계인 O(N)이다. 하지만 해시 테이블로 구현 한다면 단 한 단계만의 값을 찾을 수 있다.
        Hashtable<Integer, Boolean> numbers = new Hashtable<>();
        numbers.put(11,true);
        numbers.put(72,true);
        numbers.put(33,true);
        numbers.get(72);
위와 같은 코드를 사용한다면 단 한 단계만에 해시 테이블에 해당하는 숫자가 들어 있는지 확인 가능하다. 만약 다른 해시 테이블에 없는 다른 값을 찾게 되면 null을 반환한다.

배열 부분 집합

예를 들어 ["a","b","c","d","e","f"] 와 배열 ["b","d","f","h"]가 있다. 이 때 두번 째 배열의 b,d,f는 첫 번째 배열에 부분 집합에 해당한다. 하지만 f는 아니므로 두 번째 배열은 첫 번째 배열의 부분 집합이 아니다. 이러한 기능을 하는 코드를 배열과 해시 테이블로 작성해 보고 효율성을 생각해보자.

    public static boolean isSubset(char[] arr, char[] arr2){
        char[] large;
        char[] small;
        if(arr.length > arr2.length){
            large = new char[arr.length];
            small = new char[arr2.length];
        }
        else {
            large = new char[arr2.length];
            small = new char[arr.length];
        }
        for(int i = 0; i < small.length; i++){
            Boolean found = false;
            for (int j = 0; j < large.length; j++){
                if(small[i] == large[j]){
                    found = true;
                    break;
                }
            }
            if(!found) return false;
        }
        return true;
    }

다음과 같은 O(N * M)인 코드를 해시 테이블을 사용하면 좀 더 효율성을 올릴 수 있다.

    public static boolean isSubset2(char[] arr, char[] arr2){
        Hashtable<Character,Boolean> hashtable = new Hashtable<>();
        char[] large;
        char[] small;
        if(arr.length > arr2.length){
            large = new char[arr.length];
            small = new char[arr2.length];
        }
        else {
            large = new char[arr2.length];
            small = new char[arr.length];
        }
        for(int i = 0; i < large.length; i++){
            hashtable.put(large[i],true);
        }
        for(int i = 0; i < small.length; i++){
            if(hashtable.get(small[i])) return false;
        }
        return true;
    }

위 코드는 O(N) 효율성을 가지고 있다.

해시 테이블을 인덱스로 사용하는 이 기법은 배열을 여러 번 검색해야 하는 알고리즘에서 자주 쓰인다. 알고리즘에서배열의 값을 계속 검색해야 한다면 매 검색에만 최대 N단계씩 걸리기 때문이다. 키로 해시 테이블을 룩업해서 어떤 값이든 받으면 그 키가 해시 테이블에 있다는 뜻이다.