Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Hashing with Boost Hash Library #109

Open
staticassert opened this issue Dec 9, 2020 · 2 comments
Open

Hashing with Boost Hash Library #109

staticassert opened this issue Dec 9, 2020 · 2 comments

Comments

@staticassert
Copy link

staticassert commented Dec 9, 2020

Is there a method to use the boost hash library as a hash function in frozen::unordered_map?

I have been using boost::hash in std::unordered_map to work with non-integral keys. Using boost::hash in frozen::unordered_map creates error, because the pmh_table::lookup() function applies 2 parameters: key and static_cast<size_t>(first_seed_), whereas boost::hash only accepts 1 parameter. Is there a workaround for this?

@staticassert
Copy link
Author

This is the error:
function "boost::hash<T>::operator() [with T=std::__1::pair<int, int>]" cannot be called with the given argument list -- argument types are: (const std::__1::pair<int, int>, <error-type>) -- object type is: const boost::hash<std::__1::pair<int, int>> -- detected during: -- instantiation of "size_t frozen::bits::pmh_tables<M, Hasher>::lookup(const KeyType &key) const [with M=64UL, Hasher=boost::hash<std::__1::pair<int, int>>, KeyType=std::__1::pair<int, int>]" at line 120 of "/Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk/usr/include/frozen/unordered_map.h" -- instantiation of "const Value &frozen::unordered_map<Key, Value, N, Hash, KeyEqual>::at(const Key &key) const [with Key=std::__1::pair<int, int>, Value=char, N=64UL, Hash=boost::hash<std::__1::pair<int, int>>, KeyEqual=std::__1::equal_to<std::__1::pair<int, int>>]" at line 193 of "/Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk/usr/include/frozen/unordered_map.h"

@muggenhor
Copy link
Contributor

... the pmh_table::lookup() function applies 2 parameters: key and static_cast<size_t>(first_seed_), whereas boost::hash only accepts 1 parameter.
Is there a workaround for this?

No: this library completely relies on the ability to select alternate seeds in order to avoid hash collisions. To my understanding this is the whole point of a "perfect hash function": to avoid hash collisions requiring buckets that need to be searched in some different fashion (usually linearly).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants