folly/test/HashTest.cpp

   1 /*
   2  * Copyright 2012 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "folly/Hash.h"
  18 #include "folly/MapUtil.h"
  19 #include <gtest/gtest.h>
  20 #include <stdint.h>
  21 #include <unordered_map>
  22
  23 using namespace folly::hash;
  24
  25 TEST(Hash, Fnv32) {
  26   const char* s1 = "hello, world!";
  27   const uint32_t s1_res = 3180823791ul;
  28   EXPECT_EQ(fnv32(s1), s1_res);
  29   EXPECT_EQ(fnv32(s1), fnv32_buf(s1, strlen(s1)));
  30
  31   const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
  32   const uint32_t s2_res = 194407565ul;
  33   EXPECT_EQ(fnv32(s2), s2_res);
  34   EXPECT_EQ(fnv32(s2), fnv32_buf(s2, strlen(s2)));
  35
  36   const char* s3 = "";
  37   const uint32_t s3_res = 216613626ul;
  38   EXPECT_EQ(fnv32(s3), s3_res);
  39   EXPECT_EQ(fnv32(s3), fnv32_buf(s3, strlen(s3)));
  40 }
  41
  42 TEST(Hash, Fnv64) {
  43   const char* s1 = "hello, world!";
  44   const uint64_t s1_res = 13991426986746681734ULL;
  45   EXPECT_EQ(fnv64(s1), s1_res);
  46   EXPECT_EQ(fnv64(s1), fnv64_buf(s1, strlen(s1)));
  47
  48   const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
  49   const uint64_t s2_res = 6091394665637302478ULL;
  50   EXPECT_EQ(fnv64(s2), s2_res);
  51   EXPECT_EQ(fnv64(s2), fnv64_buf(s2, strlen(s2)));
  52
  53   const char* s3 = "";
  54   const uint64_t s3_res = 14695981039346656037ULL;
  55   EXPECT_EQ(fnv64(s3), s3_res);
  56   EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
  57
  58   // note: Use fnv64_buf to make a single hash value from multiple
  59   // fields/datatypes.
  60   const char* t4_a = "E Pluribus";
  61   int64_t t4_b = 0xF1E2D3C4B5A69788;
  62   int32_t t4_c = 0xAB12CD34;
  63   const char* t4_d = "Unum";
  64   uint64_t t4_res = 15571330457339273965ULL;
  65   uint64_t t4_hash1 = fnv64_buf(t4_a,
  66                                 strlen(t4_a));
  67   uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
  68                                 sizeof(int64_t),
  69                                 t4_hash1);
  70   uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
  71                                 sizeof(int32_t),
  72                                 t4_hash2);
  73   uint64_t t4_hash4 = fnv64_buf(t4_d,
  74                                 strlen(t4_d),
  75                                 t4_hash3);
  76   EXPECT_EQ(t4_hash4, t4_res);
  77   // note: These are probabalistic, not determinate, but c'mon.
  78   // These hash values should be different, or something's not
  79   // working.
  80   EXPECT_NE(t4_hash1, t4_hash4);
  81   EXPECT_NE(t4_hash2, t4_hash4);
  82   EXPECT_NE(t4_hash3, t4_hash4);
  83 }
  84
  85 TEST(Hash, Hsieh32) {
  86   const char* s1 = "hello, world!";
  87   const uint32_t s1_res = 2918802987ul;
  88   EXPECT_EQ(hsieh_hash32(s1), s1_res);
  89   EXPECT_EQ(hsieh_hash32(s1), hsieh_hash32_buf(s1, strlen(s1)));
  90
  91   const char* s2 = "monkeys! m0nk3yz! ev3ry \\/\\/here~~~~";
  92   const uint32_t s2_res = 47373213ul;
  93   EXPECT_EQ(hsieh_hash32(s2), s2_res);
  94   EXPECT_EQ(hsieh_hash32(s2), hsieh_hash32_buf(s2, strlen(s2)));
  95
  96   const char* s3 = "";
  97   const uint32_t s3_res = 0;
  98   EXPECT_EQ(hsieh_hash32(s3), s3_res);
  99   EXPECT_EQ(hsieh_hash32(s3), hsieh_hash32_buf(s3, strlen(s3)));
 100 }
 101
 102 TEST(Hash, TWang_Mix64) {
 103   uint64_t i1 = 0x78a87873e2d31dafULL;
 104   uint64_t i1_res = 3389151152926383528ULL;
 105   EXPECT_EQ(twang_mix64(i1), i1_res);
 106
 107   uint64_t i2 = 0x0123456789abcdefULL;
 108   uint64_t i2_res = 3061460455458984563ull;
 109   EXPECT_EQ(twang_mix64(i2), i2_res);
 110 }
 111
 112 TEST(Hash, TWang_32From64) {
 113   uint64_t i1 = 0x78a87873e2d31dafULL;
 114   uint32_t i1_res = 1525586863ul;
 115   EXPECT_EQ(twang_32from64(i1), i1_res);
 116
 117   uint64_t i2 = 0x0123456789abcdefULL;
 118   uint32_t i2_res = 2918899159ul;
 119   EXPECT_EQ(twang_32from64(i2), i2_res);
 120 }
 121
 122 TEST(Hash, Jenkins_Rev_Mix32) {
 123   uint32_t i1 = 3805486511ul;
 124   uint32_t i1_res = 381808021ul;
 125   EXPECT_EQ(jenkins_rev_mix32(i1), i1_res);
 126
 127   uint32_t i2 = 2309737967ul;
 128   uint32_t i2_res = 1834777923ul;
 129   EXPECT_EQ(jenkins_rev_mix32(i2), i2_res);
 130 }
 131
 132 TEST(Hash, hasher) {
 133   // Basically just confirms that things compile ok.
 134   std::unordered_map<int32_t,int32_t,folly::hasher<int32_t>> m;
 135   m.insert(std::make_pair(4, 5));
 136   EXPECT_EQ(get_default(m, 4), 5);
 137 }