Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2data hash pandas / numpy objects
3"""
5from __future__ import annotations
7import itertools
8from typing import TYPE_CHECKING
10import numpy as np
12from pandas._libs.hashing import hash_object_array
14from pandas.core.dtypes.common import is_list_like
15from pandas.core.dtypes.dtypes import CategoricalDtype
16from pandas.core.dtypes.generic import (
17 ABCDataFrame,
18 ABCExtensionArray,
19 ABCIndex,
20 ABCMultiIndex,
21 ABCSeries,
22)
24if TYPE_CHECKING:
25 from collections.abc import (
26 Hashable,
27 Iterable,
28 Iterator,
29 )
31 from pandas._typing import (
32 ArrayLike,
33 npt,
34 )
36 from pandas import (
37 DataFrame,
38 Index,
39 MultiIndex,
40 Series,
41 )
44# 16 byte long hashing key
45_default_hash_key = "0123456789123456"
48def combine_hash_arrays(
49 arrays: Iterator[np.ndarray], num_items: int
50) -> npt.NDArray[np.uint64]:
51 """
52 Parameters
53 ----------
54 arrays : Iterator[np.ndarray]
55 num_items : int
57 Returns
58 -------
59 np.ndarray[uint64]
61 Should be the same as CPython's tupleobject.c
62 """
63 try:
64 first = next(arrays)
65 except StopIteration:
66 return np.array([], dtype=np.uint64)
68 arrays = itertools.chain([first], arrays)
70 mult = np.uint64(1000003)
71 out = np.zeros_like(first) + np.uint64(0x345678)
72 last_i = 0
73 for i, a in enumerate(arrays):
74 inverse_i = num_items - i
75 out ^= a
76 out *= mult
77 mult += np.uint64(82520 + inverse_i + inverse_i)
78 last_i = i
79 assert last_i + 1 == num_items, "Fed in wrong num_items"
80 out += np.uint64(97531)
81 return out
84def hash_pandas_object(
85 obj: Index | DataFrame | Series,
86 index: bool = True,
87 encoding: str = "utf8",
88 hash_key: str | None = _default_hash_key,
89 categorize: bool = True,
90) -> Series:
91 """
92 Return a data hash of the Index/Series/DataFrame.
94 The hash is computed element-wise using the underlying data values,
95 and optionally includes the index when hashing a Series or DataFrame.
97 Parameters
98 ----------
99 obj : Index, Series, or DataFrame
100 The pandas object to hash.
101 index : bool, default True
102 Include the index in the hash (if Series/DataFrame).
103 encoding : str, default 'utf8'
104 Encoding for data & key when strings.
105 hash_key : str, default _default_hash_key
106 Hash_key for string key to encode.
107 categorize : bool, default True
108 Whether to first categorize object arrays before hashing. This is more
109 efficient when the array contains duplicate values.
111 Returns
112 -------
113 Series of uint64
114 Same length as the object.
116 See Also
117 --------
118 util.hash_array : Return a hash of the given array.
119 util.hash_tuples : Hash a MultiIndex or listlike-of-tuples efficiently.
121 Examples
122 --------
123 >>> pd.util.hash_pandas_object(pd.Series([1, 2, 3]))
124 0 14639053686158035780
125 1 3869563279212530728
126 2 393322362522515241
127 dtype: uint64
128 """
129 from pandas import Series
131 if hash_key is None:
132 hash_key = _default_hash_key
134 if isinstance(obj, ABCMultiIndex):
135 return Series(hash_tuples(obj, encoding, hash_key), dtype="uint64", copy=False)
137 elif isinstance(obj, ABCIndex):
138 h = hash_array(obj._values, encoding, hash_key, categorize).astype(
139 "uint64", copy=False
140 )
141 ser = Series(h, index=obj, dtype="uint64", copy=False)
143 elif isinstance(obj, ABCSeries):
144 h = hash_array(obj._values, encoding, hash_key, categorize).astype(
145 "uint64", copy=False
146 )
147 if index:
148 index_iter = (
149 hash_pandas_object(
150 obj.index,
151 index=False,
152 encoding=encoding,
153 hash_key=hash_key,
154 categorize=categorize,
155 )._values
156 for _ in [None]
157 )
158 arrays = itertools.chain([h], index_iter)
159 h = combine_hash_arrays(arrays, 2)
161 ser = Series(h, index=obj.index, dtype="uint64", copy=False)
163 elif isinstance(obj, ABCDataFrame):
164 hashes = (
165 hash_array(series._values, encoding, hash_key, categorize)
166 for _, series in obj.items()
167 )
168 num_items = len(obj.columns)
169 if index:
170 index_hash_generator = (
171 hash_pandas_object(
172 obj.index,
173 index=False,
174 encoding=encoding,
175 hash_key=hash_key,
176 categorize=categorize,
177 )._values
178 for _ in [None]
179 )
180 num_items += 1
182 # keep `hashes` specifically a generator to keep mypy happy
183 _hashes = itertools.chain(hashes, index_hash_generator)
184 hashes = (x for x in _hashes)
185 h = combine_hash_arrays(hashes, num_items)
187 ser = Series(h, index=obj.index, dtype="uint64", copy=False)
188 else:
189 raise TypeError(f"Unexpected type for hashing {type(obj)}")
191 return ser
194def hash_tuples(
195 vals: MultiIndex | Iterable[tuple[Hashable, ...]],
196 encoding: str = "utf8",
197 hash_key: str = _default_hash_key,
198) -> npt.NDArray[np.uint64]:
199 """
200 Hash a MultiIndex / listlike-of-tuples efficiently.
202 Parameters
203 ----------
204 vals : MultiIndex or listlike-of-tuples
205 encoding : str, default 'utf8'
206 hash_key : str, default _default_hash_key
208 Returns
209 -------
210 ndarray[np.uint64] of hashed values
211 """
212 if not is_list_like(vals):
213 raise TypeError("must be convertible to a list-of-tuples")
215 from pandas import (
216 Categorical,
217 MultiIndex,
218 )
220 if not isinstance(vals, ABCMultiIndex):
221 mi = MultiIndex.from_tuples(vals)
222 else:
223 mi = vals
225 # create a list-of-Categoricals
226 cat_vals = [
227 Categorical._simple_new(
228 mi.codes[level],
229 CategoricalDtype(categories=mi.levels[level], ordered=False),
230 )
231 for level in range(mi.nlevels)
232 ]
234 # hash the list-of-ndarrays
235 hashes = (
236 cat._hash_pandas_object(encoding=encoding, hash_key=hash_key, categorize=False)
237 for cat in cat_vals
238 )
239 h = combine_hash_arrays(hashes, len(cat_vals))
241 return h
244def hash_array(
245 vals: ArrayLike,
246 encoding: str = "utf8",
247 hash_key: str = _default_hash_key,
248 categorize: bool = True,
249) -> npt.NDArray[np.uint64]:
250 """
251 Given a 1d array, return an array of deterministic integers.
253 Parameters
254 ----------
255 vals : ndarray or ExtensionArray
256 The input array to hash.
257 encoding : str, default 'utf8'
258 Encoding for data & key when strings.
259 hash_key : str, default _default_hash_key
260 Hash_key for string key to encode.
261 categorize : bool, default True
262 Whether to first categorize object arrays before hashing. This is more
263 efficient when the array contains duplicate values.
265 Returns
266 -------
267 ndarray[np.uint64, ndim=1]
268 Hashed values, same length as the vals.
270 See Also
271 --------
272 util.hash_pandas_object : Return a data hash of the Index/Series/DataFrame.
273 util.hash_tuples : Hash a MultiIndex / listlike-of-tuples efficiently.
275 Examples
276 --------
277 >>> pd.util.hash_array(np.array([1, 2, 3]))
278 array([ 6238072747940578789, 15839785061582574730, 2185194620014831856],
279 dtype=uint64)
280 """
281 if not hasattr(vals, "dtype"):
282 raise TypeError("must pass an ndarray-like")
284 if isinstance(vals, ABCExtensionArray):
285 return vals._hash_pandas_object(
286 encoding=encoding, hash_key=hash_key, categorize=categorize
287 )
289 if not isinstance(vals, np.ndarray):
290 # GH#42003
291 raise TypeError(
292 "hash_array requires np.ndarray or ExtensionArray, not "
293 f"{type(vals).__name__}. Use hash_pandas_object instead."
294 )
296 return _hash_ndarray(vals, encoding, hash_key, categorize)
299def _hash_ndarray(
300 vals: np.ndarray,
301 encoding: str = "utf8",
302 hash_key: str = _default_hash_key,
303 categorize: bool = True,
304) -> npt.NDArray[np.uint64]:
305 """
306 See hash_array.__doc__.
307 """
308 dtype = vals.dtype
310 # _hash_ndarray only takes 64-bit values, so handle 128-bit by parts
311 if np.issubdtype(dtype, np.complex128):
312 hash_real = _hash_ndarray(vals.real, encoding, hash_key, categorize)
313 hash_imag = _hash_ndarray(vals.imag, encoding, hash_key, categorize)
314 return hash_real + 23 * hash_imag
316 # First, turn whatever array this is into unsigned 64-bit ints, if we can
317 # manage it.
318 if dtype == bool:
319 vals = vals.astype("u8")
320 elif issubclass(dtype.type, (np.datetime64, np.timedelta64)):
321 vals = vals.view("i8").astype("u8", copy=False)
322 elif issubclass(dtype.type, np.number) and dtype.itemsize <= 8:
323 vals = vals.view(f"u{vals.dtype.itemsize}").astype("u8")
324 else:
325 # With repeated values, its MUCH faster to categorize object dtypes,
326 # then hash and rename categories. We allow skipping the categorization
327 # when the values are known/likely to be unique.
328 if categorize:
329 from pandas import (
330 Categorical,
331 Index,
332 factorize,
333 )
335 codes, categories = factorize(vals, sort=False)
336 tdtype = CategoricalDtype(
337 categories=Index(categories, copy=False), ordered=False
338 )
339 cat = Categorical._simple_new(codes, tdtype)
340 return cat._hash_pandas_object(
341 encoding=encoding, hash_key=hash_key, categorize=False
342 )
344 try:
345 vals = hash_object_array(vals, hash_key, encoding)
346 except TypeError:
347 # we have mixed types
348 vals = hash_object_array(
349 vals.astype(str).astype(object), hash_key, encoding
350 )
352 # Then, redistribute these 64-bit ints within the space of 64-bit ints
353 vals ^= vals >> 30
354 vals *= np.uint64(0xBF58476D1CE4E5B9)
355 vals ^= vals >> 27
356 vals *= np.uint64(0x94D049BB133111EB)
357 vals ^= vals >> 31
358 # error: Incompatible return value type (got "Any | ndarray[tuple[int, ...],
359 # dtype[signedinteger[Any]]]", expected "ndarray[tuple[int, ...],
360 # dtype[unsignedinteger[_64Bit]]]")
361 return vals # type: ignore[return-value]