Repository: pandas-dev/pandas

Issue:
BUG: Index containing NA behaves absolutely unpredictably when length exceeds 128
### Pandas version checks

- [X] I have checked that this issue has not already been reported.

- [X] I have confirmed this bug exists on the [latest version](https://pandas.pydata.org/docs/whatsnew/index.html) of pandas.

- [x] I have confirmed this bug exists on the [main branch](https://pandas.pydata.org/docs/dev/getting_started/install.html#installing-the-development-version-of-pandas) of pandas.


### Reproducible Example

```python
import pandas as pd

# OK:
n, val = 127, pd.NA
idx = pd.Index(range(n), dtype="Int64").union(pd.Index([val], dtype="Int64"))
s = pd.Series(index=idx, data=range(n+1), dtype="Int64")
s.drop(0)

# Still OK:
n, val = 128, 128
idx = pd.Index(range(n), dtype="Int64").union(pd.Index([val], dtype="Int64"))
s = pd.Series(index=idx, data=range(n+1), dtype="Int64")
s.drop(0)

# But this FAILS:
n, val = 128, pd.NA
idx = pd.Index(range(n), dtype="Int64").union(pd.Index([val], dtype="Int64"))
s = pd.Series(index=idx, data=range(n+1), dtype="Int64")
s.drop(0)  # ValueError: 'indices' contains values less than allowed (-128 < -1)
# Expected no error

```

**WORKAROUND.** to filter out elements, use a boolean mask/indexing instead of s.drop():
```python
s[~s.index.isin([0])]
```



### Issue Description

When `NA` is present in `Index` and the length of the Index exceeds 128, it behaves in a completely weird way.

This bug can be narrowed down to `IndexEngine.get_indexer()` or [`MaskedIndexEngine.get_indexer()`](https://github.com/pandas-dev/pandas/blob/58461fef2315d228d08f65f8a9430e9294d65b31/pandas/_libs/index.pyx#L1164-L1166), as these examples suggest:
```python
axis = pd.Index(range(250), dtype='Int64').union(pd.Index([pd.NA], dtype='Int64'))
new_axis = axis.drop(0)
axis.get_indexer(new_axis)[-5:] # array([246, 247, 248, 249,  -6])
# Expected array([246, 247, 248, 249,  250])

axis = pd.Index(range(254), dtype='Int64').union(pd.Index([pd.NA], dtype='Int64'))
new_axis = axis.drop(0)
axis.get_indexer(new_axis)[-5:] # array([250, 251, 252, 253,  -2])
# Expected  array([250, 251, 252, 253,  254])
```
These examples further suggest that the root cause of the bug is in how `NaN` is represented in and is interacting with the hash tables that `Index` uses for its `_engine`.


### Expected Behavior

See above

### Installed Versions

<details>

commit                : 76c7274985215c487248fa5640e12a9b32a06e8c
python                : 3.11.5.final.0
python-bits           : 64
OS                    : Linux
OS-release            : 5.10.216-204.855.amzn2.x86_64
Version               : #1 SMP Sat May 4 16:53:27 UTC 2024
machine               : x86_64
processor             : x86_64
byteorder             : little
LC_ALL                : None
LANG                  : en_US.UTF-8
LOCALE                : en_US.UTF-8

pandas                : 3.0.0.dev0+1067.g76c7274985
numpy                 : 1.26.4
pytz                  : 2023.3.post1
dateutil              : 2.8.2
setuptools            : 65.5.0
pip                   : 23.2.1
Cython                : None
pytest                : None
hypothesis            : None
sphinx                : None
blosc                 : None
feather               : None
xlsxwriter            : None
lxml.etree            : None
html5lib              : None
pymysql               : None
psycopg2              : None
jinja2                : None
IPython               : None
pandas_datareader     : None
adbc-driver-postgresql: None
adbc-driver-sqlite    : None
bs4                   : None
bottleneck            : None
fastparquet           : None
fsspec                : None
gcsfs                 : None
matplotlib            : None
numba                 : None
numexpr               : None
odfpy                 : None
openpyxl              : None
pyarrow               : 15.0.0
pyreadstat            : None
python-calamine       : None
pyxlsb                : None
s3fs                  : None
scipy                 : None
sqlalchemy            : None
tables                : None
tabulate              : None
xarray                : None
xlrd                  : None
zstandard             : None
tzdata                : 2023.4
qtpy                  : None
pyqt5                 : None

</details>


Discussion:
avm19: Perhaps I should not have rebased. The changes suggested above by @mroeschke are the only changes, I promise.

Patch:
diff --git a/doc/source/whatsnew/v3.0.0.rst b/doc/source/whatsnew/v3.0.0.rst
index 0df5a70d87..fb7321139f 100644
--- a/doc/source/whatsnew/v3.0.0.rst
+++ b/doc/source/whatsnew/v3.0.0.rst
@@ -696,6 +696,7 @@ Indexing
 - Bug in :meth:`DataFrame.__getitem__` returning modified columns when called with ``slice`` in Python 3.12 (:issue:`57500`)
 - Bug in :meth:`DataFrame.from_records` throwing a ``ValueError`` when passed an empty list in ``index`` (:issue:`58594`)
 - Bug in :meth:`DataFrame.loc` with inconsistent behavior of loc-set with 2 given indexes to Series (:issue:`59933`)
+- Bug in :meth:`Index.get_indexer` and similar methods when ``NaN`` is located at or after position 128 (:issue:`58924`)
 - Bug in :meth:`MultiIndex.insert` when a new value inserted to a datetime-like level gets cast to ``NaT`` and fails indexing (:issue:`60388`)
 - Bug in printing :attr:`Index.names` and :attr:`MultiIndex.levels` would not escape single quotes (:issue:`60190`)
 
diff --git a/pandas/_libs/hashtable.pxd b/pandas/_libs/hashtable.pxd
index a5a3edad63..0480ee54ff 100644
--- a/pandas/_libs/hashtable.pxd
+++ b/pandas/_libs/hashtable.pxd
@@ -41,7 +41,7 @@ cdef class HashTable:
 
 cdef class UInt64HashTable(HashTable):
     cdef kh_uint64_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, uint64_t val)
@@ -51,7 +51,7 @@ cdef class UInt64HashTable(HashTable):
 
 cdef class Int64HashTable(HashTable):
     cdef kh_int64_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, int64_t val)
@@ -61,7 +61,7 @@ cdef class Int64HashTable(HashTable):
 
 cdef class UInt32HashTable(HashTable):
     cdef kh_uint32_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, uint32_t val)
@@ -71,7 +71,7 @@ cdef class UInt32HashTable(HashTable):
 
 cdef class Int32HashTable(HashTable):
     cdef kh_int32_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, int32_t val)
@@ -81,7 +81,7 @@ cdef class Int32HashTable(HashTable):
 
 cdef class UInt16HashTable(HashTable):
     cdef kh_uint16_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, uint16_t val)
@@ -91,7 +91,7 @@ cdef class UInt16HashTable(HashTable):
 
 cdef class Int16HashTable(HashTable):
     cdef kh_int16_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, int16_t val)
@@ -101,7 +101,7 @@ cdef class Int16HashTable(HashTable):
 
 cdef class UInt8HashTable(HashTable):
     cdef kh_uint8_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, uint8_t val)
@@ -111,7 +111,7 @@ cdef class UInt8HashTable(HashTable):
 
 cdef class Int8HashTable(HashTable):
     cdef kh_int8_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, int8_t val)
@@ -121,7 +121,7 @@ cdef class Int8HashTable(HashTable):
 
 cdef class Float64HashTable(HashTable):
     cdef kh_float64_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, float64_t val)
@@ -131,7 +131,7 @@ cdef class Float64HashTable(HashTable):
 
 cdef class Float32HashTable(HashTable):
     cdef kh_float32_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, float32_t val)
@@ -141,7 +141,7 @@ cdef class Float32HashTable(HashTable):
 
 cdef class Complex64HashTable(HashTable):
     cdef kh_complex64_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, complex64_t val)
@@ -151,7 +151,7 @@ cdef class Complex64HashTable(HashTable):
 
 cdef class Complex128HashTable(HashTable):
     cdef kh_complex128_t *table
-    cdef int64_t na_position
+    cdef Py_ssize_t na_position
     cdef bint uses_mask
 
     cpdef get_item(self, complex128_t val)
diff --git a/pandas/_libs/hashtable_class_helper.pxi.in b/pandas/_libs/hashtable_class_helper.pxi.in
index 210df09f07..eae393f33b 100644
--- a/pandas/_libs/hashtable_class_helper.pxi.in
+++ b/pandas/_libs/hashtable_class_helper.pxi.in
@@ -535,7 +535,7 @@ cdef class {{name}}HashTable(HashTable):
             int ret = 0
             {{c_type}} val
             khiter_t k
-            int8_t na_position = self.na_position
+            Py_ssize_t na_position = self.na_position
 
         if self.uses_mask and mask is None:
             raise NotImplementedError  # pragma: no cover
@@ -567,7 +567,7 @@ cdef class {{name}}HashTable(HashTable):
             Int64Vector self_locs = Int64Vector()
             Int64VectorData *l
             Int64VectorData *sl
-            int8_t na_position = self.na_position
+            Py_ssize_t na_position = self.na_position
 
         l = &locs.data
         sl = &self_locs.data
@@ -609,7 +609,7 @@ cdef class {{name}}HashTable(HashTable):
             {{c_type}} val
             khiter_t k
             intp_t[::1] locs = np.empty(n, dtype=np.intp)
-            int8_t na_position = self.na_position
+            Py_ssize_t na_position = self.na_position
 
         if self.uses_mask and mask is None:
             raise NotImplementedError  # pragma: no cover


Test patch:
diff --git a/pandas/tests/libs/test_hashtable.py b/pandas/tests/libs/test_hashtable.py
index 50b561aefc..6a95cfc735 100644
--- a/pandas/tests/libs/test_hashtable.py
+++ b/pandas/tests/libs/test_hashtable.py
@@ -149,18 +149,19 @@ class TestHashTable:
     def test_map_locations_mask(self, table_type, dtype, writable):
         if table_type == ht.PyObjectHashTable:
             pytest.skip("Mask not supported for object")
-        N = 3
+        N = 129  # must be > 128 to test GH#58924
         table = table_type(uses_mask=True)
         keys = (np.arange(N) + N).astype(dtype)
         keys.flags.writeable = writable
-        table.map_locations(keys, np.array([False, False, True]))
+        mask = np.concatenate([np.repeat(False, N - 1), [True]], axis=0)
+        table.map_locations(keys, mask)
         for i in range(N - 1):
             assert table.get_item(keys[i]) == i
 
         with pytest.raises(KeyError, match=re.escape(str(keys[N - 1]))):
             table.get_item(keys[N - 1])
 
-        assert table.get_na() == 2
+        assert table.get_na() == N - 1
 
     def test_lookup(self, table_type, dtype, writable):
         N = 3