2 * Copyright 2012 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include "folly/Hash.h"
18 #include "folly/MapUtil.h"
19 #include <gtest/gtest.h>
21 #include <unordered_map>
23 using namespace folly::hash;
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)));
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)));
37 const uint32_t s3_res = 216613626ul;
38 EXPECT_EQ(fnv32(s3), s3_res);
39 EXPECT_EQ(fnv32(s3), fnv32_buf(s3, strlen(s3)));
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)));
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)));
54 const uint64_t s3_res = 14695981039346656037ULL;
55 EXPECT_EQ(fnv64(s3), s3_res);
56 EXPECT_EQ(fnv64(s3), fnv64_buf(s3, strlen(s3)));
58 // note: Use fnv64_buf to make a single hash value from multiple
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,
67 uint64_t t4_hash2 = fnv64_buf(reinterpret_cast<void*>(&t4_b),
70 uint64_t t4_hash3 = fnv64_buf(reinterpret_cast<void*>(&t4_c),
73 uint64_t t4_hash4 = fnv64_buf(t4_d,
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
80 EXPECT_NE(t4_hash1, t4_hash4);
81 EXPECT_NE(t4_hash2, t4_hash4);
82 EXPECT_NE(t4_hash3, t4_hash4);
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)));
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)));
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)));
102 TEST(Hash, TWang_Mix64) {
103 uint64_t i1 = 0x78a87873e2d31dafULL;
104 uint64_t i1_res = 3389151152926383528ULL;
105 EXPECT_EQ(twang_mix64(i1), i1_res);
107 uint64_t i2 = 0x0123456789abcdefULL;
108 uint64_t i2_res = 3061460455458984563ull;
109 EXPECT_EQ(twang_mix64(i2), i2_res);
112 TEST(Hash, TWang_32From64) {
113 uint64_t i1 = 0x78a87873e2d31dafULL;
114 uint32_t i1_res = 1525586863ul;
115 EXPECT_EQ(twang_32from64(i1), i1_res);
117 uint64_t i2 = 0x0123456789abcdefULL;
118 uint32_t i2_res = 2918899159ul;
119 EXPECT_EQ(twang_32from64(i2), i2_res);
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);
127 uint32_t i2 = 2309737967ul;
128 uint32_t i2_res = 1834777923ul;
129 EXPECT_EQ(jenkins_rev_mix32(i2), i2_res);
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);
139 TEST(Hash, hash_combine) {
140 EXPECT_NE(hash_combine(1, 2), hash_combine(2, 1));