对于numpy数组，最有效的哈希属性是什么？

Question

为了缓存目的, 我需要能够将一个numpyarray存储在一个dict中。哈希速度很重要。

该array表示索引，因此对象的实际标识并不重要，而其值是重要的。由于我只关心当前值，因此可变性不是问题。

为了将其存储在dict中，应该对什么进行哈希处理？

我的当前方法是使用str(arr.data)，在我的测试中比md5更快。

---

为了得到相对时间的概念，我引用了一些答案中的示例：

In [121]: %timeit hash(str(y))
10000 loops, best of 3: 68.7 us per loop

In [122]: %timeit hash(y.tostring())
1000000 loops, best of 3: 383 ns per loop

In [123]: %timeit hash(str(y.data))
1000000 loops, best of 3: 543 ns per loop

In [124]: %timeit y.flags.writeable = False ; hash(y.data)
1000000 loops, best of 3: 1.15 us per loop

In [125]: %timeit hash((b*y).sum())
100000 loops, best of 3: 8.12 us per loop

看起来对于这个特定的用例（小数组索引），arr.tostring 提供了最佳性能。

虽然对只读缓冲区进行哈希运算本身很快，但设置可写标志的开销实际上使其变慢了。

- sapi

---

arr.tostring()执行相同的操作，而且更美观。如果您有非常大的数组，可以尝试仅将数组的一小部分字符串化。 - root

tostring 看起来对于小型数组的速度快了几个数量级（虽然在有 10000 个元素的数组中慢了 4 倍）。 - Fred Foo

这其实是很明显的，因为str只会格式化数组的开头和结尾。 - Fred Foo

我有错还是 str(arr.data) 是错误的？我在不同的数组上使用它，得到了相同的字符串...!? - Make42

Answer 1

您可以简单地对底层缓冲区进行哈希处理，如果您将其设置为只读：

>>> a = random.randint(10, 100, 100000)
>>> a.flags.writeable = False
>>> %timeit hash(a.data)
100 loops, best of 3: 2.01 ms per loop
>>> %timeit hash(a.tostring())
100 loops, best of 3: 2.28 ms per loop

对于非常大的数组，hash(str(a)) 的速度要快得多，但它只考虑了数组的一小部分。

>>> %timeit hash(str(a))
10000 loops, best of 3: 55.5 us per loop
>>> str(a)
'[63 30 33 ..., 96 25 60]'

- Fred Foo

---

在Python 3.4中，我发现我必须使用hash(a.data.tobytes())。 - ariddell

抱歉回复晚了，但按照@ariddell的建议使用hash(a.data.tobytes())意味着我不需要设置a.flags.writeable = false。这样做是否有什么特殊原因和可能存在的问题？ - SCB

注意：使用此方法计算的哈希值在进程之间会发生变化。例如，在不同的Python进程中，hash(np.array([0,1]).data.tobytes())的值是不同的。它不是从数组内容计算出来的确定性值。为了获得确定性行为，您需要设置PYTHONHASHSEED环境变量。更多信息请参考：https://dev59.com/QF4c5IYBdhLWcg3wzs6Q - Harald Thomson

使用hash(str(a))对于较长的数组是危险的，因为只有数组的缩短字符串表示被散列，即'[63 30 33 ..., 96 25 60]（这也可能是该方法更快的原因？）。 特别地，所有具有相同起始和结束值的数组a最终都会具有相同的哈希值。请在我们的回答中添加一条简短的注意事项。 - Tobias Windisch

如果您使用 hashlib，您将会得到一个确定性的值，并且不需要将数组设置为只读。此外，该操作不受任何格式的限制：hashlib.sha256(a.data)。 - Jann Poppinga

Answer 2

你可以尝试使用 Python binding 来通过 xxhash 进行操作。对于大型数组而言，这比使用 hash(x.tostring()) 更快。

下面是一个 IPython 会话示例：

>>> import xxhash
>>> import numpy
>>> x = numpy.random.rand(1024 * 1024 * 16)
>>> h = xxhash.xxh64()
>>> %timeit hash(x.tostring())
1 loops, best of 3: 208 ms per loop
>>> %timeit h.update(x); h.intdigest(); h.reset()
100 loops, best of 3: 10.2 ms per loop

顺便说一下，在各种博客和Stack Overflow的答案中，您会看到人们使用sha1或md5作为哈希函数。出于性能原因，这通常是不可接受的，因为这些“安全”哈希函数速度较慢。它们仅在哈希冲突是最重要的问题之一时有用。

尽管如此，哈希冲突经常发生。如果您只需要实现__hash__以使数据数组对象可以用作Python字典或集合中的键，我认为更好的方法是集中精力提高__hash__本身的速度，并让Python处理哈希冲突[1]。

[1] 您可能还需要覆盖__eq__，以帮助Python管理哈希冲突。您希望__eq__返回一个布尔值，而不是像numpy一样返回一个布尔数组。

- Cong Ma

---

我认为非加密哈希也会尝试防止“普通”数据的冲突，对吗？加密部分是指恶意攻击者不能更有可能找到冲突或了解哈希对象。所以就像这个答案所说的那样，在性能成为问题而安全性不是问题时，绝对不要使用sha1或md5。 - Mark

第四行应该是 h = xxhash.xxh64()。 - Micah Smith

@MicahSmith 谢谢。已修复。 - Cong Ma

Python中的xxhash有一个限制，大约为2 ** 32字节，因此您可能需要将数组分块并使用类似以下链接的方法组合哈希：https://dev59.com/oHVD5IYBdhLWcg3wBm1g - nimish

请注意，xxhash 是确定性的，并且对于不同的 Python 进程产生相同的结果。这在 hash 中并非如此（默认情况下），因为它为每个新进程使用随机种子。请参阅 Harald Thomson 的评论或此 SO 线程。 - normanius

Answer 3

如果你的np.array()很小并且在一个紧密的循环中使用，那么一种选择是完全跳过hash()，直接将np.array().data.tobytes()作为你的字典键使用：

grid  = np.array([[True, False, True],[False, False, True]])
hash  = grid.data.tobytes()
cache = cache or {}
if hash not in cache:
    cache[hash] = function(grid)
return cache[hash]

- James McGuigan

---

这个对我来说非常有效。记住，无论如何，字典都会为你的键进行哈希处理，因此只要数组很小，内存不是太大的问题，这是一个很好的选择。 - gregamis

Answer 4

虽然有点晚了，但是对于大数组，我认为一个不错的方法是随机抽样矩阵并对该样本进行哈希处理：

def subsample_hash(a):
    rng = np.random.RandomState(89)
    inds = rng.randint(low=0, high=a.size, size=1000)
    b = a.flat[inds]
    b.flags.writeable = False
    return hash(b.data)

我认为这比使用hash(str(a))更好，因为后者可能会混淆在中间具有唯一数据但边缘为零的数组。

- hunse

---

使用one-hot编码的人会感到失望。 - user48956

@user48956：是的，当您拥有稀疏数据（包括one-hot编码数据）时，任何从矩阵的密集版本中工作的方法都会是次优的（对整个矩阵进行哈希处理会很慢，而仅对部分进行哈希处理可能会错过非零数据值）。最好从数据的稀疏表示（即非零元素的索引和值）开始工作，并对索引和值进行哈希处理。 - hunse

Answer 5

你有什么样的数据？

• 数组大小
• 在数组中是否有多个索引

如果你的数组仅由索引的置换组成，那么可以使用基本转换。

(1, 0, 2) -> 1 * 3**0 + 0 * 3**1 + 2 * 3**2 = 10(base3)

并使用'10'作为哈希键通过

import numpy as num

base_size = 3
base = base_size ** num.arange(base_size)
max_base = (base * num.arange(base_size)).sum()

hashed_array = (base * array).sum()

现在，您可以使用一个数组(shape=(base_size, ))来访问值，而不是使用字典。

- Hensing

---

为什么要用列表推导式？在 NumPy 中可以更快地完成此操作，如 base_size ** np.arange(base_size)。 - Fred Foo

有趣的方法，虽然在小数组上速度较慢。如果我需要处理大型数据，我会记住这个方法的 :) - sapi