ENH: add data hashing routines
State: closed

xref https://github.com/dask/dask/pull/1807

Labels:
name: Enhancement
name: Numeric Operations
description: Arithmetic, Comparison, and Logical operations

Comments:
cc @mikegraham 
cc @jcrist 
cc @mrocklin

added ``index=True`` kw to by default hash the index.
With this broader goal in mind, it might be worth considering exactly what the applications are. This current implementation uses the `hash` builtin, so it will have hash randomization for strings for some Pythons. I don't know what the right move is there, but it's something to keep in mind.

There was a big discussion for the dask application about whether to handle the case where dtype was object but the objects weren't strings, and whether to handle strings in a way that was stable between runs. Part of what shaped that discussion was dask's refraining from introducing C extensions.
@mikegraham yes a stable string hash would be nice. (esp between runs). I don't think performance is an issue ATM (this is pretty fast). But can certainly deal with that if it comes up. Do you have a 'better' way of hashing strings?
should we be using ``hashlib``? https://www.peterbe.com/plog/best-hashing-function-in-python
```
(pandas) [Thu Nov 24 11:26:03 ~/pandas]$ python -c "import hashlib; print(int(hashlib.md5('foo'.encode('utf8')).hexdigest(), 16) % (10 ** 8))"
985560
```
I have seen this done. Its stable across runs & compat between python versions.
we could also always stringify ``object`` dtype data.
## [Current coverage](https://codecov.io/gh/pandas-dev/pandas/pull/14729?src=pr) is 85.28% (diff: 98.14%)
> Merging [#14729](https://codecov.io/gh/pandas-dev/pandas/pull/14729?src=pr) into [master](https://codecov.io/gh/pandas-dev/pandas/branch/master?src=pr) will increase coverage by **0.04%**

```diff
@@             master     #14729   diff @@
==========================================
  Files           143        144     +1   
  Lines         50849      50903    +54   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43343      43414    +71   
+ Misses         7506       7489    -17   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last update [837db72...f5e05a7](https://codecov.io/gh/pandas-dev/pandas/compare/837db725b147104be4b0e5cbfd49868971ee4f78...f5e05a7455446e7728a1c4cbd52b57d7195f630e?src=pr)
```
In [2]: df = tm.makeMixedDataFrame()

In [3]: df = pd.concat([df]*100000)

In [4]: df.info()
<class 'pandas.core.frame.DataFrame'>
Int64Index: 500000 entries, 0 to 4
Data columns (total 4 columns):
A    500000 non-null float64
B    500000 non-null float64
C    500000 non-null object
D    500000 non-null datetime64[ns]
dtypes: datetime64[ns](1), float64(2), object(1)
memory usage: 19.1+ MB

In [5]: df.hash()
Out[5]: 
array([ 7765496462383768478,  9003743364327424712, 10642375279821279843,
       ..., 10642375279821279843, 15490030136262591728,
        1988273298325137642], dtype=uint64)

In [6]: %timeit df.hash()
1 loop, best of 3: 995 ms per loop

```

note great about 1/2 time is spent in hashlib. but can work on that later.
> should we be using `hashlib`? 

It will be slow has heck. I have a Cython siphash implementation I can contribute if you want. This should also be able to be GIL-releasing.

> we could also always stringify object dtype data.

You mean `str(x)`? I don't think that's super valid -- it will often have unstable data (like the id) in it and will often not have real information about the object in it.
https://gist.github.com/mikegraham/feab49dd9a0ac98cc1fb26a3366e84e4
@mikegraham ok, using your cython code we now get about a 6x speedup. so 120ms for 500k rows.
couple of issues.

- ~~have to handle things like tuples (e.g. from a multiindex) / non-strings~~
- ~~the hash does not appear consistent. maybe I am doing something wrong. can you have a look.~~

ok, fixed the consistency issue. key has to be 16 long! hahha
and latest push makes this nogil!
ok, added tests for mixed dtypes, empty objects.
support for encoding and different hash_keys.

Timing is not bad

```
In [33]: len(s2)
Out[33]: 500000

In [34]: %timeit s2.hash()
10 loops, best of 3: 126 ms per loop
```

We can do even better by factorizing first & then hashing (so we wouldn't even need the object hashing code).
```
In [35]: %timeit Series(s2.factorize()[0]).hash()
10 loops, best of 3: 28 ms per loop
```

Is this a valid thing to do?

Acutally its not very hard to:

- categorize
- hash the categories
- broadcast back to the original.
are repeated hashes likely?
```
In [21]: N=1000000; s = pd.Series(tm.makeStringIndex(10).take(np.random.randint(0, 10, size=N)))

In [22]: c = s.astype('category')

In [23]: c.cat.categories
Out[23]: Index(['56bjQF4AsK', '8ZAYAT8GPT', 'AR3qPSViwT', 'I7RtoX1MVN', 'IlKrENATh1', 'QWnGtQeaPG', 'YhkZCbpQHJ', 'a7N5Sb78rE', 'fE08yrQbJ7', 'jVm54MmpWD'], dtype='object')

In [24]: c.cat.categories.hash()
Out[24]: 
array([16874492830844911956, 17129770899522711342, 16874492830844911956,
       17129770899522711342, 16874492830844911956, 17129770899522711342,
       16874492830844911956, 17129770899522711342, 16874492830844911956,
       17129770899522711342], dtype=uint64)
```

hmm, something funny going on........
```
In [27]: Index(['foo', 'bar', 'baz']).hash()
Out[27]: array([ 477881037637427054, 1374399572096150070,  477881037637427054], dtype=uint64)
```
nvm, was incorretly assigning the pointer.

```
In [1]: Index(['foo', 'bar', 'baz']).hash()
Out[1]: array([3600424527151052760, 1374399572096150070,  477881037637427054], dtype=uint64)
```
> We can do even better by factorizing first & then hashing (so we wouldn't even need the object hashing code).

That will make the hash only valid for one given series/df, I think, not between different dfs. I don't know what all the uses are for hashing, but for the dask uses, I think it wouldn't since the hash values for similar values wouldn't agree between partitions.
ok I categorize, hash, and re-broadcast (so its equivalent to the original), but we don't duplicate work.

```
In [1]: N=1000000; s = pd.Series(tm.makeStringIndex(10).take(np.random.randint(0, 10, size=N)))

In [2]: %timeit s.hash()
10 loops, best of 3: 63.4 ms per loop

In [4]: N=1000000; s = pd.Series(tm.makeStringIndex(1000).take(np.random.randint(0, 1000, size=N)))

In [5]: %timeit s.hash()
10 loops, best of 3: 80.7 ms per loop

In [6]: N=1000000; s = pd.Series(tm.makeStringIndex(100000).take(np.random.randint(0, 100000, size=N)))

In [7]: %timeit s.hash()
1 loop, best of 3: 309 ms per loop
```
and using some revised code (was sorting when factorizing, which is uncessary)

```
10 loops, best of 3: 59.6 ms per loop
10 loops, best of 3: 83 ms per loop
10 loops, best of 3: 174 ms per loop
```
Is there a planned release date for 1.19.2?  Planning dask.dataframe work.
schduled now for 12/16 about; I picked that because of the 3.6 release date. 
should I add this ``.sum()`` to the doc-string. I *think* this provides an effective way of getting a hash for an entire pandas object (something people occasionally ask for).

```
In [3]: pd.DataFrame({'A': [1, 2, 3], 'B': ['foo', 'bar', 'baz']}).hash()
Out[3]: array([11603696091789712533,  5345384428795788641,    46691607209239364], dtype=uint64)

In [4]: pd.DataFrame({'A': [1, 2, 3], 'B': ['foo', 'bar', 'baz']}).hash().sum()
Out[4]: 16995772127794740538

In [5]: pd.DataFrame({'A': [2, 2, 3], 'B': ['foo', 'bar', 'baz']}).hash().sum()
Out[5]: 11177462582024945927
```
@jorisvandenbossche @chris-b1 @TomAugspurger @sinhrks @wesm if any comments.
> should I add this .sum() to the doc-string. I think this provides an effective way of getting a hash for an entire pandas object (something people occasionally ask for).

The problem here is that `['a', 'b']` and `['b', 'a']` would hash to the same value, which is bad.  

Instead you could use something like the following:

```python
import hashlib
hashlib.sha256(result.data).hexdigest()

In [1]: import numpy as np

In [2]: import hashlib

In [3]: h = hashlib.sha256(np.ones(5).data)

In [4]: h.hexdigest()
Out[4]: '6e91e92205f42beb0df4ddf13cf0af352b29ffd2de9465348cdb1447a324e828'
```
actually, we do hash in a specific way (e.g. in column order), then the index if so indicated, so I *think* that these are a pretty good row wise data hash.

```
In [3]: pd.DataFrame({'A': [1, 2, 3], 'B': ['foo', 'bar', 'baz']}).hash()
Out[3]: array([11603696091789712533,  5345384428795788641,    46691607209239364], dtype=uint64)

In [4]: pd.DataFrame({'B': [1, 2, 3], 'A': ['foo', 'bar', 'baz']}).hash()
Out[4]: array([14224550840762107975, 10786791860424998761,  8249554186654362168], dtype=uint64)
```
`adder` is implemented in such a way that the hash is order-dependent.
@mikegraham 

> adder is implemented in such a way that it is order-dependent.

this is a feature!


Right, one I added, but I wasn't clear before that you had noticed while absorbing it ;)
@mikegraham 

> should I add this .sum() to the doc-string. I think this provides an effective way of getting a hash for an entire pandas object (something people occasionally ask for).

from my comment above, is this true?

@jreback under `sum()` would the following two hash to the same value?

```python
a = pd.Series([1, 2])
b = pd.Series([2, 1])
```