Re: Good hash for pointers

Bonita Montero <Bonita.Montero@gmail.com> writes:

This shows the perfect equal distribution if I take a 32 bit integer
and multiply it by the largest 32 bit prime:

There was no need to write this program.  It just illustrates a specific
example of a basic theorem where the multiplier and modulus are
co-prime.

#include <iostream>
#include <vector>
#include <random>
>
using namespace std;
>
int main()
{
vector<uint8_t> buckets( 1ull << 32 );
for( size_t b = buckets.size(); b; )
if( !++buckets[(uint32_t)--b * 0xFFFFFFFBu % buckets.size()] )
return EXIT_FAILURE;
vector<size_t> loads;
for( uint8_t ld : buckets )
{
if( loads.size() <= ld )
loads.resize( ld + 1 );
++loads[ld];
}
for( size_t l = 0; size_t ld : loads )
cout << l++ << ": " << 100.0 * (ptrdiff_t)ld /
(ptrdiff_t)buckets.size() << "%" << endl;
}
>
>
Result:
>
0: 0%
1: 100%
>

--
Ben.