OLD | NEW |
1 /* | 1 /* |
2 Copyright (C) 2005 Apple Inc. All rights reserved. | 2 Copyright (C) 2005 Apple Inc. All rights reserved. |
3 | 3 |
4 This library is free software; you can redistribute it and/or | 4 This library is free software; you can redistribute it and/or |
5 modify it under the terms of the GNU Library General Public | 5 modify it under the terms of the GNU Library General Public |
6 License as published by the Free Software Foundation; either | 6 License as published by the Free Software Foundation; either |
7 version 2 of the License, or (at your option) any later version. | 7 version 2 of the License, or (at your option) any later version. |
8 | 8 |
9 This library is distributed in the hope that it will be useful, | 9 This library is distributed in the hope that it will be useful, |
10 but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
58 dataLogF("longest collision chain: %d\n", maxCollisions); | 58 dataLogF("longest collision chain: %d\n", maxCollisions); |
59 for (int i = 1; i <= maxCollisions; i++) { | 59 for (int i = 1; i <= maxCollisions; i++) { |
60 dataLogF(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with
this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collis
ionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses); | 60 dataLogF(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with
this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collis
ionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses); |
61 } | 61 } |
62 dataLogF("%d rehashes\n", numRehashes); | 62 dataLogF("%d rehashes\n", numRehashes); |
63 dataLogF("%d reinserts\n", numReinserts); | 63 dataLogF("%d reinserts\n", numReinserts); |
64 } | 64 } |
65 | 65 |
66 #endif | 66 #endif |
67 | 67 |
| 68 // integer hash function |
| 69 |
| 70 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm |
| 71 unsigned intHash(uint8_t key8) |
| 72 { |
| 73 unsigned key = key8; |
| 74 key += ~(key << 15); |
| 75 key ^= (key >> 10); |
| 76 key += (key << 3); |
| 77 key ^= (key >> 6); |
| 78 key += ~(key << 11); |
| 79 key ^= (key >> 16); |
| 80 return key; |
| 81 } |
| 82 |
| 83 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm |
| 84 unsigned intHash(uint16_t key16) |
| 85 { |
| 86 unsigned key = key16; |
| 87 key += ~(key << 15); |
| 88 key ^= (key >> 10); |
| 89 key += (key << 3); |
| 90 key ^= (key >> 6); |
| 91 key += ~(key << 11); |
| 92 key ^= (key >> 16); |
| 93 return key; |
| 94 } |
| 95 |
| 96 // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm |
| 97 unsigned intHash(uint32_t key) |
| 98 { |
| 99 key += ~(key << 15); |
| 100 key ^= (key >> 10); |
| 101 key += (key << 3); |
| 102 key ^= (key >> 6); |
| 103 key += ~(key << 11); |
| 104 key ^= (key >> 16); |
| 105 return key; |
| 106 } |
| 107 |
| 108 // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.h
tm |
| 109 unsigned intHash(uint64_t key) |
| 110 { |
| 111 key += ~(key << 32); |
| 112 key ^= (key >> 22); |
| 113 key += ~(key << 13); |
| 114 key ^= (key >> 8); |
| 115 key += (key << 3); |
| 116 key ^= (key >> 15); |
| 117 key += ~(key << 27); |
| 118 key ^= (key >> 31); |
| 119 return static_cast<unsigned>(key); |
| 120 } |
| 121 |
| 122 // Compound integer hash method: http://opendatastructures.org/versions/edition-
0.1d/ods-java/node33.html#SECTION00832000000000000000 |
| 123 unsigned pairIntHash(unsigned key1, unsigned key2) |
| 124 { |
| 125 unsigned shortRandom1 = 277951225; // A random 32-bit value. |
| 126 unsigned shortRandom2 = 95187966; // A random 32-bit value. |
| 127 uint64_t longRandom = 19248658165952622LL; // A random 64-bit value. |
| 128 |
| 129 uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2); |
| 130 unsigned highBits = static_cast<unsigned>(product >> (sizeof(uint64_t) - siz
eof(unsigned))); |
| 131 return highBits; |
| 132 } |
| 133 |
| 134 // Custom secondary hash function. |
| 135 unsigned doubleHash(unsigned key) |
| 136 { |
| 137 key = ~key + (key >> 23); |
| 138 key ^= (key << 12); |
| 139 key ^= (key >> 7); |
| 140 key ^= (key << 2); |
| 141 key ^= (key >> 20); |
| 142 return key; |
| 143 } |
| 144 |
68 } // namespace WTF | 145 } // namespace WTF |
OLD | NEW |