Repository: pandas-dev/pandas
Pull request: Modify hash(pd.NA) to avoid integer hash collisions
- [X] closes #30013
- [X] tests added / passed
- [X] passes `black pandas`
- [X] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`

No whatsnew entry since this issue was never user facing.

Problem statement:
BUG: set/dict operations fail when hash collisions with pd.NA occur
```python-traceback
In [1]: import pandas as pd; pd.__version__
Out[1]: '0.26.0.dev0+1155.ged20822a5'

In [2]: {pd.NA, hash(pd.NA)}
---------------------------------------------------------------------------
TypeError: boolean value of NA is ambiguous

In [3]: {pd.NA} | {hash(pd.NA)}
---------------------------------------------------------------------------
TypeError: boolean value of NA is ambiguous

In [4]: {pd.NA: 'foo', hash(pd.NA): 'bar'}
---------------------------------------------------------------------------
TypeError: boolean value of NA is ambiguous

In [5]: d = {pd.NA: 'foo'} 
   ...: d[hash(pd.NA)]
---------------------------------------------------------------------------
TypeError: boolean value of NA is ambiguous
```

The above behavior is due to Python using equality as a fallback when hash collisions occur and our defined behavior of `bool(pd.NA)` raising.  This might be something we have to live with if we want to maintain the current behavior of `bool(pd.NA)`, or at least an immediate workaround doesn't come to mind.

The examples above are admittedly a bit contrived, so I think it'd be fairly rare to see this occur in practice.  My main concern is that this could result in some confusing behavior when `pd.NA` is included in containers, e.g. `set(IntegerArray)` could fail in rare circumstances.

cc @jorisvandenbossche @TomAugspurger

Hints from issue discussion:
Hmmm, that is unfortunate. I also can't think of a workaround right now.
It doesn't sound like there is a workaround possible .. Hmm, I think I would classify this under "unfortunate side-effect", but we can certainly discuss the bool value to be False as well.
We could maybe adjust the `__hash__` definition to work around this, or at least minimize the potential issue.

It looks like the hashes for integers are no longer idempotent starting at `2**61 - 1`:
```python
In [1]: 2**61 - 2, hash(2**61 - 2)
Out[1]: (2305843009213693950, 2305843009213693950)

In [2]: 2**61 - 1, hash(2**61 - 1)
Out[2]: (2305843009213693951, 0)

In [3]: 2**61, hash(2**61)
Out[3]: (2305843009213693952, 1)
```

So if we modify `__hash__` to be at least `2**61 - 1` we should have a workaround for the integer case at least.

For example, I made the following change:
```diff
diff --git a/pandas/_libs/missing.pyx b/pandas/_libs/missing.pyx
index 9bf955ad3..23dabc58f 100644
--- a/pandas/_libs/missing.pyx
+++ b/pandas/_libs/missing.pyx
@@ -344,7 +344,7 @@ class NAType(C_NAType):
         raise TypeError("boolean value of NA is ambiguous")
 
     def __hash__(self):
-        return id(self)
+        return 2 ** 61 - 1
 
     # Binary arithmetic and comparison ops -> propagate
```

Which fixes the examples issues I originally described:
```python
In [2]: {pd.NA, hash(pd.NA)}
Out[2]: {2305843009213693951, NA}

In [3]: {pd.NA: 'foo', hash(pd.NA): 'foo'}
Out[3]: {NA: 'foo', 2305843009213693951: 'foo'}
```

The same issue will still occur for objects that have a hash collisions with `pd.NA`, so it's not like this fixes every possible case, but the change above look like it'll get us around the issue with integers at least.

Commit message: Modify hash(pd.NA) to avoid integer hash collisions

Patch to review:
diff --git a/pandas/_libs/missing.pyx b/pandas/_libs/missing.pyx
index 63aa5501c5250..8a6dd7d1c62eb 100644
--- a/pandas/_libs/missing.pyx
+++ b/pandas/_libs/missing.pyx
@@ -345,7 +345,8 @@ class NAType(C_NAType):
         raise TypeError("boolean value of NA is ambiguous")
 
     def __hash__(self):
-        return id(self)
+        # GH 30013: Ensure hash >= 2**61 - 1 to avoid hash collisions with integers
+        return 2 ** 61 - 1
 
     # Binary arithmetic and comparison ops -> propagate
 
diff --git a/pandas/tests/scalar/test_na_scalar.py b/pandas/tests/scalar/test_na_scalar.py
index 40db617c64717..82d5b097733f1 100644
--- a/pandas/tests/scalar/test_na_scalar.py
+++ b/pandas/tests/scalar/test_na_scalar.py
@@ -175,3 +175,20 @@ def test_series_isna():
     s = pd.Series([1, NA], dtype=object)
     expected = pd.Series([False, True])
     tm.assert_series_equal(s.isna(), expected)
+
+
+def test_integer_hash_collision_dict():
+    # GH 30013
+    result = {NA: "foo", hash(NA): "bar"}
+
+    assert result[NA] == "foo"
+    assert result[hash(NA)] == "bar"
+
+
+def test_integer_hash_collision_set():
+    # GH 30013
+    result = {NA, hash(NA)}
+
+    assert len(result) == 2
+    assert NA in result
+    assert hash(NA) in result


Code review comments:
diff_hunk: @@ -345,7 +345,8 @@ class NAType(C_NAType):
         raise TypeError("boolean value of NA is ambiguous")
 
     def __hash__(self):
-        return id(self)
+        # GH 30013: Ensure hash >= 2**61 - 1 to avoid hash collisions with integers
+        return 2 ** 61 - 1
path: pandas/_libs/missing.pyx
text: @author:
Note that this changes the previous behavior in that the hash will now be constant between python sessions, whereas previously `id(self)` would vary between sessions.  If we want to maintain the previous behavior we could instead do something like `id(self) + 2 ** 61`.

Also, I'm not super well versed in the conventions related to hashing, so it's possible that we might not want such a large hash value?

@user1:
I'm not sure either.

Does this still have similar issues with UInt64? Does `set(pd.Series([pd.NA, 2**61 - 1], dtype='UInt64'))` raise on your branch?

@author:
>  Does `set(pd.Series([pd.NA, 2**61 - 1], dtype='UInt64'))` raise on your branch?

I don't anticipate having problems with uint64 since numpy looks to be following the same hashing conventions as python in terms of integers:
```python
In [2]:  hash(2**61 - 1), hash(np.int64(2**61 - 1)), hash(np.uint64(2**61 - 1))
Out[2]: (0, 0, 0)
```
Can't directly test your suggestion on my branch since `pd.NA` in `IntegerArray` isn't in `master` yet, but I applied the hash change to your branch and it works:
```python
In [1]: import numpy as np; import pandas as pd; pd.__version__
Out[1]: '0.26.0.dev0+1294.gea19b2d81.dirty'

In [2]: set(pd.Series([pd.NA, 2**61 - 1], dtype='UInt64'))
Out[2]: {2305843009213693951, NA}

In [3]: set(pd.array([pd.NA, 2**61 - 1], dtype='UInt64'))
Out[3]: {2305843009213693951, NA}

In [4]: {pd.NA, np.uint64(2**61 - 1)}
Out[4]: {2305843009213693951, NA}

In [5]: hash(pd.NA) == np.uint64(2**61 - 1)
Out[5]: True
```

diff_hunk: @@ -345,7 +345,8 @@ class NAType(C_NAType):
         raise TypeError("boolean value of NA is ambiguous")
 
     def __hash__(self):
-        return id(self)
+        # GH 30013: Ensure hash >= 2**61 - 1 to avoid hash collisions with integers
+        return 2 ** 61 - 1
path: pandas/_libs/missing.pyx
text: @user1:
this is exceeds np.int32 max so on int32 platforms this doesn't work.

```
In [7]: 2 ** 61 - 1                                                                                                                                       
Out[7]: 2305843009213693951

In [8]: np.iinfo(np.int32).max                                                                                                                            
Out[8]: 2147483647

```

@user2:
> this is exceeds np.int32 max so on int32 platforms this doesn't work.

wouldnt the same affect pd.NaT?

@user1:
hmm maybe that’s right

@author:
It looks like the integer hashing behavior is slightly different on 32-bit platforms, and resets at `2**31 - 1` instead of `2**61 - 1`, so I've updated the hash accordingly for 32-bit platforms.