Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- template <class T>
- inline void hash_combine(std::size_t& seed, const T& v)
- {
- std::hash<T> hasher;
- seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
- }
- seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
- #include <iostream>
- #include <functional>
- #include <stdlib.h>
- #include <map>
- #include <time.h>
- template <class T>
- inline T hash_combine(const T& a, const T& b)
- {
- std::hash<T> hasher;
- return a ^ ( hasher(b) + 0x9e3779b9 + (a<<6) + (a>>2) );
- }
- template <class T>
- inline T triple_hash(const T& a, const T& b, const T& c)
- {
- std::hash<T> hasher;
- return hash_combine(hash_combine(static_cast<T>(hasher(a)), b), c);
- }
- int main(int argc, char** argv){
- srand (time(NULL));
- std::hash<int> _hash;
- unsigned int rounds = 1000000;
- unsigned int limit = 0xFFFFFFFF;
- std::map<int, int> h1_map;
- std::map<int, int> h2_map;
- std::map<int, int> h3_map;
- std::map<int,int>::iterator h_iter;
- int h1_collis = 0;
- int h2_collis = 0;
- int h3_collis = 0;
- unsigned int a,b,c,d,h1,h2,h3;
- for(unsigned int i = 0; i < rounds; ++i) {
- a = rand() % limit + 1;
- b = rand() % limit + 1;
- c = rand() % limit + 1;
- d = rand() % limit + 1;
- h1 = _hash(d);
- h_iter = h1_map.find(h1);
- if(h_iter == h1_map.end())
- h1_map[h1] = 0;
- else
- h1_collis++;
- h2 = ( _hash(a) ^ _hash(b)^ _hash(c) );
- h_iter = h2_map.find(h2);
- if(h_iter == h2_map.end())
- h2_map[h2] = 0;
- else
- h2_collis++;
- h3 = triple_hash(a, b, c);
- h_iter = h3_map.find(h2);
- if(h_iter == h3_map.end())
- h3_map[h3] = 0;
- else
- h3_collis++;
- }
- std::cout << rounds << " : " << limit << " ST: " << h1_collis << " XOR: " << h2_collis << " BC: " << h3_collis << std::endl;
- time_t then, now;
- double seconds;
- unsigned int total = 0;
- rounds *= rounds;
- time(&then);
- for(unsigned int i = 0; i < rounds; ++i) {
- total += _hash(d);
- }
- time(&now);
- seconds = difftime(now, then);
- printf ("%.f seconds for straight hash.n", seconds);
- time(&then);
- for(unsigned int i = 0; i < rounds; ++i) {
- total += ( _hash(a) ^ _hash(b)^ _hash(c) );
- }
- time(&now);
- seconds = difftime(now, then);
- printf ("%.f seconds for XOR hash.n", seconds);
- time(&then);
- for(unsigned int i = 0; i < rounds; ++i) {
- total += triple_hash(a, b, c);
- }
- time(&now);
- seconds = difftime(now, then);
- printf ("%.f seconds for BC hash.n", seconds);
- std::cout << total << std::endl;
- return 0;
- }
- $ g++ -std=c++0x hashii.cpp
- $ ./a.out
- 1000000 : 4294967295 ST: 242 XOR: 222 BC: 107
- 9 seconds for straight hash.
- 22 seconds for XOR hash.
- 54 seconds for BC hash.
Add Comment
Please, Sign In to add comment