BUG: hashing datetime64 objects
State: closed

- [ ] closes #xxxx (Replace xxxx with the GitHub issue number)
- [ ] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) if fixing a bug or adding a new feature
- [ ] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [ ] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [ ] Added an entry in the latest `doc/source/whatsnew/vX.X.X.rst` file if fixing a bug or adding a new feature.

xref #50690 
this handles only cases where the relevant dt64 objects are within the pydatetime bounds.  to handle the remaining cases we need to port `astype_overflowsafe` or something like it.
<b>update</b>Now handles all cases, but only has tests for a couple within-pydatetime cases.

cc @seberg ideally we'll port this to numpy and make this `datetime64.__hash__`

cc @WillAyd

Labels:
name: Datetime
description: Datetime data dtype

Comments:
Nice job @jbrockmendel - love to see you stepping into the C world
Updated to handle cases outside pydatetime bounds.  The newly-handled cases are _not_ yet tested.
@seberg thoughts on the approach here?
>  If this is only used in Cython, then you could just put it there

This is called by kh_python_hash_func in this same file.  kh_python_hash_func is itself called from cython (but not other C files i think)
> If this is actually working on the object, then this is really patching over NumPy's hash?

We aren't setting `np.datetime64.__hash__ = this_new_thing` if that's what you're asking.  This is used in our indexing code when doing dict-like lookups that may encounter mixed-unit dt64s, pydatetimes, or Timestamps and needs to have those hashes match where appropriate.

> Also curious, if you are working on a datetime column itself (no interaction between units or Python objects) then I guess you would continue to use the integer value directly?

This is only for object-dtype.
@seberg any thoughts on how to move forward here?  this is a blocker for some other non-nano work, so we're likely to do _something_ and id much prefer it if you're on board.
Oh, didn't realize it was hanging on that.  I would prefer a scheme that doesn't iterate (and avoids modulo).  Maybe even using the structs values and a typical hashing algorithm, like what a tuple `(year, month, ...)` would give.

If you like that idea, I can give you a function that would get a hash from that (should be about 30-50 lines of C/cython code, stolen from Python, I have done that before internally in NumPy).

From what it sounds, it shouldn't matter too much if we find a better scheme in the future?  For the scalars (also in NumPy) it also seems like it might be nice if we would just cache things like the hash and even the full struct (if they exist), since memory bloat is likely not a huge issue for scalars?

Besides, that I suspect my only comment left is that moving the IMPORT out would be good, I can try to do that for you, or you just decide to keep it until a time someone fixes it up...
> If you like that idea, I can give you a function that would get a hash from that (should be about 30-50 lines of C/cython code, stolen from Python, I have done that before internally in NumPy).

That sounds great, thanks.

OK, here is a larger diff that should do the trick I think.  I also included moving the datetime import.

I do think it would probably make sense to munch together e.g. `minutes*60+seconds` for simplicity.  It might be good to make sure that whatever such calculation we do the result fits into 32bits.
Maybe the best would be to do that starting from the smallest unit and always much together until things might overflow?
(I honestly didn't think about it, can you give that a shot @jbrockmendel?)

<details>

```diff
diff --git a/pandas/_libs/khash_for_primitive_helper.pxi.in b/pandas/_libs/khash_for_primitive_helper.pxi.in
index d0934b3e0e..56743530e9 100644
--- a/pandas/_libs/khash_for_primitive_helper.pxi.in
+++ b/pandas/_libs/khash_for_primitive_helper.pxi.in
@@ -4,6 +4,11 @@ Template for wrapping khash-tables for each primitive `dtype`
 WARNING: DO NOT edit .pxi FILE directly, .pxi is generated from .pxi.in
 """
 
+# Hashing datetimes requires the datetime API be imported, this ensures it:
+from cpython.datetime cimport import_datetime
+
+import_datetime()
+
 {{py:
 
 # name, c_type
diff --git a/pandas/_libs/src/klib/khash_python.h b/pandas/_libs/src/klib/khash_python.h
index bd3011b9b1..e6f519b7a0 100644
--- a/pandas/_libs/src/klib/khash_python.h
+++ b/pandas/_libs/src/klib/khash_python.h
@@ -308,6 +308,15 @@ khuint32_t PANDAS_INLINE kh_python_hash_func(PyObject* key);
 #define _PandasHASH_XXROTATE(x) ((x << 13) | (x >> 19))  /* Rotate left 13 bits */
 #endif
 
+Py_uhash_t PANDAS_INLINE tuple_update_uhash(Py_uhash_t acc, Py_uhash_t lane)
+{
+    acc += lane * _PandasHASH_XXPRIME_2;
+    acc = _PandasHASH_XXROTATE(acc);
+    acc *= _PandasHASH_XXPRIME_1;
+    return acc;
+}
+
+
 Py_hash_t PANDAS_INLINE tupleobject_hash(PyTupleObject* key) {
     Py_ssize_t i, len = Py_SIZE(key);
     PyObject **item = key->ob_item;
@@ -318,9 +327,7 @@ Py_hash_t PANDAS_INLINE tupleobject_hash(PyTupleObject* key) {
         if (lane == (Py_uhash_t)-1) {
             return -1;
         }
-        acc += lane * _PandasHASH_XXPRIME_2;
-        acc = _PandasHASH_XXROTATE(acc);
-        acc *= _PandasHASH_XXPRIME_1;
+        acc = tuple_update_uhash(acc, lane);
     }
 
     /* Add input length, mangled to keep the historical value of hash(()). */
@@ -333,98 +340,32 @@ Py_hash_t PANDAS_INLINE tupleobject_hash(PyTupleObject* key) {
 }
 
 
-// TODO: if nanos is most common/important, might be most performant to
-// make that canonical and others cast to that?
-Py_hash_t PANDAS_INLINE hash_datetime_value_and_reso(npy_datetime value, NPY_DATETIMEUNIT unit, npy_datetimestruct* dts) {
-    // If we cannot cast to pydatetime, then the question is if there are
-    // other-resolution datetime64 objects that we might be equal to whose
-    // hashes we need to match. We let year-reso objects return value, and make
-    // higher-resolution cases responsible for checking of they match.
-    if (unit == NPY_FR_Y) {
-        if (value == -1) {
-            // https://github.com/pandas-dev/pandas/pull/50960#discussion_r1088695136
-            return -2;
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_M) {
-        if ((value % 12) == 0) {
-            return hash_datetime_value_and_reso(value / 12, NPY_FR_Y, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_W) {
-        if (dts->day == 1) {
-            value = (dts->year - 1970) * 12 + dts->month;
-            return hash_datetime_value_and_reso(value, NPY_FR_M, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_D) {
-        if ((value % 7) == 0) {
-            return hash_datetime_value_and_reso(value / 7, NPY_FR_W, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_h) {
-        if ((value % 24) == 0) {
-            return hash_datetime_value_and_reso(value / 24, NPY_FR_D, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_m) {
-        if ((value % 60) == 0) {
-            return hash_datetime_value_and_reso(value / 60, NPY_FR_h, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_s) {
-        if ((value % 60) == 0) {
-            return hash_datetime_value_and_reso(value / 60, NPY_FR_m, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_ms) {
-        if ((value % 1000) == 0) {
-            return hash_datetime_value_and_reso(value / 1000, NPY_FR_s, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_us) {
-        if ((value % 1000) == 0) {
-            return hash_datetime_value_and_reso(value / 1000, NPY_FR_ns, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_ns) {
-        if ((value % 1000) == 0) {
-            return hash_datetime_value_and_reso(value / 1000, NPY_FR_us, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_ps) {
-        if ((value % 1000) == 0) {
-            return hash_datetime_value_and_reso(value / 1000, NPY_FR_ns, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_fs) {
-        if ((value % 1000) == 0) {
-            return hash_datetime_value_and_reso(value / 1000, NPY_FR_ps, dts);
-        }
-        return value;
-    }
-    else if (unit == NPY_FR_as) {
-        if ((value % 1000) == 0) {
-            return hash_datetime_value_and_reso(value / 1000, NPY_FR_fs, dts);
-        }
-        return value;
-    }
-    else {
-        // i.e. NPY_FR_GENERIC
-        // we default to treating these like nanos
-        return hash_datetime_value_and_reso(value, NPY_FR_ns, dts);
+Py_hash_t PANDAS_INLINE hash_datetime_from_struct(npy_datetimestruct* dts) {
+    /* 
+     * If we cannot cast to datetime, use the datetime struct values directly
+     * and mix them similar to a tuple.
+     */
+
+    Py_uhash_t acc = _PandasHASH_XXPRIME_5;
+#if 64 <= SIZEOF_PY_UHASH_T
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->year);
+#else
+    /* Mix lower and uper bits of the year if int64 is larger */
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->year);
+    acc = tuple_update_uhash(acc, (Py_uhash_t)(dts->year >> SIZEOF_PY_UHASH_T));
+#endif
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->month);
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->day);
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->min);
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->sec);
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->us);
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->ps);
+    acc = tuple_update_uhash(acc, (Py_uhash_t)dts->as);
+    /* should be a need to mix length, as it is fixed anyway? */
+    if (acc == (Py_uhash_t)-1) {
+        acc = (Py_uhash_t)-2;
     }
+    return acc;
 }
 
 
@@ -448,11 +389,13 @@ Py_hash_t np_datetime64_object_hash(PyObject* key) {
     if ((dts.year > 0) && (dts.year <= 9999) && (dts.ps == 0) && (dts.as == 0)) {
         // we CAN cast to pydatetime, so use that hash to ensure we compare
         // as matching standard library datetimes (and pd.Timestamps)
-        PyDateTime_IMPORT;
-
         PyObject* dt;
         Py_hash_t hash;
 
+        /*
+         * Datetime API is needed:  User must ensure `PyDatetime_IMPORT;` or 
+         * `from cpython.datetime cimport import_datetime; import_datetime()`
+         */
         dt = PyDateTime_FromDateAndTime(
             dts.year, dts.month, dts.day, dts.hour, dts.min, dts.sec, dts.us
         );
@@ -464,7 +407,7 @@ Py_hash_t np_datetime64_object_hash(PyObject* key) {
         return hash;
     }
 
-    return hash_datetime_value_and_reso(value, unit, &dts);
+    return hash_datetime_from_struct(&dts);
 }
 
 
```
Thanks @seberg.  Updated to use your implementation, but moved it to np_datetime so we can also use it for `Timestamp.__hash__`, ensuring the hashes match.
Removed now-unnecessary casts as suggested.  Doing import_datetime() in khash.pxd and removing PyDateTime_IMPORT caused a segfault
Yeah, I guess cython doesn't like initialization functions in `pyd` files, which makes sense in general since `pyd` files are more typically linked rather than included.  But here, you effectively include it directly (its not linked, the headers contain everything).

I am not aware that you can do this in cython.  Cython does it for NumPy, but I think that is a NumPy specific hack.  So either `import_datetime` is required in every `.pyx` or we need to link (have a `khash.pyx` file which includes the import, I think).
@seberg @WillAyd im having a tough time keeping this green and without merge conflicts.  can we _please_ table the PyDatetime_Import and other pure-refactor issues so that the bugfix can get in for the RC next week?
It is unfortunate that the `import` thing is tricky, but I don't disagree that these should maybe be follow-ups.  Backporting the hashing as is seems fine even if we might consider tweaking it also.  A possible header refactor or other cleanups seems not important to me to begin with and things that don't need backporting.

Maybe @WillAyd can just follow up with trying to extract the import (and do any smaller improvements), that seems indeed easier especially if this keeps having merge conflicts.
im trying in a separate branch to put `PyDateTime_IMPORT;` at the top of np_datetime.c.  when i do, i get

```
pandas/_libs/tslibs/src/datetime/np_datetime.c:32:1: warning: type specifier missing, defaults to 'int' [-Wimplicit-int]
PyDateTime_IMPORT;
^
/usr/local/opt/python@3.10/Frameworks/Python.framework/Versions/3.10/include/python3.10/datetime.h:200:5: note: expanded from macro 'PyDateTime_IMPORT'
    PyDateTimeAPI = (PyDateTime_CAPI *)PyCapsule_Import(PyDateTime_CAPSULE_NAME, 0)
    ^
pandas/_libs/tslibs/src/datetime/np_datetime.c:32:1: error: redefinition of 'PyDateTimeAPI' with a different type: 'int' vs 'PyDateTime_CAPI *'
/usr/local/opt/python@3.10/Frameworks/Python.framework/Versions/3.10/include/python3.10/datetime.h:200:5: note: expanded from macro 'PyDateTime_IMPORT'
    PyDateTimeAPI = (PyDateTime_CAPI *)PyCapsule_Import(PyDateTime_CAPSULE_NAME, 0)
    ^
/usr/local/opt/python@3.10/Frameworks/Python.framework/Versions/3.10/include/python3.10/datetime.h:197:25: note: previous definition is here
static PyDateTime_CAPI *PyDateTimeAPI = NULL;
                        ^
1 warning and 1 error generated.
error: command '/usr/local/opt/ccache/libexec/clang' failed with exit code 1
```

googling PyDateTime_IMPORT i see some people have done `if (!PyDateTimeAPI) { PyDateTime_IMPORT; }` (at runtime).  Putting that at the top of the file gives

```
pandas/_libs/tslibs/src/datetime/np_datetime.c:34:1: error: expected identifier or '('
if (!PyDateTimeAPI) { PyDateTime_IMPORT; }
^
1 error generated.
```
You can't put any code top-level in C, it would have to be inside an init function (in Python that would mean called by the module initialization function, which has a special module-dependent name.

However, doing `if (!PyDateTimeAPI) { PyDateTime_IMPORT; }` is a very reasonable solution here.  In fact, we do similar things all over the place in NumPy where up-front initialization would be tedious or just not super obvious.
To get this in I think we should:

1. Not duplicate any defines across the header files, so put the cpython hashing stuff in its own header
2. Add a few more tests of the expected behavior, where the distinction between Python equality and hashing semantics becomes necessary (ex: getting a unique sequence)
ci failure is unrelated

@WillAyd we're cutting it down to the wire in terms of getting this in for the RC.  I'll pinky-swear to follow up with the no-duplicate-defines request if we can put that off.  For the other, can you flesh out a bit what you have in mind?
My concern is generally about the lack of tests - this has some pretty far reaching implications and there is only 1 test. I might be missing the larger context, but what's the reason this needs to be part of the RC?

Here's a specific example from this branch - I don't think the behavior of unique / value counts are correct:

```python
>>> pd.Series([np.datetime64(1, "ms"), np.datetime64(1000, "us")], dtype=object)
0       1970-01-01T00:00:00.001
1    1970-01-01T00:00:00.001000
dtype: object
>>> pd.Series([np.datetime64(1, "ms"), np.datetime64(1000, "us")], dtype=object).unique()
array([numpy.datetime64('1970-01-01T00:00:00.001')], dtype=object)
>>> pd.Series([np.datetime64(1, "ms"), np.datetime64(1000, "us")], dtype=object).value_counts()
1970-01-01 00:00:00.001    2
Name: count, dtype: int64
```
> but what's the reason this needs to be part of the RC?

For yak-shaving reasons this a blocker for getting .unique to preserve non-nano which I was hoping to get in for 2.0.  Turns out there are other blockers for that, so this is less time-sensitive than I had thought.
> Here's a specific example from this branch - I don't think the behavior of unique / value counts are correct:

Will add a test for this.  I guess its plausible if a user specified this separately they might want them to count as distinct, but I think its reasonable to say they match.
I think it is pretty confusing for different frequencies to hash to the same value. Are there other non-dt instances where we do something like this? 

cc @MarcoGorelli and @mroeschke for any thoughts they might have
> I think it is pretty confusing for different frequencies to hash to the same value. Are there other non-dt instances where we do something like this?

:+1: for tests, there were not enough (initially at least).  And yeah, mixing frequencies is weird and can definitely lead to surprises (e.g. because you don't know which frequency will "survive" in a `unique` call).  But the rule is if it evaluates `==` it must hash equal.  The alternative should just lead to other/more serious inconsistencies.
> But the rule is if it evaluates `==` it must hash equal. The alternative should just lead to other/more serious inconsistencies.

Hmm didn't realize this was a requirement of CPython but nice callout. With that said, I find this to be really surprising behavior; essentially whenever the hash of these gets invoked you aren't guaranteed to get the same object back. I don't think that is very user friendly, especially if you go through a lot of care to set these units in the first place.

What would be the downside of an alternative like `is_datetime_equivalent` to perform the comparison across units while still ensuring we can preserve the unit?
> What would be the downside of an alternative like is_datetime_equivalent to perform the comparison across units while still ensuring we can preserve the unit?

1) Maintenance.  I'm optimistic an implementation similar to this PR's will get upstreamed to numpy soonish, after which (once our min-version catches up) we can remove some of this.  But not if we have a separate is_datetime_equivalent

2) Lack of clarity as to which convention is used in what context.  e.g. the test case https://github.com/pandas-dev/pandas/pull/50960/files#diff-b9e8ea9ddb76d75890be0087dd93d9b6e1482280f2104b3a2dd8a1c602ac1576R192 get_loc goes through a hash-based path in some cases and an equality-checking path in others.  The motivating case _needs_ index.get_indexer to see these objects as matching (or to avoid going through index.get_indexer which would be a whole other barrel of worms)
@WillAyd the build here started breaking after the capsule PR was merged.  i cant reproduce locally.  help?
I think your final issue is going to be the lack of a `PandasDateTime_IMPORT` in the timestamps.pyx file. Right now you are getting the includes there but not actually assigning to the static variable that holds all the function pointers from the capsule
timestamps.pyx has a import_pandas_datetime().  I thought that was equivalent to PandasDateTime_IMPORT?
Ah OK sorry I misread that. So the problem is that you are updating khash_python.h and introducing some new symbol names. To hack it I think you need to update the remaining files that don't have access to those symbols to do the pandas_datetime_import (ex: algos.pyx, hashtable.pyx, etc...) Basically anywhere in the logs where you see this:

```sh
In file included from pandas/_libs/src/klib/khash_python.h:13,
                 from pandas/_libs/algos.c:802:
/home/runner/micromamba/envs/test/include/python3.8/datetime.h:189:25: error: ‘PyDateTimeAPI’ defined but not used [-Werror=unused-variable]
  189 | static PyDateTime_CAPI *PyDateTimeAPI = NULL;
```

The `algos.c` is an indicator that `algos.pyx` doesn't have access to the capsule symbols, but you are inserting code from a header file that assumes it does.

You can try to hack around that, but I think also better if we figure out a way to restructure things so that the headers and modules aren't mixing up symbol requirements like they are now. Is `khash_python` something that was vendored? 
> Is khash_python something that was vendored?

I'm pretty sure khash.h was vendored, not sure about khash_python.h.

I'm increasingly making "grumpy old man" mutterings about this capsule thing.