내 해시 알고리즘을 개선하는 방법

stper** pages; 
int tableSize;  
struct Person{ 

    string name; 
    int age;  
    string homeTown; 
}; 


void fonk1 (int numberOfBuckets) 
{ 
    pages = new stper*[numberOfBuckets](); 
    tableSize = numberOfBuckets; 
} 

    int hashPerson(Person& person) 
    { 
    int hashVal = 0; 
    for (int i=0; i < (person.getName()).length() ; i++) 
     hashVal = 37*hashVal + (person.getName())[i]; 

    for (int i=0; i < (person.getHomeTown()).length() ; i++) 
     hashVal = 37*hashVal + (person.getHomeTown())[i]; 
    hashVal+= person.getAge(); 

    hashVal %= tableSize; 
    if(hashVal < 0) 
     hashVal += tableSize; 
    return hashVal; 
    }

안녕하세요 여러분, 저는 해시에 새로운 사람입니다. 내 해싱 함수는 위의 hashPerson 함수에 있으며 세 개의 키가 있다는 것을 알 수 있습니다. 내 함수는 해시를위한 좋은 알고리즘이며 어떻게 함수를 개선하고 충돌 수를 줄일 수 있습니까? 나는 몇 가지 제안을내 해시 알고리즘을 개선하는 방법

출처

2013-01-05 peaceman

지금까지 해시 함수에 어떤 문제가 있습니까? 당신이 그것을 바꿀 필요가 있다고 의심할만한 이유가 있습니까? – templatetypedef

해시 함수가 좋습니다. 하지만 당신은 C++을 사용하고 있는데 왜 stl을 사용하지 않습니까? –

나는 그것을 향상시킬 수 있는지 알고 싶어하고 좋은 기능인지 아닌지 잘 모른다. – peaceman

(구문 실수가있을 경우 무시하십시오) :

사용 unsigned 대신 int을. 내 경험상 이것은 부호없는 오버플로가 발생할 때와 같이 성능이 뛰어남을 입증 했으므로 여전히 음수가 아닙니다 (그렇지 않으면 %가 큰 문제로 이어질 수 있습니다 - 음수 인덱스가 나오고 충돌이 발생 함). 감소 된 충돌 속도 (경험적으로 입증 됨). 또한 모든 함수가 테이블에서 인덱스를 반환해야하므로 값이 부호가없는 것이 자연 스럽습니다. 인덱스는 음수 일 수 없습니다.
연령을 추가 할 때 hashVal에 무언가를 곱하십시오. 예를 들어 200보다 큰 값을 제안 할 것입니다.
tableSize은 절대로 말하지 않습니다. 충돌 비율을 줄이기 위해 큰 소수 (가능한 한 큰)를 사용하는 것이 좋습니다.

출처

2013-01-05 21:25:09

std::hash을 사용하면 기본 구성 요소의 양호한 해시 값을 생성 할 수 있습니다. 몇 가지 예와 설명을 찾을 수 있습니다 here.

부스트 버전이 설치된 경우 boost::hash_combine에서 필요한 것을 수행 할 수 있습니다. 당신은 좋은 샘플 here으로 부스트의 문서를 찾을 수 있습니다.

출처

2013-01-05 23:06:27

내 해시 알고리즘을 개선하는 방법

답변

관련 문제