0
기본 함수는 std :: hash입니다. 계산 시간을 절약하기 위해 더 나은 해시 함수가 있는지 궁금합니다. 정수 키 및 문자열 키의 경우C++에서 unordered_map/set에 대한 더 빠른 해시 함수가 있습니까?
Google에서 City Hash를 정수 및 문자열 키로 모두 시도했지만 성능이 std :: hash보다 약간 더 좋았습니다.
A
답변
2
어떤 의미에서 '더 나은'설명이 필요합니까? 가장 빠른 해시 함수는 단순히 값을 사용하지만 쓸모가 없습니다. 보다 구체적인 대답은 기억의 제약과 충돌의 가능성에 따라 달라질 수 있습니다.
또한 inbuilt 해시 함수는 다른 유형에 따라 다르게 빌드되므로 결과적으로 시간 복잡성 및 충돌 확률에 대한 일반적인 의미로 최적화하여 int 및 string의 해시 함수를 이미 예상 할 수 있습니다.
+0
내 목표는 전반적인 CPU를 줄이는 것입니다. 그래서 (1) 해시 계산 자체가 빠릅니다. (2) 충돌이 적다. 내가 올바른 길을 가고 있는지 확실하지 않습니다. – SuperBald
+0
@superbald : 질문은 왜 당신이 더 잘 할 수 있다고 생각합니까? 표준 라이브러리 함수는 가능한 최고의 라이브러리 함수를 생성하려는 매우 영리한 프로그래머가 작성했습니다. 더 잘할 수 있다면 아마도 특정 데이터 세트의 성능을 향상시킬 수있는 데이터에 대해 알고 있기 때문일 것입니다. 그러나 키를 해시하기가 더 쉬운 이유에 대한 단서를 제공하지 않았습니다. 표준 라이브러리 구현은 광범위한 데이터에서 잘 수행되어야하며, 특별한 것이 없으면 자신의 것과 잘 어울립니다. – rici
+0
STL에 있다는 것이 최선이라는 의미는 아닙니다. 예 : Google 오픈 소스 해시지도 및 트리지도 (표준보다 월등 함) 해시 함수에 대해 잘 모르겠습니다. 그래서이 질문을했습니다. – SuperBald
4
std :: hash 함수는 이미 성능이 우수합니다. 오픈 소스 해시 함수를 사용해보아야한다고 생각합니다.
이것을 확인하십시오. https://github.com/Cyan4973/xxHash. "xxHash는 RAM 속도 제한에서 실행되는 매우 빠른 해시 알고리즘으로, 해시 함수의 충돌, 분산 및 임의성 품질을 평가하는 SMHasher 테스트를 성공적으로 완료합니다. 코드는 이동성이 뛰어나며 해시도 동일합니다. 모든 플랫폼 (리틀/빅 엔디안). "
이 사이트의 다른 질문에서이 스레드도 Fast Cross-Platform C/C++ Hashing Library입니다. FNV, Jenkins 및 MurmurHash는 빠르다고 알려져 있습니다.
일반적으로 해싱중인 데이터에 대한 구체적인 정보를 알고있는 경우 더 빠른 해시 함수를 작성할 수 있습니다. 바보 같은 예로서, 17과 535의 두 정수 값만 다루는 경우 0과 1을 쉽게 해시 할 수 있습니다. 정수 값의 전체 범위를 처리하는 해시 함수보다 빠릅니다. 그래서 당신이 해싱하는 가치에 대해 특별한 것은 무엇입니까? –
문제가 해결되면 문제를 해결하는 것이 항상 좋은 생각입니다 :) –