Created
October 18, 2017 06:48
-
-
Save ctreffs/81c1338d999950e0717e3a760e6a35ce to your computer and use it in GitHub Desktop.
[Swift] hash combine and hash range
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// Calculates the combined hash of two values. This implementation is based on boost::hash_combine. | |
/// Will always produce the same result for the same combination of seed and value during the single run of a program. | |
/// | |
/// - Parameters: | |
/// - seed: seed hash. | |
/// - value: value to be combined with seed hash. | |
/// - Returns: combined hash value. | |
func hash(combine seed: Int, _ value: Int) -> Int { | |
/// http://www.boost.org/doc/libs/1_65_1/doc/html/hash/combine.html | |
/// http://www.boost.org/doc/libs/1_65_1/doc/html/hash/reference.html#boost.hash_combine | |
/// http://www.boost.org/doc/libs/1_65_1/boost/functional/hash/hash.hpp | |
/// http://book.huihoo.com/data-structures-and-algorithms-with-object-oriented-design-patterns-in-c++/html/page214.html | |
/// https://stackoverflow.com/a/35991300 | |
/// https://stackoverflow.com/a/4948967 | |
/* | |
let phi = (1.0 + sqrt(5.0)) / 2 // golden ratio | |
let a32 = pow(2.0,32.0) / phi | |
let a64 = pow(2.0,64.0) / phi | |
*/ | |
#if arch(x86_64) || arch(arm64) // 64 bit | |
let fibA: UInt = 0x9e3779b97f4a7c15 // = 11400714819323198485 aka Fibonacci Hash a value for 2^64; calculate by: 2^64 / (golden ratio) | |
#elseif arch(i386) || arch(arm) // 32 bit | |
let fibA: UInt = 0x9e3779b9 // = 2654435769 aka Fibonacci Hash a value for 2^32; calculate by: 2^32 / (golden ratio) | |
#endif | |
var uSeed = UInt(bitPattern: seed) | |
let uValue = UInt(bitPattern: value) | |
uSeed ^= uValue &+ fibA &+ (uSeed << 6) &+ (uSeed >> 2) | |
return Int(bitPattern: uSeed) | |
} | |
/// Calculates the combined hash value of the elements. This implementation is based on boost::hash_range. | |
/// Is sensitive to the order of the elements. | |
/// - Parameter hashValues: sequence of hash values to combine. | |
/// - Returns: combined hash value. | |
func hash<S: Sequence>(combine hashValues: S) -> Int where S.Element == Int { | |
/// http://www.boost.org/doc/libs/1_65_1/doc/html/hash/reference.html#boost.hash_range_idp517643120 | |
return hashValues.reduce(0, { hash(combine: $0, $1) }) | |
} | |
/// Calculates the combined hash value of the elements. This implementation is based on boost::hash_range. | |
/// Is sensitive to the order of the elements. | |
/// - Parameter hashValues: sequence of hash values to combine. | |
/// - Returns: combined hash value. | |
func hash<H: Sequence>(combine hashables: H) -> Int where H.Element == Hashable { | |
/// http://www.boost.org/doc/libs/1_65_1/doc/html/hash/reference.html#boost.hash_range_idp517643120 | |
return hashables.reduce(0, { hash(combine: $0, $1.hashValue) }) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Is this MurMurHash? I have a friend who has code which uses "0x9E3779B97F4A7C15" and it's known.