# Let Optional, Dictionary and Array conditionally conform to Hashable **URL:** \ **Category:** Pitches\ **Created:** [January 26, 2018, 8:18pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046 "2018-01-26T20:18:50Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 26, 2018, 8:18pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/1 "2018-01-26T20:18:50Z")
Hi all, I just tried out Swift 4.1 synthesis of Equatable and Hashable. This is truly awesome, and removes boilerplate code that is bothersome to maintain. In case of Hashable it also eliminates the need for the developer to know and understand the intricacies of creating good hashes. When synthesizing Hashable I noticed that Array, Optional and Dictionary do not conditionally conform to Hashable, while Set (unconditionally) does. While it is fairly easy to add the support through conditional conformances (awesome!), the developer still has to know and understand how to create good hashes. I looked at Set’s Hashable implementation and made similar implementations for the other three types. Are there any reasons that these should not be added to the standard library?? I’d be happy to give the implementation a go and try writing a formal proposal. Sincerely, /morten ---
**Author:** ![moiseev](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/moiseev/32/281_2.png) [@moiseev](https://forums.swift.org/u/moiseev)\ **Post date:** [January 26, 2018, 10:14pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/2 "2018-01-26T22:14:56Z")
@ben-cohen, IIRC we made `Array` etc. conditionally `Equatable` without an evolution proposal. This addition seem to be from the same bucket. Do we need a proposal or the implementation would suffice? ---
**Author:** ![saagarjha](https://avatars.discourse-cdn.com/v4/letter/s/85f322/32.png) [@saagarjha](https://forums.swift.org/u/saagarjha)\ **Post date:** [January 27, 2018, 12:13am UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/3 "2018-01-27T00:13:25Z")
I'm on board for [`Optional`](https://forums.swift.org/t/pitch-conditionally-conform-optional-sequence-where-wrapped-sequence/7733/2) and `Array`, but when would `Dictionary` conform? When both its `Key`s and `Value`s are `Hashable`? ---
**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\ **Post date:** [January 27, 2018, 4:07am UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/4 "2018-01-27T04:07:41Z")
> [@saagarjha](#): > > When both its Keys and Values are Hashable? That's the only way, no? ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 27, 2018, 1:21pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/5 "2018-01-27T13:21:14Z")
Right, when both keys and values are Hashable. When two dictionaries are equal they must hash to the same value, so that requirement is given. ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 28, 2018, 2:44pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/6 "2018-01-28T14:44:05Z")
And Dictionary keys are already Hashable, so the extra requirement is only for the values to be Hashable. ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 28, 2018, 3:16pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/7 "2018-01-28T15:16:39Z")
I am right now trying to move my very simple implementation into the standard library, and I am meeting a few obstacles, never having tried to build/test the entire swift codebase before. I have a few questions, but I don't know if this is the correct forum to ask the questions in. If it's not the best place to ask these questions, please have me excused. For reference, here is my first shot (still lacking tests for Array and Dictionary): > **[GitHub - mortenbekditlevsen/swift at hashable](https://github.com/mortenbekditlevsen/swift/tree/hashable)** > > hashable For Optional, I have added the implementation to stdlib/public/core/Optional.swift right after the conditional conformance to Equatable. For testing the Optional conditional conformance to Hashable, I have basically duplicated the tests for Equatable: ``` OptionalTests.test("Hashable") { expectEqual([true, false, false, false, false, true], testRelation { $0.hashValue == $1.hashValue }) expectEqual([false, true, true, true, true, false], testRelation { $0.hashValue != $1.hashValue }) } ``` So this verifies that equal optionals have equal hashes (and for these specific values that the non-equal optionals also happen to have non-equal hashes). Is this a sufficient test? With regards to Array, I have added the implementation to stdlib/public/core/Arrays.swift.gyb. Here I have also followed the style for Equatable cond. conf. so my implementation is added for both ContiguousArray, ArraySlice and Array. Does this choice make sense? I am uncertain. With regards to Dictionary, the implementation is added to stdlib/public/core/HashedCollections.swift.gyb - where the (unconditional) conformance for Set already resides. Here I am a bit uncertain as to whether I need special cases for cocoa vs. native Dictionaries - or whether my more 'naive' implementation is fine. For both Array and Dictionary I have no clue as to where I should add the tests. Regarding the build/test process: Is the easiest way to build/test to: 1. Follow build instructions 2. Run initial test before making changes 3. After changing stdlib only, run ninja swift-stdlib from SWIFT\_BUILD\_DIR 4. Run utils/build-script --test from 'swift' dir Number 4 takes quite a lot of time. I have tried adding --test-paths test/stdlib/Optional.swift command line arg to build-script, but I'm guessing that's not the correct format, because it didn't appear to work. Anyone with experience in building and running tests for the swift project, please feel free to comment if I am on the right track or not. :-) Sincerely, /morten ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 28, 2018, 3:35pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/8 "2018-01-28T15:35:34Z")
One additional question: The Hashable conformance for Set includes a few FIXMEs. I don't know if I should copy these to my implementations since I do not understand them. :-| They are: ``` @_inlineable // FIXME(sil-serialize-all) ``` and ``` // FIXME(ABI)#177: Cache Set hashValue ``` Should similare fixmes be added for any of the implementations for Optional, the Array types and Dictionary? Sincerely, /morten ---
**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\ **Post date:** [January 29, 2018, 5:28pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/9 "2018-01-29T17:28:00Z")
> [@Morten\_Bek\_Ditlevsen](#): > > I have a few questions, but I don’t know if this is the correct forum to ask the questions in. Thanks for working on an implementation! There's a separate [standard library development category](https://forums.swift.org/c/development/stdlib) for questions like this, and you can also open a PR (prefixed with WIP) and ask for feedback that way. With the PR, it's a little easier to comment on specific parts of your code. > [@](#): > > For testing the Optional conditional conformance to Hashable, I have basically duplicated the tests for Equatable: > > OptionalTests.test("Hashable") { > expectEqual([true, false, false, false, false, true], testRelation { $0.hashValue == $1.hashValue }) > expectEqual([false, true, true, true, true, false], testRelation { $0.hashValue != $1.hashValue }) > } > > So this verifies that equal optionals have equal hashes (and for these specific values that the non-equal optionals also happen to have non-equal hashes). > > Is this a sufficient test? There's a `checkHashable` function that tests different aspects of the conformance—you can see how `Set` uses it in "validation-test/stdlib/Set.swift". > [@](#): > > With regards to Array, I have added the implementation to stdlib/public/core/Arrays.swift.gyb. > Here I have also followed the style for Equatable cond. conf. so my implementation is added for both ContiguousArray, ArraySlice and Array. Does this choice make sense? I am uncertain. Makes sense to me! Note that the way you're using `_mixInt` is commutative, so the hash value for `[1, 2, 3]` and `[3, 2, 1]` will end up the same. That makes sense for sets and dictionaries (where the order shouldn't affect equality or hashing) but for arrays you can use the `_combineHashValues` function instead. > [@](#): > > With regards to Dictionary, the implementation is added to stdlib/public/core/HashedCollections.swift.gyb - where the (unconditional) conformance for Set already resides. > > Here I am a bit uncertain as to whether I need special cases for cocoa vs. native Dictionaries - or whether my more ‘naive’ implementation is fine. > > For both Array and Dictionary I have no clue as to where I should add the tests. I think your naive implementation should be fine, as it follows what `Set` is already doing. Tests could go in "validation-tests/stdlib/Arrays.swift.gyb" and ".../Dictionary.swift". > [@](#): > > Number 4 takes quite a lot of time. I have tried adding --test-paths test/stdlib/Optional.swift command line arg to build-script, but I’m guessing that’s not the correct format, because it didn’t appear to work. Once you've built once for tests, you should be able to run subsequent tests individually with "utils/run-test". ---
**Author:** ![moiseev](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/moiseev/32/281_2.png) [@moiseev](https://forums.swift.org/u/moiseev)\ **Post date:** [January 29, 2018, 6:43pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/10 "2018-01-29T18:43:23Z")
> [@Morten\_Bek\_Ditlevsen](#): > > They are: > > @\_inlineable // FIXME(sil-serialize-all) > > and > > // FIXME(ABI)#177: \ Cache Set\ hashValue > > Should similare fixmes be added for any of the implementations for Optional, the Array types and Dictionary? Please copy the first on (`@_inlineable`), and in fact, please add this line to every new method/property that you add to the standard library. As for the second one, here is the text from that radar: > Computing the hashValue of a Set is O(n), so we should cache it and only update in mutating methods. If this applies to your new methods, it won't hurt to copy the `FIXME`. It will simplify the task of finding all the relevant places in code that should be updated. ---
**Author:** ![moiseev](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/moiseev/32/281_2.png) [@moiseev](https://forums.swift.org/u/moiseev)\ **Post date:** [January 29, 2018, 6:50pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/11 "2018-01-29T18:50:24Z")
> [@Morten\_Bek\_Ditlevsen](#): > > Is the easiest way to build/test to: > > Follow build instructions > Run initial test before making changes > After changing stdlib only, run ninja swift-stdlib from SWIFT\_BUILD\_DIR > Run utils/build-script --test from ‘swift’ dir Even when you only change the standard library, running `utils/build-script` is still fine. There is not too much overhead there. It might be a little better to invoke the `build-script` with `--skip-build-benchmarks --skip-test-cmark --release-debuginfo --debug-swift-stdlib`. This will avoid building unnecessary things, as well as speed up the stdlib build. ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 29, 2018, 7:55pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/12 "2018-01-29T19:55:14Z")
Hi Nate, Thanks for your reply - and for the pointer to the stdlib dev category. I updated the implementation to use \_combineHashValues. I looked at the implementation for Set for inspiration, but failed to realize that Set does naturally not have the ordering issue that Array does. Following advise from Xiaodi Wu the new implementation follows the example from the code that autosynthesizes Hashable support for enums and structs. I will have a look at testing, and then do a WIP-PR. Thanks! ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 29, 2018, 7:56pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/13 "2018-01-29T19:56:08Z")
Hi Max, Thanks - I will add the FIXMEs to the new methods too. ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 29, 2018, 8:13pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/14 "2018-01-29T20:13:27Z")
Regarding the commutativity: For Dictionaries, the dictionary values should be combined using \_combineHashValues too, right? Because [0: "a", 1: "b"] would otherwise hash equal to [0: "b", 1: "a"], right? In my current suggestion I use \_combineHashValues for all keys and values. But if the dictionary keys could be thought of as a Set, then all the keys could combined by xor'ing \_mixInts and the result of this could then be combined with all the values using \_combineHashes. I guess this would probably be a slight performance optimization, but would such an optimization be worthwile? I guess it's peanuts compared to caching the hash. ---
**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\ **Post date:** [January 29, 2018, 8:30pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/15 "2018-01-29T20:30:06Z")
> [@Morten\_Bek\_Ditlevsen](#): > > But if the dictionary keys could be thought of as a Set, then all the keys could combined by xor’ing \_mixInts and the result of this could then be combined with all the values using \_combineHashes. You could treat the dictionary as a set of (Key, Value) pairs. That is, for each (Key, Value) pair, use `_combineHashValues` on that key and its value, then merge the results as you would for a Set. ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 29, 2018, 8:58pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/17 "2018-01-29T20:58:39Z")
I have now added tests using checkHashable for Optional, Array and Dictionary. I have created a WIP PR: [https://github.com/apple/swift/pull/14247](https://github.com/apple/swift/pull/14247) Thanks for the pointers to running the tests much, much faster than I previously did, @nnnnnnnn and @moiseev. @Nevin right now I am still doing \_combineHashValues on all keys and values, but your suggestion would cut that use in half, so that sounds like a good idea. ---
**Author:** ![jawbroken](https://avatars.discourse-cdn.com/v4/letter/j/cc9497/32.png) [@jawbroken](https://forums.swift.org/u/jawbroken)\ **Post date:** [January 30, 2018, 3:47am UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/18 "2018-01-30T03:47:40Z")
Is that implementation for Dictionary correct? I haven't looked into the currently implementation, but I thought that the iteration order of key-value pairs in a Dictionary was undefined, i.e. equal Dictionaries may iterate in a different order, which would make your hash value unequal for equal dictionaries. See the implementation of Equatable for Dictionaries in that same file, for example. ---
**Author:** ![Morten\_Bek\_Ditlevsen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/morten_bek_ditlevsen/32/28133_2.png) [@Morten\_Bek\_Ditlevsen](https://forums.swift.org/u/Morten_Bek_Ditlevsen)\ **Post date:** [January 30, 2018, 5:10am UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/19 "2018-01-30T05:10:00Z")
Thanks a lot, jawbroken, that makes perfect sense. I will try adding a failing test for equal dictionaries traversed in different order, and then refactor to the suggested “consider each (k, v) as an element in a Set”. ---
**Author:** ![lorentey](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lorentey/32/1299_2.png) [@lorentey](https://forums.swift.org/u/lorentey)\ **Post date:** [January 30, 2018, 4:11pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/20 "2018-01-30T16:11:50Z")
Strong +1; types in the standard library should conform to `Hashable` whenever possible. Here are some additional types that could benefit from conditional `Hashable` conformance, in order of decreasing (subjective) importance: - `Range` and the partial range types - `Slice`, with caveat below - `DictionaryLiteral` - `CollectionOfOne` - `EmptyCollection` (I expect the last two would pop up mostly when they're used as constrained type parameters of generic types.) `Slice` supports unordered collections, so if we want to make it `Hashable`, we need to decide if lexicographic equality and ordered hashing is suitable for it. @nnnnnnnn has a convincing argument that it is: > [@Combining hashes](https://forums.swift.org/t/combining-hashes/9082/53): > > thinking I think slices of sets and dictionaries probably need to be order-dependent when we compare them. Those two types are "substitutable" for their primary use cases when equal, but definitely not for slicing operations. Indeed, a `Set.SubSequence` value is decidedly not substitutable with slices from other sets, even if they happen to contain the same elements. ---
**Author:** ![hlovatt](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/hlovatt/32/3044_2.png) [@hlovatt](https://forums.swift.org/u/hlovatt)\ **Post date:** [January 30, 2018, 10:09pm UTC](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046/21 "2018-01-30T22:09:49Z")
Other languages, e.g. Java, have set types that have the concept of order, either order of addition or are sorted. These order retaining sets if added to Swift should conform to Hashable since element order is known and similarly slices of these sets should also be Hashable. However an unordered set shouldn’t conform to Hashable since if the sets are equal, they contain the same elements, then they should have the same hash. Similarly slices of unordered sets shouldn’t be Hashable. [Next page](https://forums.swift.org/t/let-optional-dictionary-and-array-conditionally-conform-to-hashable/9046.md?page=2)