13. Hash tables

1. Hash function

 

Key에 순서가 있는 경우, BST에 넣어서 Symbol table을 구현할 수 있었다. 

만약 Key에 순서가 없는 경우 Hash table을 이용하면 logarithm time이 아닌 constant time에 search가 가능하다.

 

hash table의 기본적인 아이디어는, key에 hash function을 적용한 값이 배열의 Index가 되도록 하는 것이다.

이렇게 된다면 우리는 key에 단순히 hash function으로 연산을 하거나, 그 값을 cache에 저장시켜놓고 사용함으로서. 배열의 임의의 요소의 접근시간은 constant time이므로 빠른 searching이 가능하다.

하지만, 한가지 문제는 (key, value)쌍의 갯수보다 배열의 공간이 작을 경우, 또는 서로 다른 key에 대해 hash function을 적용했음에도 동일한 hash value가 나오는 경우, 이런 경우에  서로 다른 key가 동일한 배열 index를 가리키게 되는 문제점이 발생한다. 이를 hash collision이라고 한다. collision이 자주 발생할 경우, search/insert 시간이 길어지고, constant time을 보장할 수 없게 된다.

 

이상적으로 hash function은 계산가능한 시간내에 효율적으로 계산할 수 있는 함수여야 한다. 그리고 각각의 key에 대해 hash function을 사용했을 때 배열에 index들에 균등하게 분배되어야 한다. 이 때, 충돌은 input갯수에 비해 매우 큰 index로 설정하지 않는 이상 통계적으로 피하는것이 어렵다(Birthday problem)

또한, key type에 따라 다른 hash전략이 사용되어야 한다.

 

Java의 모든 class는 32bit int를 return하는 hashCode() 함수를 상속받는다. hash code는 실제로 hash function이 적용되는 값이다. hashCode()함수의 한가지 요구사항은, 만약, x와 y가 같다면, x의 hashcode와 y의 hashcode가 같아야 한다는 점이다. 객체마다 서로 다른 방식으로 hash function을 구현할 수 있다.  Integer, Double, String 등은 모두 다른 방식으로 hashCode()를 구현한다.

Java에서는 서로 다른 두 Integer wapper 객체의 Interger.value가 같을 때 서로 같은 것으로 취급하므로, hashCode()는 메모리 주소가 아닌, 단순히 32bit int형식의 값을 리턴하도록 함으로서 구현할 수 있다.

 

String의 경우 hashCode()는 java에서 아래와 같이 구현된다.

이것은 Horner's method인데, 현재 hash값에  31을 곱하고 문자의 unicode값을 더해 새로운 hash값을 만드는 과정을 문자별로 반복하여 최종값을 얻는다. 수식으로는 아래와 같다

(만약 중간에 요소를 skip하면서 계산할 경우, 계산과정이 감소되어 실행시간이 감소하지만, 충돌 가능성은 더 높아진다!)

 

public int hashCode(){
	int hash = 0;
    for (int i = 0; i < length(); i++)
    	hash = s[i] + (31 * hash) //  s는 char[] 문자열
    return hash;
}

 

user-defined type의 경우에도 비슷한 방법을 사용해서 hashCode()를 구현할 수 있다.

31x + y rule이란 건데, 다음 hash = (현재 hash*31 + 한 필드의 hash code) 를 반복한다.

primitive type의 경우 wrapper를 활용한다.

 

public final class Transaction implements Comparable<Transaction>{
	
    private final String who;
    private final Date when;
    private final double amount;
    
    ...
    
    public int hashCode(){
    	int hash = 17; 
        hash = 31*hash + who.hashCode();
        hash = 31*hash + when.hashCode();
        hash = 31*hash + ((Double)amount).hashCode(); //wrapper type 이용
        return hash;
    }
}

 

31을 선택하는 이유는 31이 꽤나 작은 소수(prime number)이기 때문이다. 큰 수를 선택하면 계산시간이 오래걸리고 값이 너무 커지는 문제가 있고, 소수를 선택할 경우 hash function 적용시에 collision이 최소화 된다.

 

hash code는 32bit int이므로, -2^32 ~ 2^31-1 사이의 값이다.

hash function중 대표적인것은 Modular hash function인데, 이것은 M으로 나눈 후 나머지 값을 index로 얻는다.

따라서 hash function의 값은 0 ~ M-1 사이이다. 그렇다면 음수 hash code에 modular연산을 하면 어떻게 될까? 바로 음수가 나온다. 하지만, 배열의 index는 양수이다. 따라서 modular연산 이전에 양수가 됨을 보장하기 위해서  아래와 같이 최상위 bit를 0으로 만들어주는 bitwise연산을 수행할 수 있다. 물론 1111..., 0111...  값은 서로 collision이 발생할 것이다.

 

private int hash(key key)
{ return (key.hashCode() & 0x7ffffffff) % M; }

 

 2) Separating chaining

 

collision에 대한 하나의 대응책으로 separating chaining이 있다. 이것은 배열의 요소가 linked list를 가리키도록 하고, collision이 발생할 때마다 chaining방식으로 linked list에 key, value쌍을 추가시켜가는 방식이다.

 

search/insert 시간은 N/M에 비례한다(N은 key갯수) 보통 M ~ N/5 정도로 잡게되면, 평균적으로 하나의 index당 길이 5의 linked list가 존재하게 되므로, constant time을 보장할 수 있게 된다. 

 

3) Linear probling

 

collision에 대한 또 다른 대응책으로는 linear probing이 있다.

hash function으로 index에 값을 넣고, 채워져있을 경우 한칸씩 계속 빈공간이 있을 때까지 index를 증가시켜가며 insert할 공간을 찾는다. 검색의 경우도 해당 index에 값이 없을 경우 index를 증가시켜가며 존재하는 곳을 찾는다.

 

한가지 문제점은 배열의 공간이 거의 다 찼을 경우, search/insert의 시간이 급격하게 증가한다는 것이다. 보통 key의 갯수 N의 2배를 M의 값으로 설정한다. M이 너무 크면 공간을 낭비하게 되고, 너무 작으면 search/insert time이 급격히 증가한다.

 

M의 값만 적절하게 선택된다면, linear probling은 pointer를 사용하지 않고 array만 사용하므로 보통은 separating chaining에 비해 적은 공간을 사용하며, 공간참조성에 의해 더 빠른 성능을 보여준다. 또한, 메모리 공간이 제한된 경우 동적공간할당인 malloc의 실패를 걱정할 필요가 없다. 하지만 data clustering에 민감하고 hash function의 collision이 자주발생할 경우, 주변의 인접한 index에도 영향을 미치게 된다.

 

4) 추가

 

Hash function의 균등한 배분은 성능을 보장하기 위해서 중요하다. 만약 그렇지 못한 hash function이 노출될 경우 악의적인 공격자가 의도적으로 collision이 발생하도록 값을 계속 집어넣어서 검색을 느리게 만드는 DOS공격을 할 수 있다.

 

one-way hash function은 hash value를 알아도 key를 찾기가 어려운 hash function을 의미하며, 안전한 것을 사용해야 한다. 지문, 비밀번호등을 저장하기 위해 사용한다. 예를 들어, 비밀번호를 입력하면 hash function을 거친 후, DB의 hash value와 비교하여 동일하면 로그인된다.

 

기존의 separating chaning, linear probing을 개선한 two-probe hashing, double hashing, cuckoo hashing 등이 있다. 더 복잡하지만 개선된 버전들이다. 

 

Hash table은 constans time을 보장한다. 하지만 언제나 Balanced search trees보다 hash table을 사용하는 것이 좋은 것은 아니다. Balanced search tree는 hash table보다 더 강한 성능 보장을 제공한다. 또한, equals()나 hashCode()를 구현하는 것보다 compareTo()를 구현하는 것이 더 쉽고, 순서를 사용하는 연산이 경우에는 Balanced search tree가 적합하다.