Accessing Swift set elements by their hash value

Question

Say I'm making a chess app, in which a position is stored like this:

struct Position {
    var pieces: Set<Piece>
    // some other stuff
}

Piece is defined as follows:

struct Piece: Hashable {
    var row: Int
    var column: Int
    let player: Player
    let type: PieceType

    var hashValue: Int {
        return 8 * row + column
    }
}

Player and PieceType are simple enums:

enum Player {
    case White, Black
}

enum PieceType {
    case Queen, King, ...
}

Now, I would like to access a Piece in a Position by its position on the board. The hash value of a Piece is uniquely determined by its position, so access to a Piece should be possible in constant time. However, a Swift set doesn't have a function to get one of its elements by its hash value. All I could come up with is

for piece in pieces {
    if piece.hashValue == 25 {
        // do something
    }
}

...but obviously, this runs in linear time, not in constant time.

A way to solve this problem is to not use a set, but an array instead:

var pieces: [Piece?]

Then I can access the piece at a certain position simply with pieces[25], in constant time. I do find this less elegant, because this method stores the position of each Piece twice: by the position in the pieces array and by the values of the row and column variables.

Is there a way to access a set element by its hash value (in constant time)? Or should I just use an array?

Answer 1

Or you can do:

let piece = pieces.filter { $0.hashValue == 25 }[0]

You are scanning an 8x8 chessboard. Stop worrying about complexity.

Answer 2

Getting an element in a Set by it's hashValue in constant time generally wouldn't be possible since the properties used to compute the hashValue might change (e.g. the Piece moves) and the Set doesn't know when this has happened. If the Set could know somehow then it might be able to store the element in a new location with respect to the hashValue to allow subsequent constant lookups. Basically that's what you would be doing if you put them in a [Position: Piece] dictionary and added/removed keys for every move.

In this case a simple array is probably the best solution. As for the array wasting space, it's a classic case of a space–time tradeoff.