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 #ifndef FOLLY_BASE_HASH_H_
18 #define FOLLY_BASE_HASH_H_
25 * Various hashing functions.
28 namespace folly { namespace hash {
30 //////////////////////////////////////////////////////////////////////
33 * Thomas Wang 64 bit mix hash function
36 inline uint64_t twang_mix64(uint64_t key) {
37 key = (~key) + (key << 21);
38 key = key ^ (key >> 24);
39 key = (key + (key << 3)) + (key << 8);
40 key = key ^ (key >> 14);
41 key = (key + (key << 2)) + (key << 4);
42 key = key ^ (key >> 28);
43 key = key + (key << 31);
48 * Thomas Wang downscaling hash function
51 inline uint32_t twang_32from64(uint64_t key) {
52 key = (~key) + (key << 18);
53 key = key ^ (key >> 31);
55 key = key ^ (key >> 11);
56 key = key + (key << 6);
57 key = key ^ (key >> 22);
58 return (uint32_t) key;
62 * Robert Jenkins' reversible 32 bit mix hash function
65 inline uint32_t jenkins_rev_mix32(uint32_t key) {
78 * Fowler / Noll / Vo (FNV) Hash
79 * http://www.isthe.com/chongo/tech/comp/fnv/
82 const uint32_t FNV_32_HASH_START = 216613626UL;
83 const uint64_t FNV_64_HASH_START = 14695981039346656037ULL;
85 inline uint32_t fnv32(const char* s,
86 uint32_t hash = FNV_32_HASH_START) {
88 hash += (hash << 1) + (hash << 4) + (hash << 7) +
89 (hash << 8) + (hash << 24);
95 inline uint32_t fnv32_buf(const void* buf,
97 uint32_t hash = FNV_32_HASH_START) {
98 const char* char_buf = reinterpret_cast<const char*>(buf);
100 for (int i = 0; i < n; ++i) {
101 hash += (hash << 1) + (hash << 4) + (hash << 7) +
102 (hash << 8) + (hash << 24);
109 inline uint32_t fnv32(const std::string& str,
110 uint64_t hash = FNV_32_HASH_START) {
111 return fnv32_buf(str.data(), str.size(), hash);
114 inline uint64_t fnv64(const char* s,
115 uint64_t hash = FNV_64_HASH_START) {
117 hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
118 (hash << 8) + (hash << 40);
124 inline uint64_t fnv64_buf(const void* buf,
126 uint64_t hash = FNV_64_HASH_START) {
127 const char* char_buf = reinterpret_cast<const char*>(buf);
129 for (int i = 0; i < n; ++i) {
130 hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
131 (hash << 8) + (hash << 40);
137 inline uint64_t fnv64(const std::string& str,
138 uint64_t hash = FNV_64_HASH_START) {
139 return fnv64_buf(str.data(), str.size(), hash);
143 * Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html
146 #define get16bits(d) (*((const uint16_t*) (d)))
148 inline uint32_t hsieh_hash32_buf(const void* buf, int len) {
149 const char* s = reinterpret_cast<const char*>(buf);
154 if (len <= 0 || buf == 0) {
162 for (;len > 0; len--) {
163 hash += get16bits (s);
164 tmp = (get16bits (s+2) << 11) ^ hash;
165 hash = (hash << 16) ^ tmp;
166 s += 2*sizeof (uint16_t);
170 /* Handle end cases */
173 hash += get16bits(s);
175 hash ^= s[sizeof (uint16_t)] << 18;
179 hash += get16bits(s);
189 /* Force "avalanching" of final 127 bits */
202 inline uint32_t hsieh_hash32(const char* s) {
203 return hsieh_hash32_buf(s, std::strlen(s));
206 inline uint32_t hsieh_hash32_str(const std::string& str) {
207 return hsieh_hash32_buf(str.data(), str.size());
210 //////////////////////////////////////////////////////////////////////
217 template<> struct hasher<int32_t> {
218 size_t operator()(int32_t key) const {
219 return hash::jenkins_rev_mix32(uint32_t(key));
223 template<> struct hasher<uint32_t> {
224 size_t operator()(uint32_t key) const {
225 return hash::jenkins_rev_mix32(key);
229 template<> struct hasher<int64_t> {
230 size_t operator()(int64_t key) const {
231 return hash::twang_mix64(uint64_t(key));
235 template<> struct hasher<uint64_t> {
236 size_t operator()(uint64_t key) const {
237 return hash::twang_mix64(key);