해시테이블_충돌

1. 충돌

해시테이블을 구현 할 때 주로 해결해야 할 문제가 충돌문제.

나머지를 구하는 해싱의 경우, 키가 14와 10,564이면 나머지가 4로 충돌한다.

충돌을 해소하려면 해시함수를 사용하거나 충돌이 문제되지 않는 방식으로 테이블을 수정해야한다.

(1.개별자리수 더하기, 2.문자열의 해싱)

2. 해시함수

1)개별 자리수 더하기: 간단한 해시함수는 각 자리를 모두 더하는것.

ex) 143,674와 645,394 

1+4+3+6+7+4 = 25

6+4+5+3+9+4 = 31

->충돌이 발생하지는 않지만 배열의 크기 10을 넘어간다.

해결방법

(1)배열의 크기를 54로 하는것(6자리:9+9+9+9+9+9+)

(2)이중해싱으로 키 값을 특정한 방법으로 해싱을 하고 그 해싱된 값을 한번 더 해싱

!-> 개별자리수 더하기 역시 충돌이 발생한다.

2)

문자열 해싱: 정수 이외에 문자열도 키로 많이 쓰인다.

문자열을 해싱해서 하나의 정수를 얻는 알고리즘, 충돌이 매우 적게 일어난다.

ex)

unsigned long int StringHash(const char* p_string){
    unsigned long int hash = 0;
    int i;
    int length = strlen(p_string);
    for(i = 0; i<length; i++){
        hash += ((i+1)* p_string[i]);}
    return hash;
}

이 방법은 문자열 안의 문자가 본질적으로 정수라는 사실에 기반한 것.

한 문자가 0~255 사이의 정수이며, 문자열은 그러한 정수들의 수열이라고 할 수 있다.

이 함수는 자릿수 더하기와 비슷하지만 수자들을 그냥 더하는게 아니라 숫자에 현재 색인을 곱한 값을

더한다.

문자열 "Hello!" -> 72, 101, 108, 108, 111, 33

(72*1)+ (101*2)+(108*3) ...

이렇게 얻은 값을 키로 사용해도 되고 한 번더 해싱해도 된다.

색인을 곱해 줌으로써 같은 글자들이러달도 순서가 다르면 완전히 다른 해시값을 얻을 수 있다.

2016.10.18. 19:27