95

I need to be able to store a numpy array in a dict for caching purposes. Hash speed is important.

The array represents indicies, so while the actual identity of the object is not important, the value is. Mutabliity is not a concern, as I'm only interested in the current value.

What should I hash in order to store it in a dict?

My current approach is to use str(arr.data), which is faster than md5 in my testing.


I've incorporated some examples from the answers to get an idea of relative times:

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

It would appear that for this particular use case (small arrays of indicies), arr.tostring offers the best performance.

While hashing the read-only buffer is fast on its own, the overhead of setting the writeable flag actually makes it slower.

4
  • 2
    arr.tostring() does the same and is more aesthetically pleasing. If you have really big arrays you could try stringifying only a small part of the array.
    – root
    May 16, 2013 at 14:45
  • 1
    tostring also appears to be orders of magnitude faster for small arrays (although 4× slower for an array of 10000 elements).
    – Fred Foo
    May 16, 2013 at 15:49
  • 16
    ... which is actually quite obvious, because str only formats the head and tail of the array.
    – Fred Foo
    May 16, 2013 at 15:56
  • Am I mistaken or is str(arr.data) simply wrong? I used this on different arrays and got the same strings back...!?
    – Make42
    Feb 6, 2021 at 17:50

5 Answers 5

74

You can simply hash the underlying buffer, if you make it read-only:

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

For very large arrays, hash(str(a)) is a lot faster, but then it only takes a small part of the array into account.

>>> %timeit hash(str(a))
10000 loops, best of 3: 55.5 us per loop
>>> str(a)
'[63 30 33 ..., 96 25 60]'
9
  • 57
    In Python 3.4 I found I had to use hash(a.data.tobytes())
    – ariddell
    Oct 16, 2014 at 2:41
  • 4
    Sorry for coming to this kind late, but using hash(a.data.tobytes()) as @ariddell suggested means I don't have to set a.flags.writeable = false. Any reason for this and any potential problems in doing so?
    – SCB
    Sep 30, 2015 at 9:11
  • 51
    Attention: The hash calculated with this method changes between processes. i.e. hash(np.array([0,1]).data.tobytes()) has a different value in different python process. It is not a deterministic value calculated from the array content. To get a deterministic behavior you need to set the PYTHONHASHSEED environment variable. More info: stackoverflow.com/questions/27522626/… Apr 16, 2018 at 14:03
  • 4
    Using hash(str(a)) is dangerous and leads to wrong results for long arrays, as only the shortened string representation of the array, namely '[63 30 33 ..., 96 25 60], is hashed (this is probably also the reason why this method is faster?). Particularly, all arrays a having the same starting and ending values end up with the same hash. Could you please add a short note on that in our answer? Jan 9, 2021 at 19:40
  • 4
    If you use hashlib you 1. will get a deterministic value and 2. don't have to set the array to read-only and 3. the operation is not restricted to any format: hashlib.sha256( a.data ). Nov 1, 2021 at 7:22
41

You can try xxhash via its Python binding. For large arrays this is much faster than hash(x.tostring()).

Example IPython session:

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

And by the way, on various blogs and answers posted to Stack Overflow, you'll see people using sha1 or md5 as hash functions. For performance reasons this is usually not acceptable, as those "secure" hash functions are rather slow. They're useful only if hash collision is one of the top concerns.

Nevertheless, hash collisions happen all the time. And if all you need is implementing __hash__ for data-array objects so that they can be used as keys in Python dictionaries or sets, I think it's better to concentrate on the speed of __hash__ itself and let Python handle the hash collision[1].

[1] You may need to override __eq__ too, to help Python manage hash collision. You would want __eq__ to return a boolean, rather than an array of booleans as is done by numpy.

5
  • I think non-cryptographic hashes also try to prevent collisions for 'normal' data, right? The crypto part is that a malicious attacker cannot be more likely to find a collision or know learn about the hashes object. So like this answer says, definitely don't use sha1 or md5 when performance is an issue and security is not.
    – Mark
    Nov 8, 2016 at 14:01
  • The fourth line should be h = xxhash.xxh64() Apr 12, 2017 at 14:30
  • 1
    @MicahSmith Thanks. Fixed.
    – Cong Ma
    Apr 13, 2017 at 3:34
  • xxhash from python has a limit of something like 2**32 bytes, so you may need to chunk up your array and combine the hashes using something like: stackoverflow.com/questions/113511/…
    – nimish
    Feb 3, 2018 at 18:26
  • 2
    Note that xxhash is deterministic and yields the same result for different python processes. This is not the case (by default) for hash, which uses a random seed for every new process. See Harald Thomson's comment or this SO thread.
    – normanius
    Mar 3, 2020 at 13:35
10

If your np.array() is small and in a tight loop, then one option is to skip hash() completely and just use np.array().data.tobytes() directly as your dict key:

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]
1
  • This works great for me. Remember, a dictionary is going to hash your keys anyway, so as long as the arrays are small and memory isn't too big a concern, this is a good choice.
    – gregamis
    Mar 6 at 17:54
8

Coming late to the party, but for large arrays, I think a decent way to do it is to randomly subsample the matrix and hash that sample:

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)

I think this is better than doing hash(str(a)), because the latter could confuse arrays that have unique data in the middle but zeros around the edges.

2
  • 3
    People doing one-hot coding will be sad.
    – user48956
    Oct 23, 2019 at 2:57
  • @user48956 : Yes, when you have sparse data (including one-hot coded data), any approach that works from the dense version of the matrix will be sub-optimal (hashing the whole thing would be slow, and hashing only part could miss the non-zero data values). Better to work from a sparse representation of the data (i.e. indices and values of the non-zero elements) and hash both the indices and values.
    – hunse
    Oct 24, 2019 at 17:23
2

What kind of data do you have?

  • array-size
  • do you have an index several times in the array

If your array only consists of permutation of indices you can use a base-convertion

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

and use '10' as hash_key via

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()

Now you can use an array (shape=(base_size, )) instead of a dict in order to access the values.

2
  • 1
    Why the list comprehension? This can be done much faster in NumPy as base_size ** np.arange(base_size).
    – Fred Foo
    May 16, 2013 at 15:46
  • Interesting approach, although slower for small arrays. I'll keep this in mind if I need to play with anything large :)
    – sapi
    May 16, 2013 at 21:13

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.