通过散列值访问 Swift 个集合元素

Question

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

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 集没有通过哈希值获取其中一个元素的函数。我能想到的就是

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

...但显然，这是线性时间运行，而不是常数时间。

解决这个问题的一种方法是不使用集合，而是使用数组：

var pieces: [Piece?]

然后我可以在恒定时间内简单地使用 pieces[25] 访问某个位置的片段。我确实觉得这不太优雅，因为这种方法将每个 Piece 的位置存储两次：通过 pieces 数组中的位置以及 row 和 column 的值变量。

有没有办法通过哈希值（在恒定时间内）访问集合元素？还是我应该只使用数组？

Answer 1

我会坚持使用数组。

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.

如果您可以通过散列访问集合中的值（您不能），您将遇到相同的问题，即值被存储两次。数组将是访问元素的更好方式。

// array
pieces[25]

// set (not possible)
pieces.elementWithHash(25)

实际上我会将其更改为使用二维数组，因为它对您正在访问的内容更具可读性。

var pieces: [[Piece?]]
pieces[3][1]

Answer 2

或者你可以这样做：

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

您正在扫描一个 8x8 的棋盘。不再担心复杂性。

Answer 3

序言：

因为有 64 个正方形，所以最好选择一组可选的棋子
通常，您使用带有 Int 键的字典作为稀疏数组（参见下面的示例）
您不应该单独将 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[[=10=].location] = [=10=]
        }
    }
}

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

Answer 4

为了让它更优雅，我会在 Board 结构中添加一个下标。

struct Board {

  var grid: [Piece?]
  let rows: Int, columns: Int

  init(rows: Int, columns: Int) {
    self.rows = rows
    self.columns = columns
    grid = [Piece?](count: rows * columns, repeatedValue: nil)
  }

  func isValidIndex(row: Int, column: Int) -> Bool {
    return row >= 0 && row < rows && column >= 0 && column < columns
  }

  subscript(row: Int, column: Int) -> Piece? {
    get {
      assert(isValidIndex(row, column: column), "Index out of range")
      return grid[(row * columns) + column]
    }
    set(newValue) {
      assert(isValidIndex(row, column: column), "Index out of range")
      grid[(row * columns) + column] = newValue
    }
  }
}

还有 get/set 个这样的作品：

var board = Board(rows: 8, columns: 8)
board[0, 1] = Piece(player: .White, type: .King)
board[0, 2] // nil

Answer 5

在恒定时间内通过 hashValue 获取 Set 中的元素通常是不可能的，因为用于计算 hashValue 的属性可能会改变（例如 Piece 移动）并且 Set 不知道这是什么时候发生的。如果 Set 能以某种方式知道，那么它可能能够将元素存储在相对于 hashValue 的新位置，以允许后续不断查找。基本上，如果将它们放入 [Position: Piece] 字典中，并且每一步都使用 added/removed 键，那么这就是您要做的。

在这种情况下，一个简单的数组可能是最好的解决方案。至于数组浪费space，这是space–time tradeoff.

的经典案例

通过散列值访问 Swift 个集合元素

Accessing Swift set elements by their hash value

hash

set

swift