通过其哈希值访问Swift set元素 [英] Accessing Swift set elements by their hash value

问题描述

假设我正在制作一个国际象棋应用程序，其中的位置存储如下:

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的定义如下:

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

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

Player和PieceType是简单的枚举:

enum Player {
    case White, Black
}

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

现在，我想按其在板上的位置访问Position中的Piece. Piece的哈希值由其位置唯一确定，因此应该可以在恒定时间内访问Piece.但是，Swift集不具有通过其哈希值获取其元素之一的功能.我所能想到的就是

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?]

然后我可以用pieces[25]恒定时间访问特定位置的作品.我确实发现它不太优雅，因为此方法将每个Piece的位置存储两次:通过pieces数组中的位置以及通过row和column变量的值.

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.

是否有一种方法可以通过其散列值(恒定时间)访问set元素?还是应该只使用数组?

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

推荐答案

序言:

1. 因为有64个正方形，所以最好是由可选件组成的阵列
2. 通常，您使用带有Int键的字典作为稀疏数组(请参见下面的示例)
3. 您不应仅将hashValue用于位置，因为它应考虑所有属性(在下面的示例中，我将位置更改为位置)-尽管在这种情况下，我知道除了短暂地没有2个块可以具有相同的位置，因此可能还可以

我该如何编码:

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

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

struct Board {
    var pieces = [Int : Piece]()

    init(pieces: Piece...) {
        pieces.forEach {
            self.pieces[$0.location] = $0
        }
    }
}

let whiteKing = Piece(row: 0, column: 4, player: .White, type: .King)
let blackKing = Piece(row: 7, column: 3, player: .Black, type: .King)

let board = Board(pieces: whiteKing, blackKing)

board.pieces // [4: {row 0, column 4, White, King}, 59: {row 7, column 3, Black, King}]

这篇关于通过其哈希值访问Swift set元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！