1
Rabin-Karp string search algorithm을 구현하는 데 사용할 수있는 좋은 해시 함수는 무엇입니까? 난 단지 다항식 해시를 알고 있지만, 가장 중요한 것은, 해싱이 모듈로 2로 수행된다면, 매우 자주 충돌을 일으킬 수있는 테스트가 있다는 것입니다 (mod 연산이 다른 모듈러를 사용하기 때문에 실용적이지 않습니다). 매우 비싼). 그래서, 빠르고, 쓰기 쉬운 좋은 해시 함수는 무엇입니까?Rabin-Karp 문자열 검색 알고리즘에 적합한 해시 함수 찾기
P. 내가 buzhash에 대해 알고 있지만 다른 대안이 있는지 궁금해하고 있습니다 ...
mod (%)는 비싸지 않습니다. 그것은 1980 년대 비싸기 위해 사용되었습니다. 질문 : 왜 해시 함수가 * 빠름 *일까요? – wildplasser
BTW : 모듈로 (1 << 64)는 확실히 비싸지 않습니다. 64 비트 * 부호없는 * 유형을 사용하는 경우 * 고맙습니다 *. – wildplasser
@wildplasser 특정 테스트에 대한 그의 의견은이 질문이 프로그래밍 방식의 관점에서 요구된다는 것을 암시하는 듯하다. 모듈 식 1 << 64는 비실용적이다. http://codeforces.com/blog/entry/4898 – ffao