Test/hash_collision.cc at master · nongli/Test · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <stdio.h>
#include <string.h>
#include <vector>
#include <cstdint>

using namespace std;

static const uint64_t MURMUR_PRIME = 0xc6a4a7935bd1e995;
static const int MURMUR_R = 47;

#define SIMPLE_HASH 0

// Murmur2 hash implementation returning 64-bit hashes.
static uint64_t MurmurHash2_64(const void* input, int len, uint64_t seed) {
  uint64_t h = seed ^ (len * MURMUR_PRIME);

  const uint64_t* data = reinterpret_cast<const uint64_t*>(input);
  const uint64_t* end = data + (len / sizeof(uint64_t));

  while (data != end) {
    uint64_t k = *data++;
    k *= MURMUR_PRIME;
    k ^= k >> MURMUR_R;
    k *= MURMUR_PRIME;
    h ^= k;
    h *= MURMUR_PRIME;
  }

  const uint8_t* data2 = reinterpret_cast<const uint8_t*>(data);
  switch (len & 7) {
    case 7: h ^= uint64_t(data2[6]) << 48;
    case 6: h ^= uint64_t(data2[5]) << 40;
    case 5: h ^= uint64_t(data2[4]) << 32;
    case 4: h ^= uint64_t(data2[3]) << 24;
    case 3: h ^= uint64_t(data2[2]) << 16;
    case 2: h ^= uint64_t(data2[1]) << 8;
    case 1: h ^= uint64_t(data2[0]);
            h *= MURMUR_PRIME;
  }

  h ^= h >> MURMUR_R;
  h *= MURMUR_PRIME;
  h ^= h >> MURMUR_R;
  return h;
}

int main(int argc, char** argv) {
  vector<int> year;
  vector<int> month;
  vector<int> day;

  for (int i = 2000; i < 2200; i++) {
    year.push_back(i);
  }
  for (int i = 0; i < 12; i++) {
    month.push_back(i);
  }
  for (int i = 0; i < 30; i++) {
    day.push_back(i);
  }

  int NUM_PARTITIONS = 100;
  vector<vector<int> > partitions;
  partitions.resize(NUM_PARTITIONS);

  for (int i = 0; i < year.size(); i++) {
    for (int j = 0; j < month.size(); j++) {
      for (int k = 0; k < day.size(); k++) {

        uint64_t hash = 0;
#if SIMPLE_HASH
        hash = 31 * hash + year[i];
        hash = 31 * hash + month[j];
        hash = 31 * hash + day[k];
#else
        hash = MurmurHash2_64(&year[i], sizeof(int), hash);
        hash = MurmurHash2_64(&month[j], sizeof(int), hash);
        hash = MurmurHash2_64(&day[k], sizeof(int), hash);
#endif
        partitions[hash % NUM_PARTITIONS].push_back(hash);
      }
    }
  }


  int NUM_BUCKETS = 10;
  vector<int> buckets;
  buckets.resize(NUM_BUCKETS);
  const vector<int>& bucket_data = partitions[5];
  for (int i = 0; i < bucket_data.size(); i++) {
    int idx = bucket_data[i] % NUM_BUCKETS;
    if (idx < 0) idx = -idx;
    buckets[idx]++;
  }


  int max_bucket_size = 0;
  for (int i = 0; i < NUM_BUCKETS; i++) {
    if (buckets[i] > max_bucket_size) max_bucket_size = buckets[i];
  }

  int expected_per_bucket = bucket_data.size()/ NUM_BUCKETS;

  printf("Expected per bucket: %d\n", expected_per_bucket);
  printf("Max bucket: %d\n", max_bucket_size);

}