특정 시나리오에 대한 빠른 해시 함수

Question

해시 테이블 조회에 사용하기 위해 빠른 해시 함수를 찾고 있습니다. 입력은 재귀 양식 f (x, y)의 표현식으로 구성됩니다. 여기서 x와 y는 두 개의 인수 또는 변수가있는 함수가 될 수 있습니다. 몇 가지 예 :

• B (b (b (b, b), b), b)
• foo에 (바, 바)
• A (A (A, a)는 (a (a, a), a))

이 표현식은 최대 200.000 자까지 입력 할 수 있지만 수천 개의 표현식을 동일한 테이블에 해시해야합니다.

입력 내용은 표현식의 처음 10 자와 전체 표현식의 길이로만 구성됩니다. A, B 및 C는 각각 541, 733 및 941입니다. 이 알고리즘은 몇 가지 최악의 경우 (첫 번째 예제와 같이 길고 반복적 인 중첩 루프)에 대해 100ms 미만으로 실행되지만 많은 충돌이 발생하고 O (1) 검색에 더 가까워 질 수 있는지 알고 싶습니다 이 경우에도 마찬가지입니다.

Answer 1

이 시도 :

uint32_t hash(const string &s, uint32_t n) { 
    uint32_t step = 1 | (s.size() >> 4); // ~16 iters 
    uint32_t h = 0x1F351F35; // Barker code - 2 
    for(uint32_t i = 0; i < s.size(); i += step + (h & step)) 
    h = ((h << 5) | (h >> (32 - 5))) + (s[i]^n^i); 
    return h % C; 
}