MCPcopy Create free account
hub / github.com/apache/arrow / ComputeStringHash

Function ComputeStringHash

cpp/src/arrow/util/hashing.h:163–223  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

161
162template <uint64_t AlgNum = 0>
163hash_t ComputeStringHash(const void* data, int64_t length) {
164 if (ARROW_PREDICT_TRUE(length <= 16)) {
165 // Specialize for small hash strings, as they are quite common as
166 // hash table keys. Even XXH3 isn't quite as fast.
167 auto p = reinterpret_cast<const uint8_t*>(data);
168 auto n = static_cast<uint32_t>(length);
169 if (n <= 8) {
170 if (n <= 3) {
171 if (n == 0) {
172 return 1U;
173 }
174 uint32_t x = (n << 24) ^ (p[0] << 16) ^ (p[n / 2] << 8) ^ p[n - 1];
175 return ScalarHelper<uint32_t, AlgNum>::ComputeHash(x);
176 }
177 // 4 <= length <= 8
178 // We can read the string as two overlapping 32-bit ints, apply
179 // different hash functions to each of them in parallel, then XOR
180 // the results
181 uint32_t x, y;
182 hash_t hx, hy;
183 x = util::SafeLoadAs<uint32_t>(p + n - 4);
184 y = util::SafeLoadAs<uint32_t>(p);
185 hx = ScalarHelper<uint32_t, AlgNum>::ComputeHash(x);
186 hy = ScalarHelper<uint32_t, AlgNum ^ 1>::ComputeHash(y);
187 return n ^ hx ^ hy;
188 }
189 // 8 <= length <= 16
190 // Apply the same principle as above
191 uint64_t x, y;
192 hash_t hx, hy;
193 x = util::SafeLoadAs<uint64_t>(p + n - 8);
194 y = util::SafeLoadAs<uint64_t>(p);
195 hx = ScalarHelper<uint64_t, AlgNum>::ComputeHash(x);
196 hy = ScalarHelper<uint64_t, AlgNum ^ 1>::ComputeHash(y);
197 return n ^ hx ^ hy;
198 }
199
200#if XXH3_SECRET_SIZE_MIN != 136
201# error XXH3_SECRET_SIZE_MIN changed, please fix kXxh3Secrets
202#endif
203
204 // XXH3_64bits_withSeed generates a secret based on the seed, which is too slow.
205 // Instead, we use hard-coded random secrets. To maximize cache efficiency,
206 // they reuse the same memory area.
207 static constexpr unsigned char kXxh3Secrets[XXH3_SECRET_SIZE_MIN + 1] = {
208 0xe7, 0x8b, 0x13, 0xf9, 0xfc, 0xb5, 0x8e, 0xef, 0x81, 0x48, 0x2c, 0xbf, 0xf9, 0x9f,
209 0xc1, 0x1e, 0x43, 0x6d, 0xbf, 0xa6, 0x6d, 0xb5, 0x72, 0xbc, 0x97, 0xd8, 0x61, 0x24,
210 0x0f, 0x12, 0xe3, 0x05, 0x21, 0xf7, 0x5c, 0x66, 0x67, 0xa5, 0x65, 0x03, 0x96, 0x26,
211 0x69, 0xd8, 0x29, 0x20, 0xf8, 0xc7, 0xb0, 0x3d, 0xdd, 0x7d, 0x18, 0xa0, 0x60, 0x75,
212 0x92, 0xa4, 0xce, 0xba, 0xc0, 0x77, 0xf4, 0xac, 0xb7, 0x03, 0x53, 0xf0, 0x98, 0xce,
213 0xe6, 0x2b, 0x20, 0xc7, 0x82, 0x91, 0xab, 0xbf, 0x68, 0x5c, 0x62, 0x4d, 0x33, 0xa3,
214 0xe1, 0xb3, 0xff, 0x97, 0x54, 0x4c, 0x44, 0x34, 0xb5, 0xb9, 0x32, 0x4c, 0x75, 0x42,
215 0x89, 0x53, 0x94, 0xd4, 0x9f, 0x2b, 0x76, 0x4d, 0x4e, 0xe6, 0xfa, 0x15, 0x3e, 0xc1,
216 0xdb, 0x71, 0x4b, 0x2c, 0x94, 0xf5, 0xfc, 0x8c, 0x89, 0x4b, 0xfb, 0xc1, 0x82, 0xa5,
217 0x6a, 0x53, 0xf9, 0x4a, 0xba, 0xce, 0x1f, 0xc0, 0x97, 0x1a, 0x87};
218
219 static_assert(AlgNum < 2, "AlgNum too large");
220 static constexpr auto secret = kXxh3Secrets + AlgNum;

Callers

nothing calls this directly

Calls

no outgoing calls

Tested by

no test coverage detected