<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Yes please! I’ve a package on GitHub to implement roughly the same thing. I’ve been happily using it for months now, and I wouldn’t ever write a hashValue implementation by hand again.</div><div class=""><br class=""></div><div class=""><a href="https://github.com/lorentey/SipHash" class="">https://github.com/lorentey/SipHash</a></div><div class=""><br class=""></div><div class=""><div class="">I think the fact that we’ve both come up with essentially the same API is an interesting data point; it definitely underlines the need for a better Hashable protocol.</div></div><div class=""><br class=""></div><div class="">My comments:</div><div class=""><br class=""></div><div class="">* In an ideal world, this would be a replacement for Hashable, not a protocol with a different name. Once visitor-based hashing becomes available, nobody should implement a hashValue property.</div><div class=""><br class=""></div><div class="">* All standard Hashable types in standard library should implement the new hash function directly, rather than relying on the default implementation.</div><div class=""><br class=""></div><div class="">* Why is the HashVisitable.hash a generic function? Hasher could just as well be a concrete type defined in stdlib. Making it generic may have some performance implications.</div><div class=""><br class=""></div><div class="">* I find that I prefer to hash components by calling a mutating method on the hasher, rather than directly calling the components' hash implementations. Putting the hasher first is much more readable to me, primarily because it gets rid of all the distracting &s. It also makes it possible to find slightly better names, eliminating the repetitiveness of "foo.hash(&hasher)":</div><div class=""><br class=""></div><div class="">extension GridPoint: SipHashable {</div> func appendHashes(to hasher: inout<div class=""> SipHasher) {</div><div class=""> hasher.append(x)</div><div class=""> hasher.append(y)</div><div class=""> }</div><div class="">}</div><div class=""><br class=""></div><div class="">* I suggest using SipHash instead of FNV-1a. The standard library already contains an implementation for SipHash, as undocumented internal API, complete with a note that it should be made public. AFAICR, it is currently only used for String hashing, but it would be very much worth making it universal. (Accomodating SipHash's random key is one reason why hashValue’s documentation explicitly notes that its value is "not guaranteed to be equal across different executions of your program.”)</div><div class=""><br class=""></div><div class="">* ContiguouslyHashable seems like an unsafe construct to me. It is quite dangerous to base hashing on the raw byte sequence underlying a value: for example, struct values may include uninitialized gaps between some of their stored properties due to alignment constraints. So two otherwise identical values may very well have different in-memory representations. Therefore, I suggest ContiguouslyHashable should be removed from the proposal. Swift programmers who know what they’re doing would still be able to call withUnsafeBytes(of:) when they want to, but regular schmoes like myself will not be tempted to shoot themselves in the foot by using it inappropriately.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class="">Karoly</div><div class=""><br class=""></div><div class=""><br class=""></div><div><blockquote type="cite" class=""><div class="">On 2017-03-13, at 16:38, Vincent Esche via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">Hi there,</div><div class=""><br class=""></div><div class="">I've written up a proposal for an overhaul/replacement of the Hashable protocol and would love to hear your feedback on it!</div><div class=""><br class=""></div><a href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25" class="">Rendered</a> | <a href="https://blog.definiteloops.com/ha-r-sh-visitors-8c0c3686a46f" class="">Blog Post</a><div class=""><br class=""></div><div class="">Cheers,</div><div class="">Vincent</div><div class=""><br class=""></div><div class="">Ps: I'd like to thank David Hart (@hartbit) for his great editorial feedback on this proposal. 👍</div><div class=""><br class=""></div><div class=""><h1 style="box-sizing:border-box;margin:0px 0px 16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class="">HashVisitable</h1><ul style="box-sizing:border-box;padding-left:2em;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class=""><li style="box-sizing:border-box" class="">Proposal: <a href="https://gist.github.com/regexident/NNNN-filename.md" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none" class="">SE-NNNN</a></li><li style="box-sizing:border-box;margin-top:0.25em" class="">Authors: <a href="https://github.com/regexident" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none" class="">Vincent Esche</a></li><li style="box-sizing:border-box;margin-top:0.25em" class="">Review Manager: TBD</li><li style="box-sizing:border-box;margin-top:0.25em" class="">Status: <span style="box-sizing:border-box;font-weight:600" class="">Awaiting review</span></li></ul><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-introduction" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#introduction" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Introduction</h2><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Replace the <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hashable</code> protocol by two new procotols (<code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hasher</code> and <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">HashVisitable</code>) to improve safety, versatility and learnability.</p><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-motivation" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#motivation" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Motivation</h2><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Implementing <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hashable</code> is difficult and the consequences if not done well have dire performance and safety repercussions.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">The documentation of <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hashable</code> lists a <a href="https://developer.apple.com/reference/swift/hashable" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none" class="">sample implementation</a> of <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">var hashValue</code>:</p><pre style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;margin-top:0px;margin-bottom:16px;font-stretch:normal;line-height:1.45;word-wrap:normal;padding:16px;overflow:auto;background-color:rgb(246,248,250);border-radius:3px;color:rgb(36,41,46)" class=""><code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0px;margin:0px;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-radius:3px;word-break:normal;border:0px;display:inline;overflow:visible;line-height:inherit;word-wrap:normal" class="">/// A point in an x-y coordinate system.
struct GridPoint {
var x: Int
var y: Int
}
extension GridPoint: Hashable {
var hashValue: Int {
return x.hashValue ^ y.hashValue
}
static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {
return lhs.x == rhs.x && lhs.y == rhs.y
}
}
</code></pre><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Calculating the hashes of all <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">GridPoints</code> (given the above implementation) on a <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">1000 × 1000</code> grid …</p><pre style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;margin-top:0px;margin-bottom:16px;font-stretch:normal;line-height:1.45;word-wrap:normal;padding:16px;overflow:auto;background-color:rgb(246,248,250);border-radius:3px;color:rgb(36,41,46)" class=""><code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0px;margin:0px;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-radius:3px;word-break:normal;border:0px;display:inline;overflow:visible;line-height:inherit;word-wrap:normal" class="">let (width, height) = (1000, 1000)
let total = width * height
var hashes = Set<Int>()
for x in 0..<width {
for y in 0..<height {
hashes.insert(GridPoint(x: x, y: y).hashValue)
}
}
print("\(hashes.count) unique hashes out of a total of \(total).")
</code></pre><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">… results in just <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">1024</code> unique hash values for <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">1_000_000</code> unique values.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">In other words: The recommended implementation causes 99.9% of values to trigger a hash collision.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Out of those <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">1_000_000</code> values the median collision count was <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">976</code> with min and max being <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">976</code> and <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">1000</code>respectively.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">The collision rate will have negative impact in algorithms which heavily use <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">hashValue</code> like the ones in <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Dictionary</code>and <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Set</code>. Furthermore, it increases the vulnerability to <a href="https://arstechnica.com/business/2011/12/huge-portions-of-web-vulnerable-to-hashing-denial-of-service-attack/" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none" class="">DDOS attacks when exposed to the web</a>.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">If even the official Swift documentation gets the implementation of <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">hashValue</code> wrong, then who is to expect the average Swift programmer to do any better?</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">In contrast, running the same snippet using <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">HashVisitable</code> and the semi-secure <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Fnv1aHash</code> (see below) results in zero collisions!</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Finally, the design of the <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hashable</code> protocol forces the use of one implementation without the possibility of switching between multiple hashing algorithms.</p><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-proposed-solution" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#proposed-solution" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Proposed solution</h2><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Instead of coupling the hashing algorithm with each and every Swift type, we should provide a hashing API based on the visitor-pattern. By freeing application developers from the burden of having to implement hashing algorithms, the Standard Library can provide default ones which fulfill collision, performance and security goals. Furthermore, it would allow developers to swap to different algorithms based on the use case.</p><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-detailed-design" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#detailed-design" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Detailed design</h2><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">The proposal deprecates the <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hashable</code> protocol and introduces the following two:</p><div class="gmail-highlight gmail-highlight-source-swift" style="box-sizing:border-box;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px"><pre style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;margin-top:0px;margin-bottom:0px;font-stretch:normal;line-height:1.45;word-wrap:normal;padding:16px;overflow:auto;background-color:rgb(246,248,250);border-radius:3px;word-break:normal" class=""><span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">protocol</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">Hasher</span> {
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">mutating</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">func</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">finish</span>() <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">-></span> <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">Int</span>
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">mutating</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">func</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">write</span>(<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)"><span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">bytes</span></span>: UnsafeRawBufferPointer)
}
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">protocol</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">HashVisitable</span> {
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">func</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">hash</span><<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">H</span>: <span class="gmail-pl-e" style="box-sizing:border-box;color:rgb(121,93,163)">Hasher</span>>(<span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">_</span> <span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">hasher</span>: <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">inout</span> H)
}</pre></div><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class=""><code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hasher</code> is the protocol which represents a hashing algorithm, and <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">HashVisitable</code> replaces <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hashable</code>. For types entirely represented by their memory layout, the following protocol would provide a default implementation:</p><pre style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;margin-top:0px;margin-bottom:16px;font-stretch:normal;line-height:1.45;word-wrap:normal;padding:16px;overflow:auto;background-color:rgb(246,248,250);border-radius:3px;color:rgb(36,41,46)" class=""><code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0px;margin:0px;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;background-color:transparent;border-radius:3px;word-break:normal;border:0px;display:inline;overflow:visible;line-height:inherit;word-wrap:normal" class="">protocol ContiguouslyHashable: HashVisitable {}
extension ContiguouslyHashable {
func hash<H: Hasher>(_ hasher: inout H) {
var mutableSelf = self
try! Swift.withUnsafeBytes(of: &mutableSelf) {
hasher.write(bytes: $0)
}
}
}
extension Bool : ContiguouslyHashable {}
extension UInt8 : ContiguouslyHashable {}
extension UInt16 : ContiguouslyHashable {}
extension UInt32 : ContiguouslyHashable {}
extension UInt64 : ContiguouslyHashable {}
extension UInt : ContiguouslyHashable {}
extension Int8 : ContiguouslyHashable {}
extension Int16 : ContiguouslyHashable {}
extension Int32 : ContiguouslyHashable {}
extension Int64 : ContiguouslyHashable {}
extension Int : ContiguouslyHashable {}
</code></pre><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">The Standard-Library would then provide a set of hashing implementations specific to each purpose. A possible choice for hashing algorithms would be the reasonably fast <a href="https://en.wikipedia.org/wiki/SipHash" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none" class="">SipHash-2-4</a>, and the reasonably secure <a href="https://en.wikipedia.org/wiki/SipHash" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none" class="">SipHash-4-8</a>.</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">FNV-1A is another popular semi-secure but blazingly fast hash algorithm, which – for the sake of demonstration – could be implemented as follows:</p><div class="gmail-highlight gmail-highlight-source-swift" style="box-sizing:border-box;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px"><pre style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;margin-top:0px;margin-bottom:0px;font-stretch:normal;line-height:1.45;word-wrap:normal;padding:16px;overflow:auto;background-color:rgb(246,248,250);border-radius:3px;word-break:normal" class=""><span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">struct</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">Fnv1aHash</span> {
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">fileprivate</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">var</span> state<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">:</span> <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">UInt</span>
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">init</span>(<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)"><span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">seed</span></span>: <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">UInt</span>) {
<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">self</span>.<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">state</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">=</span> seed <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">&+</span> <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">14695981039346656037</span>
}
}
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">extension</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">Fnv1aHash</span>: <span class="gmail-pl-e" style="box-sizing:border-box;color:rgb(121,93,163)">Hasher </span>{
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">mutating</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">func</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">write</span>(<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)"><span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">bytes</span></span>: UnsafeRawBufferPointer) {
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">for</span> byte <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">in</span> bytes {
<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">self</span>.<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">state</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">=</span> (<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">self</span>.<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">state</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">^</span> <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">UInt</span>(byte)) <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">&*</span> <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">1099511628211</span>
}
}
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">mutating</span> <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">func</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">finish</span>() <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">-></span> <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">Int</span> {
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">return</span> <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">unsafeBitCast</span>(<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">self</span>.<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">state</span>, <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">to</span>: <span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">Int</span>.<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">self</span>)
}
}</pre></div><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Coming back to the sample code present in the <code style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;padding:0.2em 0px;margin:0px;background-color:rgba(27,31,35,0.0470588);border-radius:3px" class="">Hashable</code> documentation, the new implementation would look like:</p><div class="gmail-highlight gmail-highlight-source-swift" style="box-sizing:border-box;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px"><pre style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;margin-top:0px;margin-bottom:0px;font-stretch:normal;line-height:1.45;word-wrap:normal;padding:16px;overflow:auto;background-color:rgb(246,248,250);border-radius:3px;word-break:normal" class=""><span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">extension</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">GridPoint</span>: <span class="gmail-pl-e" style="box-sizing:border-box;color:rgb(121,93,163)">HashVisitable </span>{
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">func</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">hash</span><<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">H</span>: <span class="gmail-pl-e" style="box-sizing:border-box;color:rgb(121,93,163)">Hasher</span>>(<span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">_</span> <span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">hasher</span>: <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">inout</span> H) {
<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">self</span>.<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">x</span>.<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">hash</span>(<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">&</span>hasher)
<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">self</span>.<span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">y</span>.<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">hash</span>(<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">&</span>hasher)
}
}</pre></div><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-source-compatibility" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#source-compatibility" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Source compatibility</h2><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">Making use of "<a href="https://github.com/apple/swift-evolution/blob/d33c129f0920af0404f42219db56981411b20e76/proposals/0143-conditional-conformances.md#extending-protocols-to-conform-to-protocols" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none" class="">extending protocols to conform to protocols</a>":</p><div class="gmail-highlight gmail-highlight-source-swift" style="box-sizing:border-box;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px"><pre style="box-sizing:border-box;font-family:sfmono-regular,consolas,"liberation mono",menlo,courier,monospace;font-size:13.6px;margin-top:0px;margin-bottom:0px;font-stretch:normal;line-height:1.45;word-wrap:normal;padding:16px;overflow:auto;background-color:rgb(246,248,250);border-radius:3px;word-break:normal" class=""><span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">extension</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)"><span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">Hashable</span></span>: <span class="gmail-pl-e" style="box-sizing:border-box;color:rgb(121,93,163)">HashVisitable </span>{
<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">func</span> <span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">hash</span><<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">H</span>: <span class="gmail-pl-e" style="box-sizing:border-box;color:rgb(121,93,163)">Hasher</span>>(<span class="gmail-pl-en" style="box-sizing:border-box;color:rgb(121,93,163)">_</span> <span class="gmail-pl-smi" style="box-sizing:border-box;color:rgb(51,51,51)">hasher</span>: <span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">inout</span> H) {
<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">self</span>.<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">hashValue</span>.<span class="gmail-pl-c1" style="box-sizing:border-box;color:rgb(0,134,179)">hash</span>(<span class="gmail-pl-k" style="box-sizing:border-box;color:rgb(167,29,93)">&</span>hasher)
}
}</pre></div><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-effect-on-abi-stability" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#effect-on-abi-stability" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Effect on ABI stability</h2><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">n/a</p><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-effect-on-api-resilience" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#effect-on-api-resilience" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Effect on API resilience</h2><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol";font-size:16px" class="">This feature should be possible to add/remove without breaking ABI.</p><h2 style="box-sizing:border-box;margin-top:24px;margin-bottom:16px;line-height:1.25;padding-bottom:0.3em;border-bottom:1px solid rgb(234,236,239);color:rgb(36,41,46);font-family:-apple-system,system-ui,"segoe ui",helvetica,arial,sans-serif,"apple color emoji","segoe ui emoji","segoe ui symbol"" class=""><a id="gmail-user-content-alternatives-considered" class="gmail-anchor" href="https://gist.github.com/regexident/1b8e84974da2243e5199e760508d2d25#alternatives-considered" style="box-sizing:border-box;background-color:transparent;color:rgb(3,102,214);text-decoration:none;float:left;padding-right:4px;line-height:1"></a>Alternatives considered</h2><div style="box-sizing: border-box; margin-top: 0px; color: rgb(36, 41, 46); font-family: -apple-system, system-ui, 'segoe ui', helvetica, arial, sans-serif, 'apple color emoji', 'segoe ui emoji', 'segoe ui symbol'; font-size: 16px; margin-bottom: 0px;" class="">n/a</div></div></div>
_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></body></html>