如何从整数向量生成唯一的哈希键？

Question

只是为了好玩，我正在尝试实施 A* 搜索以寻找解谜器。我想将到目前为止访问过的所有状态保存在哈希中。状态基本上是从 0 到 15 的整数向量。（我现在不会提供更多信息，以免破坏这个谜题。）

(defstruct posn
  "A posn is a pair struct containing two integer for the row/col indices."
  (row 0 :type fixnum)
  (col 0 :type fixnum))

(defstruct state
  "A state contains a vector and a posn describing the position of the empty slot."
  (matrix '#(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0) :type simple-vector)
  (empty-slot (make-posn :row 3 :col 3) :type posn))

因为我似乎必须检查 states 的大约 100.000s 我认为生成一些数字作为哈希键而不是直接使用状态会更有效并且需要使用 equal每次。

我从

开始

(defun gen-hash-key (state)
  "Returns a unique(?) but simple hash key for STATE which is used for tracking
if the STATE was already visited."
  (loop
     with matrix = (state-matrix state)
     for i from 1
     for e across matrix
     summing (* i e)))

但必须知道这不会导致真正唯一的哈希键。例如。向量 '#(14 1 4 6 15 11 7 12 9 10 3 0 13 8 5 2)) 和 '#(15 14 1 6 9 0 4 12 10 11 7 3 13 8 5 2)) 都会导致 940 导致 A* 搜索错过状态，因此破坏了我的整个想法。

在我继续以我的业余方式调整计算之前，我想问问是否有人可以指出一种有效生成真正唯一密钥的方法？我缺乏正规的 CS 教育，不知道是否有生成此类密钥的标准方法。

Answer 1

16个取值范围为0到15的整数可以用一个64位的整数来表示：64位除以16就是4位一个数，(expt 2 4)就是16。例如：

CL-USER> #(14 1 4 6 15 11 7 12 9 10 3 0 13 8 5 2)
#(14 1 4 6 15 11 7 12 9 10 3 0 13 8 5 2)

CL-USER> (loop
        for c across *
        for i = 1 then (* i 16)
          sum (* i c))
2705822978855101470

第二个向量：

CL-USER> #(15 14 1 6 9 0 4 12 10 11 7 3 13 8 5 2)
#(15 14 1 6 9 0 4 12 10 11 7 3 13 8 5 2)

CL-USER> (loop
        for c across *
        for i = 1 then (* i 16)
          sum (* i c))
2705880226411930095

您还可以预先计算所有因素：

CL-USER> (coerce (loop for i = 1 then (* i 16) repeat 16 collect i) 'vector)
#(1 16 256 4096 65536 1048576 16777216 268435456 4294967296 68719476736
  1099511627776 17592186044416 281474976710656 4503599627370496
  72057594037927936 1152921504606846976)

我不确定你从中得到了多少。请注意，如果您花费大量时间将数字转换为向量，那么不使用 equal 进行散列的好处可能会超过计算这些散列的成本。

Answer 2

您不需要创建一些特殊的哈希键：语言会为您完成！

特别是 equalp 在数组和结构上具有您想要的行为。

对于数组：

If two arrays have the same number of dimensions, the dimensions match, and the corresponding active elements are equalp. The types for which the arrays are specialized need not match; for example, a string and a general array that happens to contain the same characters are equalp. Because equalp performs element-by-element comparisons of strings and ignores the case of characters, case distinctions are ignored when equalp compares strings.

对于结构：

If two structures S1 and S2 have the same class and the value of each slot in S1 is the same under equalp as the value of the corresponding slot in S2.

并且 equalp 是 make-hash-table 的可用测试函数之一，这意味着您可以创建状态结构将正确散列的散列表。

如何从整数向量生成唯一的哈希键？

How to generate a unique hash key from a vector of integers?

hash

common-lisp