Set-uniqueness of instances with distinct hashValue

Using Swift
1

Given an array of instances of a `Hashable` value type, all equal according to `Equatable` protocol, but with distinct `hashValue`s, I would expect that initialising a set with that array would preserve all the instances. Instead, running the code below in an iOS playground on Xcode 8.0 (8A218a), results in a behaviour that I cannot explain. If anyone can, I’d be very grateful!

     struct X: Hashable {
         let x: Int
         let hashValue: Int

         static func == (lhs: X, rhs: X) -> Bool {
             return lhs.x == rhs.x
         }
     }

     let array: = (1...100).map{ X(x: 7, hashValue: $0) } // unique hash values
     array.count //→ 100

     let set = Set(array)
     set.count //→ 43

     let set2 = Set(Array(set))
     set2.count //→ 30

     let set3 = Set(Array(set2))
     set3.count //→ 30

     set3.sorted{ $0.hashValue < $1.hashValue }
         .forEach{ print(String($0.hashValue, radix: 2), "=", $0.hashValue) } /*→
            1 = 1
           11 = 3
          101 = 5
         1111 = 15
        10010 = 18
        10011 = 19
        11000 = 24
        11101 = 29
        11111 = 31
       100000 = 32
       100011 = 35
       100100 = 36
       100110 = 38
       101000 = 40
       101001 = 41
       101011 = 43
       101111 = 47
       110010 = 50
       110101 = 53
       111101 = 61
      1000010 = 66
      1001011 = 75
      1001101 = 77
      1001111 = 79
      1010000 = 80
      1011001 = 89
      1011100 = 92
      1011110 = 94
      1011111 = 95
      1100010 = 98
     */

Many thanks,

milos

2

Equal hashables must have the same hashValue. If you violate this rule,
all bets are off. As the doc says:

  A hash value, provided by a type's hashValue property, is an integer
  that is the same for any two instances that compare equally. That is,
  for two instances a and b of the same type, if a == b then a.hashValue
  == b.hashValue.

···

on Sun Oct 23 2016, milos <swift-users-AT-swift.org> wrote:

Given an array of instances of a `Hashable` value type, all equal
according to `Equatable` protocol, but with distinct `hashValue`s,

--
-Dave

3

If you change the “==“ function to:

func == (lhs: X, rhs: X) -> Bool {
    return (lhs.x == rhs.x) && (lhs.hashValue == rhs.hashValue)
}

then the example works as expected.

Apple says this: “A hash value, provided by a type’s hashValue property, is an integer that is the same for any two instances that compare equally.”

You violated this rule in the original example.

Apple says: “Set and dictionary performance depends on hash values that minimize collisions for their associated element and key types, respectively.”

From which I draw the conclusion that there are “under the hood” optimizations at work that produce the results in your example. These can probably change from compiler version to compiler version and are principally unreliable because your example violated the rule for Hashable.

Rien.

···

On 23 Oct 2016, at 10:51, milos via swift-users <swift-users@swift.org> wrote:

Given an array of instances of a `Hashable` value type, all equal according to `Equatable` protocol, but with distinct `hashValue`s, I would expect that initialising a set with that array would preserve all the instances. Instead, running the code below in an iOS playground on Xcode 8.0 (8A218a), results in a behaviour that I cannot explain. If anyone can, I’d be very grateful!

   struct X: Hashable {
       let x: Int
       let hashValue: Int

       static func == (lhs: X, rhs: X) -> Bool {
           return lhs.x == rhs.x
       }
   }

   let array: = (1...100).map{ X(x: 7, hashValue: $0) } // unique hash values
   array.count //→ 100

   let set = Set(array)
   set.count //→ 43

   let set2 = Set(Array(set))
   set2.count //→ 30

   let set3 = Set(Array(set2))
   set3.count //→ 30

   set3.sorted{ $0.hashValue < $1.hashValue }
       .forEach{ print(String($0.hashValue, radix: 2), "=", $0.hashValue) } /*→
          1 = 1
         11 = 3
        101 = 5
       1111 = 15
      10010 = 18
      10011 = 19
      11000 = 24
      11101 = 29
      11111 = 31
     100000 = 32
     100011 = 35
     100100 = 36
     100110 = 38
     101000 = 40
     101001 = 41
     101011 = 43
     101111 = 47
     110010 = 50
     110101 = 53
     111101 = 61
    1000010 = 66
    1001011 = 75
    1001101 = 77
    1001111 = 79
    1010000 = 80
    1011001 = 89
    1011100 = 92
    1011110 = 94
    1011111 = 95
    1100010 = 98
   */

Many thanks,

milos

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users