1 // Copyright 2013 Google Inc. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS-IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 // Original author: jyrki@google.com (Jyrki Alakuijala) 16 // Converted to D: madric@gmail.com (Vijay Nayar) 17 18 module s2.util.hash.mix; 19 20 // Fast mixing of hash values -- not strong enough for fingerprinting. 21 // May change from time to time. 22 // 23 // Values given are expected to be hashes from good hash functions. 24 // What constitutes a good hash may depend on your application. As a rule of 25 // thumb, if std::hash<int> is strong enough for your hashing need if 26 // your data were just ints, it will most likely be the correct choice 27 // for a mixed hash of data members. HashMix does one round of multiply and 28 // rotate mixing, so you get some additional collision avoidance guarantees 29 // compared to just using std::hash<int> directly. 30 // 31 // Possible use: 32 // 33 // struct Xyzzy { 34 // int x; 35 // int y; 36 // 37 // size_t toHash() const { 38 // auto mix = HashMix(x); 39 // mix.mix(y); 40 // return mix.get() 41 // } 42 // } 43 // 44 45 struct HashMix { 46 private: 47 static size_t MUL = 0xdc3eb94af8ab4c93; 48 49 size_t _hash = 1; 50 51 public: 52 this(size_t val) nothrow @safe { 53 _hash = val + 83; 54 } 55 56 HashMix mix(size_t val) nothrow @safe { 57 _hash *= MUL; 58 _hash = ((_hash << 19) | 59 (_hash >> size_t.sizeof * 8 - 19)) + val; 60 return this; 61 } 62 63 size_t get() const nothrow @safe { 64 return _hash; 65 } 66 }