This is the 2nd iteration of a code review. The 1st iteration (completed) is at
Iter 1: Reusable, robust c++ std::hash<mpz_class> for GMP’s big integer type
1. Goal
My intention is to provide a fast hashing algorithm to hash GMP’s big integer type mpz_class and mpz_t so I can use these types as keys for an unordered_map. The code shall be reusable for others.
2. Current Approach
string_view is used to wrap the data of the big integer’s absolute value. Since C++17, the standard library provides the specialization hash<string_view> which is used to produce the initial hash value. If the big integer is negative, the initial hash value is scambled once to produce different hash values for positive and for negative big integers of the same magnitude.
3. Code
File hash_mpz.h:
#ifndef HASH_MPZ_H_
#define HASH_MPZ_H_
#include <gmpxx.h>
namespace std {
template<> struct hash<mpz_srcptr> {
size_t operator()(const mpz_srcptr x) const;
};
template<> struct hash<mpz_t> {
size_t operator()(const mpz_t x) const;
};
template<> struct hash<mpz_class> {
size_t operator()(const mpz_class &x) const;
};
}
#endif /* HASH_MPZ_H_ */
File hash_mpz.cpp:
#include "hash_mpz.h"
#include <cstddef>
#include <string_view>
constexpr size_t pi_size_t() {
if (sizeof(size_t) == 4) {
return 0xc90fdaa2; // floor(pi/4 * 2^32)
} else if (sizeof(size_t) == 8) {
return 0xc90fdaa22168c234; // floor(pi/4 * 2^64)
} else {
throw std::logic_error(
"current sizeof(size_t) not supported. only 32 or 64 bits are supported.");
}
}
inline size_t scramble(size_t v) {
return v ^ (pi_size_t() + (v << 6) + (v >> 2));
}
namespace std {
size_t std::hash<mpz_srcptr>::operator()(const mpz_srcptr x) const {
string_view view { reinterpret_cast<char*>(x->_mp_d), abs(x->_mp_size)
* sizeof(mp_limb_t) };
size_t result = hash<string_view> { }(view);
// produce different hashes for negative x
if (x->_mp_size < 0) {
result = scramble(result);
}
return result;
}
size_t hash<mpz_t>::operator()(const mpz_t x) const {
return hash<mpz_srcptr> { }(static_cast<mpz_srcptr>(x));
}
size_t hash<mpz_class>::operator()(const mpz_class &x) const {
return hash<mpz_srcptr> { }(x.get_mpz_t());
}
}
File main.cpp:
#include <iostream>
#include <gmpxx.h>
#include <unordered_map>
#include "hash_mpz.h"
using namespace std;
int main() {
mpz_class a;
mpz_ui_pow_ui(a.get_mpz_t(), 168, 16);
cout << "a : " << a << endl;
cout << "hash( a): " << (hash<mpz_class> { }(a)) << endl;
cout << "hash(-a): " << (hash<mpz_class> { }(-a)) << endl;
unordered_map<mpz_class, int> map;
map(a) = 2;
cout << "map(a) : " << map(a) << endl;
return 0;
}
4. Question
Is there anything which can benefit from further improvement?
