정렬 된 숫자 목록을 해시하려면 어떤 해시 함수를 사용해야합니까?

Question

int 키와 int 값의 맵인 유형을 고려하십시오. 키가 작은 순서로 정렬되고지도가 평면 목록 {key1, val1, key2, val2 등}으로 간주 될 수 있습니다.

나는이지도의 목록을 생성하고 동일한지도를 식별 할 수 있기를 원합니다. O (n^2) 시간보다 적습니다. 이를 달성하기 위해 각지도를 한 번 해시 할 계획입니다.

이 목적에 가장 적합한 해시 함수가 무엇인지 확신 할 수 없습니다. 내 키는 매우 큰 숫자 일 수 있지만 (여전히 int32), 값이 작을 수 있습니다. 그런 고려 사항은 부적절하다고 생각합니다. 일반적으로 숫자 시퀀스에서 잘 작동하는 해시 함수가 있기를 바랍니다.

아이디어가 있으십니까? 고맙습니다.

Answer 1

대부분의 해시 함수, 특히 암호화 해시 함수는 이진 데이터를 처리하므로 바이트 시퀀스로 표현할 수있는 모든 항목을 처리 할 수 ​​있습니다. 키의 값에 어떤 인코딩을 사용할 지 결정해야합니다.

해시 기능은 보안과 관련이 없으므로 원하는 기능 만 선택할 수 있습니다. 암호화 해시 함수는 매우 우수한 "혼합"을 제공하고 일부는 매우 빠릅니다 (CRC32와 같은 잘 알려진 비 암호화 해시 함수와 경쟁적입니다). 예 : MD4. 하지만 프로그래밍 언어 (사용하는 언어를 말하지 않은)가 이미 MD5 구현을 제공하고 있으며 이는 아직 상당히 빠른 속도입니다.