In Swift can I use a tuple as the key in a dictionary?

Question

I'm wondering if I can somehow use an x, y pair as the key to my dictionary

let activeSquares = Dictionary <(x: Int, y: Int), SKShapeNode>()

But I get the error:

Cannot convert the expression's type '<<error type>>' to type '$T1'

and the error:

Type '(x: Int, y: Int)?' does not conform to protocol 'Hashable'

So.. how can we make it conform?

Kimberleykimberli

+1. Do tuples as values work? – Vasomotor

I'm sure (x:Int,y:Int) is not a Hashable thing :) – Janik

@Vasomotor yes tuples as values work – Kimberleykimberli

@JasonCoco Why not? The hash could be hash(x) ^ hash(y). – Wrongly

@SiLo Not that they can't be hashed, but that they don't conform to Hashable, which is required for the key portion of the Swift Dictionary. I should have surrounded in code block, sorry :) – Janik

I think you should just make a struct type that is modeled this way and make it conform to Hashable. – Janik

I don't think tuples can be made to conform since they can't be extended. – Cheer

@sjeohp They can't, you would simple make a simple value type using a struct. – Janik

The reason that tuples cannot be used as keys (or specifically, are not hashable) is because they are not strictly immutable. If you define it using let, it is immutable, but if you define it using var, it is not. The hash used as a key in a dictionary MUST be immutable by the definition of a hash table, and as any kind of reasonable hash would directly depend on the values inside a container, a mutable container cannot be hashed (and likewise, an immutable container containing mutable objects cannot be reasonably hashed). – Echinoderm

There are, of course, languages that let you use mutable values as keys in dictionary/map objects (such as C++), but if you mutate an object used as a key, it becomes undefined behavior. Apple doesn't dig undefined behavior, so they took the Python approach and don't allow mutable containers to be hashed. You can of course get around this using, as others have suggested, your own container that conforms to Hashable, but as any reasonable hash is value-dependent, you're just asking for undefined behavior by working around the system this way, unless you make your container immutable. – Echinoderm

@Echinoderm The mutability of tuples is beside the point - they are value types, so, hashability aside, it would be an immutable copy of the tuple that got stored in the dictionary. The only issue is that tuples don't conform to Hashable and can't be extended to do so. Tuples are no more mutable than strings or Ints, which are just fine as Dictionary keys. – Cush

Answer 1

The definition for Dictionary is struct Dictionary<KeyType : Hashable, ValueType> : ..., i.e. the type of the key must conform to the protocol Hashable. But the language guide tells us that protocols can be adopted by classes, structs and enums, i.e. not by tuples. Therefore, tuples cannot be used as Dictionary keys.

A workaround would be defining a hashable struct type containing two Ints (or whatever you want to put in your tuple).

Untinged

Suppose I make a hashable struct unique across two Int properties. How should I map the combination of two ints to a unique hash? "x ^ y"? "x<<16 | y"? – Boley

Aww, this seems like such a total miss-out on what could have been an awesome language feature. I mean there's no reason that I can think of that they couldn't have made tuples implicitly hashable by combining the hashes of their components. It would have been a really swifty way to avoid two-dimensional dictionaries! – Admeasurement

Totally should be a feature, and I'd be surprised if a later version of Swift didn't add it (though v4 still doesn't have it). In Python, a tuple of hashables is automatically hashable. – Decongestant

This proposal has been accepted: github.com/apple/swift-evolution/blob/master/proposals/… – Bricklaying

@Admeasurement this is perhaps one reason why C++s usage of comparison is superior to hashing. Its easier to compose comparable operations for data structures like tuples. – Teets

There is currently an accepted evolution proposal to automatically add Hashable conformance to tuples (SE-0283). However, there has been some difficulty with the implementation. – Grekin

Answer 2

As mentioned in the answer above, it is not possible. But you can wrap tuple into generic structure with Hashable protocol as a workaround:

struct Two<T:Hashable,U:Hashable> : Hashable {
  let values : (T, U)

  var hashValue : Int {
      get {
          let (a,b) = values
          return a.hashValue &* 31 &+ b.hashValue
      }
  }
}

// comparison function for conforming to Equatable protocol
func ==<T:Hashable,U:Hashable>(lhs: Two<T,U>, rhs: Two<T,U>) -> Bool {
  return lhs.values == rhs.values
}

// usage:
let pair = Two(values:("C","D"))
var pairMap = Dictionary<Two<String,String>,String>()
pairMap[pair] = "A"

Tonedeaf

Can you explain what the &* 31 &+ part does? – Admeasurement

&* and &+ are like normal operations * and + but with overflow error protection (so in case of overflow no error is thrown) – Tonedeaf

In Swift 3, == has been moved to a static func inside the struct: static func ==<T: Hashable, U: Hashable>(...) -> Bool {} – Wedge

Fantastic answer. Using pairs is a great workaround for dealing with this problem in a general way. – Excuse

@Wedge Almost: static func ==(lhs: Two<T, U>, rhs: Two<T, U>) -> Bool { ... } – Megasporophyll

As of swift 4.1, the hashable implementation can now be synthesized for you on a struct or enum that has values which are all hashable - just opt in by extending the Hashable protocol. See github.com/apple/swift-evolution/blob/master/proposals/…. In swift 4.2 there's also the hash(into:) function to handle combining hashes: github.com/apple/swift-evolution/blob/master/proposals/…. The dev docs are also updated, see "Conforming to the Hashable Protocol". – Brahmani

Answer 3

Unfortunately, as of Swift 4.2 the standard library still doesn't provide conditional conformance to Hashable for tuples and this is not considered valid code by the compiler:

extension (T1, T2): Hashable where T1: Hashable, T2: Hashable {
  // potential generic `Hashable` implementation here..
}

In addition, structs, classes and enums having tuples as their fields won't get Hashable automatically synthesized.

While other answers suggested using arrays instead of tuples, this would cause inefficiencies. A tuple is a very simple structure that can be easily optimized due to the fact that the number and types of elements is known at compile-time. An Array instance almost always preallocates more contiguous memory to accommodate for potential elements to be added. Besides, using Array type forces you to either make item types the same or to use type erasure. That is, if you don't care about inefficiency (Int, Int) could be stored in [Int], but (String, Int) would need something like [Any].

The workaround that I found relies on the fact that Hashable does synthesize automatically for fields stored separately, so this code works even without manually adding Hashable and Equatable implementations like in Marek Gregor's answer:

struct Pair<T: Hashable, U: Hashable>: Hashable {
  let first: T
  let second: U
}

Oppidan

This should be the correct answer. It does not rely on any magic numbers, yet retains generality. – Vouchsafe

Answer 4

No need special code or magic numbers to implement Hashable

Hashable in Swift 4.2:

struct PairKey: Hashable {

    let first: UInt
    let second: UInt

    func hash(into hasher: inout Hasher) {
        hasher.combine(self.first)
        hasher.combine(self.second)
    }

    static func ==(lhs: PairKey, rhs: PairKey) -> Bool {
        return lhs.first == rhs.first && lhs.second == rhs.second
    }
}

More info: https://nshipster.com/hashable/

Organon

Answer 5

I created this code in an app:

struct Point2D: Hashable{
    var x : CGFloat = 0.0
    var y : CGFloat = 0.0

    var hashValue: Int {
        return "(\(x),\(y))".hashValue
    }

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

struct Point3D: Hashable{
    var x : CGFloat = 0.0
    var y : CGFloat = 0.0
    var z : CGFloat = 0.0

    var hashValue: Int {
        return "(\(x),\(y),\(z))".hashValue
    }

    static func == (lhs: Point3D, rhs: Point3D) -> Bool {
        return lhs.x == rhs.x && lhs.y == rhs.y && lhs.z == rhs.z
    }

}

var map : [Point2D : Point3D] = [:]
map.updateValue(Point3D(x: 10.0, y: 20.0,z:0), forKey: Point2D(x: 10.0, 
y: 20.0))
let p = map[Point2D(x: 10.0, y: 20.0)]!

Stuartstub

Nice example 👍 – Choose

Answer 6

If you don't mind a bit of inefficiency, you can easily convert your tuple to a string and then use that for the dictionary key...

var dict = Dictionary<String, SKShapeNode>() 

let tup = (3,4)
let key:String = "\(tup)"
dict[key] = ...

Clara

Answer 7

You can't yet in Swift 5.3.2, But you can use an Array instead of tuple:

var dictionary: Dictionary<[Int], Any> = [:]

And usage is simple:

dictionary[[1,2]] = "hi"
dictionary[[2,2]] = "bye"

Also it supports any dimentions:

dictionary[[1,2,3,4,5,6]] = "Interstellar"

Contraband

As Max already said in this answer, using an [Int] instead of (Int, Int) comes with a number of caveats. – Vouchsafe

Answer 8

I suggest to implement structure and use solution similar to boost::hash_combine.

Here is what I use:

struct Point2: Hashable {

    var x:Double
    var y:Double

    public var hashValue: Int {
        var seed = UInt(0)
        hash_combine(seed: &seed, value: UInt(bitPattern: x.hashValue))
        hash_combine(seed: &seed, value: UInt(bitPattern: y.hashValue))
        return Int(bitPattern: seed)
    }

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

func hash_combine(seed: inout UInt, value: UInt) {
    let tmp = value &+ 0x9e3779b97f4a7c15 &+ (seed << 6) &+ (seed >> 2)
    seed ^= tmp
}

It's much faster then using string for hash value.

If you want to know more about magic number.

Glyoxaline

Answer 9

Add extension file to project (View on gist.github.com):

extension Dictionary where Key == Int64, Value == SKNode {
    func int64key(_ key: (Int32, Int32)) -> Int64 {
        return (Int64(key.0) << 32) | Int64(key.1)
    }

    subscript(_ key: (Int32, Int32)) -> SKNode? {
        get {
            return self[int64key(key)]
        }
        set(newValue) {
            self[int64key(key)] = newValue
        }
    }
}

Declaration:

var dictionary: [Int64 : SKNode] = [:]

Use:

var dictionary: [Int64 : SKNode] = [:]
dictionary[(0,1)] = SKNode()
dictionary[(1,0)] = SKNode()

Selfexcited

Answer 10

Or just use Arrays instead. I was trying to do the following code:

let parsed:Dictionary<(Duration, Duration), [ValveSpan]> = Dictionary(grouping: cut) { span in (span.begin, span.end) }

Which led me to this post. After reading through these and being disappointed (because if they can synthesize Equatable and Hashable by just adopting the protocol without doing anything, they should be able to do it for tuples, no?), I suddenly realized, just use Arrays then. No clue how efficient it is, but this change works just fine:

let parsed:Dictionary<[Duration], [ValveSpan]> = Dictionary(grouping: cut) { span in [span.begin, span.end] }

My more general question becomes "so why aren't tuples first class structs like arrays are then? Python pulled it off (duck and run)."

Recorder

Answer 11

Deeply inspired by previous answers here, in Swift 5.10 this worked well for me.

struct hashable_pair<T1: Hashable, T2: Hashable>: Hashable {
    let t1: T1
    let t2: T2
}

usage:

var myDict: Dictionary<hashable_pair<MyType, MyOtherType>, ValueType>
...
let key = hashable_pair<MyType, MyOtherType>(t1: instanceOfMyType, t2: instanceOfMyOtherType)
...

Harvest

Answer 12

struct Pair<T:Hashable> : Hashable {
    let values : (T, T)
    
    init(_ a: T, _ b: T) {
        values = (a, b)
    }
    
    static func == (lhs: Pair<T>, rhs: Pair<T>) -> Bool {
        return lhs.values == rhs.values
    }
    
    func hash(into hasher: inout Hasher) {
        let (a, b) = values
        hasher.combine(a)
        hasher.combine(b)
    }
}

let myPair = Pair(3, 4)

let myPairs: Set<Pair<Int>> = set()
myPairs.update(myPair)

Pleat