해시 함수 및 작동 방법

Question

그래서 두 개의 다른 필드 유형 인 char * 길이 n 및 int 있습니다. 둘 다 키로 사용하여 hashvalue를 생성하고 싶습니다. int 변수의 마지막 16 비트를 더하고 sum x를 호출 한 다음 collate : hash를 사용하여 char *에 대한 hashvalue를 생성합니다. 정수 y라고 부릅니다. 그런 다음 x + y를 더한 다음 합계와 함께 해시를 사용하여 해시 값을 생성합니다. 내가 해시 값을 [1,4]의 범위로 제한하고 싶다고하자. 내가 원하는 것을 얻기 위해 단지 hashvalue % 4 할 수 있습니까? 또한 두 개의 키에서 해시 값을 생성하는 더 좋은 방법이 있다면 알려주십시오.

Answer 1

범위 [1,4]의 경우 hashvalue%4에 1을 더해야합니다. 그러나 4의 해시는 매우 작은 해시입니다. 그게 당신에게 충돌을 많이 줄 것이다, 해시의 효과를 제한 (즉, 많은 필드의 값이이되면 동일한 해시 값을 갖게됩니다.)

더 많은 크기 (비트)를 추가하는 것이 좋습니다. 해시, 아마도 64K (16 비트 해시). 그러면 충돌이 줄어 듭니다. 또한 이미 해시 테이블을 구현하는 std::unordered_map을 사용하지 않으시겠습니까?

마지막으로 해싱 기능에 따라 각 필드의 의미에 따라 다릅니다. 예를 들어, 구현에서 정수의 하위 16 비트 만 계산하면 해시는 해당 비트를 기반으로해야합니다. 문자열과 정수에 대한 일반적인 해싱 함수가 있기 때문에 이들 중 하나를 사용할 수 있습니다. 마지막으로, 두 필드의 해시 값을 합치려면 합계 (또는 xor-ing)하는 것이 일반적인 방법입니다. 생성 된 해시 값이 가능한 한 범위에서 똑같이 퍼지도록하십시오. 당신은 많은 단어에서 무엇을 설명 그래서

Answer 2

는 기록 : 데이터에 따라

struct noname { 
    int ifield; 
    char[N] cfield; 
}; 

int hash(const noname &n) { 
    int x = n.ifield; 
    int y = ???(n.cfield); 
    return x + y; 
    // return (x + y) & 3; 
} 

이 해시 함수가 잘되어 있는지 여부를 확인합니다. 예를 들어, ifield이 항상 4의 배수이면 명확하지 않습니다. 필드 값이 대략 고르게 분포되면 모든 것이 정상입니다.

해시 범위를 [1;4]으로 제한해야한다는 요구 사항을 제외하고는. 첫째, [0;3]은 계산하기가 쉽습니다. 둘째, 해시 코드가 생성 될 2 ~ 3 가지 항목 만 있으면 작은 범위가 적합합니다. 범위는 예상되는 다른 요소의 수의 두 배 이상이어야합니다.