<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=""><br class=""><div><blockquote type="cite" class=""><div class="">On Mar 13, 2017, at 8:38 AM, 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></div></div></div></blockquote></div><div>And that’s why I tend to look at Dictionary<> and Set<> kinda like they’re that kid in The Exorcist whenever I start thinking about how they work…</div><div><br class=""></div><div>I understand hashing in theory, but can’t for the life of me come up with an algorithm for creating them the wouldn't almost immediately result in collisions for the kinds of use-cases I envision. I haven’t finished reading the proposal yet, but I wanted to get a firm and enthusiastic +1 in for its intent.</div></body></html>