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, length: int = 0
50) -> npt.NDArray[np.uint64]:
51 """
52 Parameters
53 ----------
54 arrays : Iterator[np.ndarray]
55 num_items : int
56 length : int, default 0
57 Length of the result if ``arrays`` is empty.
59 Returns
60 -------
61 np.ndarray[uint64]
63 Should be the same as CPython's tupleobject.c
64 """
65 try:
66 first = next(arrays)
67 except StopIteration:
68 # GH#24318 each row hashes as an empty tuple: seed plus finalizer
69 return np.full(length, 0x345678 + 97531, dtype=np.uint64)
71 arrays = itertools.chain([first], arrays)
73 mult = np.uint64(1000003)
74 out = np.zeros_like(first) + np.uint64(0x345678)
75 last_i = 0
76 for i, a in enumerate(arrays):
77 inverse_i = num_items - i
78 out ^= a
79 out *= mult
80 mult += np.uint64(82520 + inverse_i + inverse_i)
81 last_i = i
82 assert last_i + 1 == num_items, "Fed in wrong num_items"
83 out += np.uint64(97531)
84 return out
87def hash_pandas_object(
88 obj: Index | DataFrame | Series,
89 index: bool = True,
90 encoding: str = "utf8",
91 hash_key: str | None = _default_hash_key,
92 categorize: bool = True,
93) -> Series:
94 """
95 Return a data hash of the Index/Series/DataFrame.
97 The hash is computed element-wise using the underlying data values,
98 and optionally includes the index when hashing a Series or DataFrame.
100 Parameters
101 ----------
102 obj : Index, Series, or DataFrame
103 The pandas object to hash.
104 index : bool, default True
105 Include the index in the hash (if Series/DataFrame). When True,
106 the hash for each row depends on both the value and the index label,
107 so the same value at a different index position will produce a
108 different hash.
109 encoding : str, default 'utf8'
110 Encoding for data & key when strings.
111 hash_key : str, default _default_hash_key
112 Hash_key for string key to encode.
113 categorize : bool, default True
114 Whether to first categorize object arrays before hashing. This is more
115 efficient when the array contains duplicate values.
117 Returns
118 -------
119 Series of uint64
120 Same length as the object.
122 See Also
123 --------
124 util.hash_array : Return a hash of the given array.
125 util.hash_tuples : Hash a MultiIndex or listlike-of-tuples efficiently.
127 Examples
128 --------
129 >>> pd.util.hash_pandas_object(pd.Series([1, 2, 3]))
130 0 14639053686158035780
131 1 3869563279212530728
132 2 393322362522515241
133 dtype: uint64
135 By default, the hash includes the index, so the same value at a
136 different index position will produce a different hash:
138 >>> df1 = pd.DataFrame({"a": ["a", "b", "c"]})
139 >>> df2 = pd.DataFrame({"a": ["b", "a", "c"]})
140 >>> pd.util.hash_pandas_object(df1)
141 0 4578374827886788867
142 1 17338122309987883691
143 2 5473791562133574857
144 dtype: uint64
145 >>> pd.util.hash_pandas_object(df2)
146 0 8168238220198793318
147 1 14044658390916132862
148 2 5473791562133574857
149 dtype: uint64
151 Set ``index=False`` to hash only the values. In this case, the same
152 value always produces the same hash regardless of its position:
154 >>> pd.util.hash_pandas_object(df1, index=False)
155 0 5694802365760992243
156 1 2797248057711234736
157 2 18202460376300699891
158 dtype: uint64
159 >>> pd.util.hash_pandas_object(df2, index=False)
160 0 2797248057711234736
161 1 5694802365760992243
162 2 18202460376300699891
163 dtype: uint64
164 """
165 from pandas import Series
167 if hash_key is None:
168 hash_key = _default_hash_key
170 if isinstance(obj, ABCMultiIndex):
171 return Series(hash_tuples(obj, encoding, hash_key), dtype="uint64", copy=False)
173 elif isinstance(obj, ABCIndex):
174 h = hash_array(obj._values, encoding, hash_key, categorize).astype(
175 "uint64", copy=False
176 )
177 ser = Series(h, index=obj, dtype="uint64", copy=False)
179 elif isinstance(obj, ABCSeries):
180 h = hash_array(obj._values, encoding, hash_key, categorize).astype(
181 "uint64", copy=False
182 )
183 if index:
184 index_iter = (
185 hash_pandas_object(
186 obj.index,
187 index=False,
188 encoding=encoding,
189 hash_key=hash_key,
190 categorize=categorize,
191 )._values
192 for _ in [None]
193 )
194 arrays = itertools.chain([h], index_iter)
195 h = combine_hash_arrays(arrays, 2)
197 ser = Series(h, index=obj.index, dtype="uint64", copy=False)
199 elif isinstance(obj, ABCDataFrame):
200 hashes = (
201 hash_array(series._values, encoding, hash_key, categorize)
202 for _, series in obj.items()
203 )
204 num_items = len(obj.columns)
205 if index:
206 index_hash_generator = (
207 hash_pandas_object(
208 obj.index,
209 index=False,
210 encoding=encoding,
211 hash_key=hash_key,
212 categorize=categorize,
213 )._values
214 for _ in [None]
215 )
216 num_items += 1
218 # keep `hashes` specifically a generator to keep mypy happy
219 _hashes = itertools.chain(hashes, index_hash_generator)
220 hashes = (x for x in _hashes)
221 h = combine_hash_arrays(hashes, num_items, len(obj))
223 ser = Series(h, index=obj.index, dtype="uint64", copy=False)
224 else:
225 raise TypeError(f"Unexpected type for hashing {type(obj)}")
227 return ser
230def hash_tuples(
231 vals: MultiIndex | Iterable[tuple[Hashable, ...]],
232 encoding: str = "utf8",
233 hash_key: str = _default_hash_key,
234) -> npt.NDArray[np.uint64]:
235 """
236 Hash a MultiIndex / listlike-of-tuples efficiently.
238 Parameters
239 ----------
240 vals : MultiIndex or listlike-of-tuples
241 encoding : str, default 'utf8'
242 hash_key : str, default _default_hash_key
244 Returns
245 -------
246 ndarray[np.uint64] of hashed values
247 """
248 if not is_list_like(vals):
249 raise TypeError("must be convertible to a list-of-tuples")
251 from pandas import (
252 Categorical,
253 MultiIndex,
254 )
256 if not isinstance(vals, ABCMultiIndex):
257 mi = MultiIndex.from_tuples(vals)
258 else:
259 mi = vals
261 # create a list-of-Categoricals
262 cat_vals = [
263 Categorical._simple_new(
264 mi.codes[level],
265 CategoricalDtype(categories=mi.levels[level], ordered=False),
266 )
267 for level in range(mi.nlevels)
268 ]
270 # hash the list-of-ndarrays
271 hashes = (
272 cat._hash_pandas_object(encoding=encoding, hash_key=hash_key, categorize=False)
273 for cat in cat_vals
274 )
275 h = combine_hash_arrays(hashes, len(cat_vals))
277 return h
280def hash_array(
281 vals: ArrayLike,
282 encoding: str = "utf8",
283 hash_key: str = _default_hash_key,
284 categorize: bool = True,
285) -> npt.NDArray[np.uint64]:
286 """
287 Given a 1d array, return an array of deterministic integers.
289 This function applies a hash function to each element of the input
290 array, producing a fixed set of uint64 values suitable for use in
291 hashing-based algorithms.
293 Parameters
294 ----------
295 vals : ndarray or ExtensionArray
296 The input array to hash.
297 encoding : str, default 'utf8'
298 Encoding for data & key when strings.
299 hash_key : str, default _default_hash_key
300 Hash_key for string key to encode.
301 categorize : bool, default True
302 Whether to first categorize object arrays before hashing. This is more
303 efficient when the array contains duplicate values.
305 Returns
306 -------
307 ndarray[np.uint64, ndim=1]
308 Hashed values, same length as the vals.
310 See Also
311 --------
312 util.hash_pandas_object : Return a data hash of the Index/Series/DataFrame.
313 util.hash_tuples : Hash a MultiIndex / listlike-of-tuples efficiently.
315 Examples
316 --------
317 >>> pd.util.hash_array(np.array([1, 2, 3]))
318 array([ 6238072747940578789, 15839785061582574730, 2185194620014831856],
319 dtype=uint64)
320 """
321 if not hasattr(vals, "dtype"):
322 raise TypeError("must pass an ndarray-like")
324 if isinstance(vals, ABCExtensionArray):
325 return vals._hash_pandas_object(
326 encoding=encoding, hash_key=hash_key, categorize=categorize
327 )
329 if not isinstance(vals, np.ndarray):
330 # GH#42003
331 raise TypeError(
332 "hash_array requires np.ndarray or ExtensionArray, not "
333 f"{type(vals).__name__}. Use hash_pandas_object instead."
334 )
336 return _hash_ndarray(vals, encoding, hash_key, categorize)
339def _hash_ndarray(
340 vals: np.ndarray,
341 encoding: str = "utf8",
342 hash_key: str = _default_hash_key,
343 categorize: bool = True,
344) -> npt.NDArray[np.uint64]:
345 """
346 See hash_array.__doc__.
347 """
348 dtype = vals.dtype
350 # _hash_ndarray only takes 64-bit values, so handle complex dtypes by
351 # parts. complex64 fits in 64 bits, but bit-hashing its two halves as a
352 # single value would bypass the float canonicalization below (GH#28363).
353 if dtype.type in (np.complex64, np.complex128):
354 hash_real = _hash_ndarray(vals.real, encoding, hash_key, categorize)
355 hash_imag = _hash_ndarray(vals.imag, encoding, hash_key, categorize)
356 return hash_real + 23 * hash_imag
358 # First, turn whatever array this is into unsigned 64-bit ints, if we can
359 # manage it.
360 if dtype == bool:
361 vals = vals.astype("u8")
362 elif issubclass(dtype.type, (np.datetime64, np.timedelta64)):
363 vals = vals.view("i8").astype("u8", copy=False)
364 elif issubclass(dtype.type, np.number) and dtype.itemsize <= 8:
365 uint_dtype = f"u{dtype.itemsize}"
366 uints = vals.view(uint_dtype).astype("u8")
367 if issubclass(dtype.type, np.floating):
368 # GH#28363 a single float value can have more than one bit
369 # pattern: 0.0 vs -0.0, and NaN with any sign or payload.
370 # Canonicalize those so that equal values hash equal.
371 uints[np.isnan(vals)] = np.array(np.nan, dtype=dtype).view(uint_dtype)
372 uints[uints == np.array(-0.0, dtype=dtype).view(uint_dtype)] = 0
373 vals = uints
374 else:
375 # With repeated values, its MUCH faster to categorize object dtypes,
376 # then hash and rename categories. We allow skipping the categorization
377 # when the values are known/likely to be unique.
378 if categorize:
379 from pandas import (
380 Categorical,
381 Index,
382 factorize,
383 )
385 codes, categories = factorize(vals, sort=False)
386 tdtype = CategoricalDtype(
387 categories=Index(categories, copy=False), ordered=False
388 )
389 cat = Categorical._simple_new(codes, tdtype)
390 return cat._hash_pandas_object(
391 encoding=encoding, hash_key=hash_key, categorize=False
392 )
394 try:
395 vals = hash_object_array(vals, hash_key, encoding)
396 except TypeError:
397 # we have mixed types
398 vals = hash_object_array(
399 vals.astype(str).astype(object), hash_key, encoding
400 )
402 # Then, redistribute these 64-bit ints within the space of 64-bit ints
403 vals ^= vals >> 30
404 vals *= np.uint64(0xBF58476D1CE4E5B9)
405 vals ^= vals >> 27
406 vals *= np.uint64(0x94D049BB133111EB)
407 vals ^= vals >> 31
408 # error: Incompatible return value type (got "Any | ndarray[tuple[int, ...],
409 # dtype[signedinteger[Any]]]", expected "ndarray[tuple[int, ...],
410 # dtype[unsignedinteger[_64Bit]]]")
411 return vals # type: ignore[return-value]