Skip to content

Instantly share code, notes, and snippets.

@metopa
Created January 30, 2016 15:10
Show Gist options
  • Save metopa/7703a7a51a2b33ee1966 to your computer and use it in GitHub Desktop.
Save metopa/7703a7a51a2b33ee1966 to your computer and use it in GitHub Desktop.
#include <cstdint>
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using std::vector;
using std::function;
using std::cout;
using std::endl;
using std::min_element;
using std::max_element;
using std::accumulate;
uint64_t hash( int a, int b, int c) {
return (uint64_t) ( a ^ ( b * 1021) ^ ( c * 1048573) );
}
template <class HashFunc>
void test( size_t tableSize, int loopCount, HashFunc hashFunc ) {
vector<int> table( tableSize, 0);
for ( int a = 0; a < loopCount; a++ )
for ( int b = 0; b < loopCount; b++ )
for ( int c = 0;c < loopCount; c++ )
table[hashFunc( a, b, c ) % tableSize]++;
cout << "Test for " << tableSize << " N and " << loopCount * loopCount * loopCount << " loops" << endl;
cout << "Max collisions: " << *max_element( table.begin(), table.end() ) << endl;
cout << "Min collisions: " << *min_element( table.begin(), table.end() ) << endl;
cout << "Avg collisions: " << accumulate( table.begin(), table.end(), 0 ) / (double)tableSize << endl;
}
int main() {
test( 256 * 256 * 256 / 2, 256, hash );
test( 1024, 256, hash );
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment