Guest User

Untitled

a guest
Jun 21st, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.58 KB | None | 0 0
  1. template <class T>
  2. inline void hash_combine(std::size_t& seed, const T& v)
  3. {
  4. std::hash<T> hasher;
  5. seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
  6. }
  7.  
  8. seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
  9.  
  10. #include <iostream>
  11. #include <functional>
  12. #include <stdlib.h>
  13. #include <map>
  14. #include <time.h>
  15.  
  16. template <class T>
  17. inline T hash_combine(const T& a, const T& b)
  18. {
  19. std::hash<T> hasher;
  20. return a ^ ( hasher(b) + 0x9e3779b9 + (a<<6) + (a>>2) );
  21. }
  22.  
  23. template <class T>
  24. inline T triple_hash(const T& a, const T& b, const T& c)
  25. {
  26. std::hash<T> hasher;
  27. return hash_combine(hash_combine(static_cast<T>(hasher(a)), b), c);
  28. }
  29.  
  30. int main(int argc, char** argv){
  31.  
  32. srand (time(NULL));
  33. std::hash<int> _hash;
  34. unsigned int rounds = 1000000;
  35. unsigned int limit = 0xFFFFFFFF;
  36.  
  37. std::map<int, int> h1_map;
  38. std::map<int, int> h2_map;
  39. std::map<int, int> h3_map;
  40. std::map<int,int>::iterator h_iter;
  41.  
  42. int h1_collis = 0;
  43. int h2_collis = 0;
  44. int h3_collis = 0;
  45.  
  46. unsigned int a,b,c,d,h1,h2,h3;
  47. for(unsigned int i = 0; i < rounds; ++i) {
  48. a = rand() % limit + 1;
  49. b = rand() % limit + 1;
  50. c = rand() % limit + 1;
  51. d = rand() % limit + 1;
  52.  
  53. h1 = _hash(d);
  54.  
  55. h_iter = h1_map.find(h1);
  56. if(h_iter == h1_map.end())
  57. h1_map[h1] = 0;
  58. else
  59. h1_collis++;
  60.  
  61. h2 = ( _hash(a) ^ _hash(b)^ _hash(c) );
  62.  
  63. h_iter = h2_map.find(h2);
  64. if(h_iter == h2_map.end())
  65. h2_map[h2] = 0;
  66. else
  67. h2_collis++;
  68.  
  69. h3 = triple_hash(a, b, c);
  70.  
  71. h_iter = h3_map.find(h2);
  72. if(h_iter == h3_map.end())
  73. h3_map[h3] = 0;
  74. else
  75. h3_collis++;
  76. }
  77.  
  78. std::cout << rounds << " : " << limit << " ST: " << h1_collis << " XOR: " << h2_collis << " BC: " << h3_collis << std::endl;
  79.  
  80. time_t then, now;
  81. double seconds;
  82. unsigned int total = 0;
  83.  
  84. rounds *= rounds;
  85.  
  86. time(&then);
  87. for(unsigned int i = 0; i < rounds; ++i) {
  88. total += _hash(d);
  89. }
  90. time(&now);
  91. seconds = difftime(now, then);
  92. printf ("%.f seconds for straight hash.n", seconds);
  93.  
  94. time(&then);
  95. for(unsigned int i = 0; i < rounds; ++i) {
  96. total += ( _hash(a) ^ _hash(b)^ _hash(c) );
  97. }
  98. time(&now);
  99. seconds = difftime(now, then);
  100. printf ("%.f seconds for XOR hash.n", seconds);
  101.  
  102. time(&then);
  103. for(unsigned int i = 0; i < rounds; ++i) {
  104. total += triple_hash(a, b, c);
  105. }
  106. time(&now);
  107. seconds = difftime(now, then);
  108. printf ("%.f seconds for BC hash.n", seconds);
  109. std::cout << total << std::endl;
  110. return 0;
  111. }
  112.  
  113. $ g++ -std=c++0x hashii.cpp
  114. $ ./a.out
  115. 1000000 : 4294967295 ST: 242 XOR: 222 BC: 107
  116. 9 seconds for straight hash.
  117. 22 seconds for XOR hash.
  118. 54 seconds for BC hash.
Add Comment
Please, Sign In to add comment