python पाइथन में हैश(एन)== एन कब है?




python-2.7 python-3.x (4)

मैं पाइथन के हैश फ़ंक्शन के साथ खेल रहा हूं। छोटे पूर्णांक के लिए, यह hash(n) == n हमेशा दिखाई देता है। हालांकि यह बड़ी संख्या में विस्तार नहीं करता है:

>>> hash(2**100) == 2**100
False

मैं आश्चर्यचकित नहीं हूं, मैं समझता हूं कि हैश मूल्यों की एक सीमित श्रृंखला लेता है। वह सीमा क्या है?

मैंने सबसे छोटी संख्या hash(n) != n खोजने के लिए बाइनरी खोज का उपयोग करने की कोशिश की hash(n) != n

>>> import codejamhelpers # pip install codejamhelpers
>>> help(codejamhelpers.binary_search)
Help on function binary_search in module codejamhelpers.binary_search:

binary_search(f, t)
    Given an increasing function :math:`f`, find the greatest non-negative integer :math:`n` such that :math:`f(n) \le t`. If :math:`f(n) > t` for all :math:`n \ge 0`, return None.

>>> f = lambda n: int(hash(n) != n)
>>> n = codejamhelpers.binary_search(f, 0)
>>> hash(n)
2305843009213693950
>>> hash(n+1)
0

2305843009213693951 के बारे में विशेष क्या है? मुझे लगता है कि यह sys.maxsize == 9223372036854775807 से कम है

संपादित करें: मैं पायथन 3 का उपयोग कर रहा हूं। मैंने पाइथन 2 पर एक ही बाइनरी खोज चलाई और मुझे एक अलग परिणाम मिला 2147483648, जो मुझे नोट है sys.maxint+1

हैश फ़ंक्शन की सीमा का अनुमान लगाने के [hash(random.random()) for i in range(10**6)] साथ भी खेला। अधिकतम ऊपर एन नीचे लगातार है। न्यूनतम की तुलना में, ऐसा लगता है कि पायथन 3 हैश हमेशा सकारात्मक मूल्यवान है, जबकि पायथन 2 के हैश नकारात्मक मान ले सकते हैं।



2305843009213693951 2^61 - 1 । यह सबसे बड़ा मेर्सन प्राइम है जो 64 बिट्स में फिट बैठता है।

यदि आपको मूल्य मोड को कुछ संख्या ले कर हैश बनाना है, तो एक बड़ा मेर्सन प्राइम एक अच्छा विकल्प है - गणना करना आसान है और संभावनाओं का वितरण भी सुनिश्चित करना आसान है। (हालांकि मैं व्यक्तिगत रूप से कभी इस तरह एक हैश नहीं बनाऊंगा)

फ्लोटिंग पॉइंट नंबरों के लिए मॉड्यूलस की गणना करना विशेष रूप से सुविधाजनक है। उनके पास एक घातीय घटक है जो पूरे नंबर को 2^x गुणा करता है। चूंकि 2^61 = 1 mod 2^61-1 , आपको केवल (exponent) mod 61 पर विचार करने की आवश्यकता है।

देखें: https://en.wikipedia.org/wiki/Mersenne_prime


हैश फ़ंक्शन सादा int देता है जिसका अर्थ है कि लौटाया गया मान -sys.maxint से अधिक है और -sys.maxint से कम है, जिसका अर्थ है कि यदि आप sys.maxint + x को पास करते हैं तो परिणाम -sys.maxint + (x - 2)

hash(sys.maxint + 1) == sys.maxint + 1 # False
hash(sys.maxint + 1) == - sys.maxint -1 # True
hash(sys.maxint + sys.maxint) == -sys.maxint + sys.maxint - 2 # True

इस बीच 2**200 sys.maxint से n गुणा अधिक है - मेरा अनुमान है कि हैश रेंज -sys.maxint..+sys.maxint n बार पर -sys.maxint..+sys.maxint जब तक कि यह उस सीमा में सादे पूर्णांक पर बंद न हो, जैसे कोड स्निपेट में ऊपर..

तो आम तौर पर, किसी भी एन <= sys.maxint के लिए :

hash(sys.maxint*n) == -sys.maxint*(n%2) +  2*(n%2)*sys.maxint - n/2 - (n + 1)%2 ## True

नोट: यह अजगर 2 के लिए सच है।


pyhash.c फ़ाइल में पायथन दस्तावेज़ के आधार पर:

संख्यात्मक प्रकारों के लिए, x x का हैश x modulo को प्राथमिक P = 2**_PyHASH_BITS - 1 में कमी पर आधारित है। यह डिज़ाइन किया गया है कि hash(x) == hash(y) जब भी एक्स और वाई संख्यात्मक रूप से बराबर हों, भले ही एक्स और वाई के अलग-अलग प्रकार हों।

तो 64/32 बिट मशीन के लिए, कमी 2 _PyHASH_BITS - 1 होगी, लेकिन _PyHASH_BITS क्या है?

आप इसे pyhash.h हेडर फ़ाइल में पा सकते हैं जो 64 बिट मशीन के लिए 61 के रूप में परिभाषित किया गया है (आप pyconfig.h फ़ाइल में और स्पष्टीकरण पढ़ सकते हैं)।

#if SIZEOF_VOID_P >= 8
#  define _PyHASH_BITS 61
#else
#  define _PyHASH_BITS 31
#endif

तो सबसे पहले यह आपके प्लेटफॉर्म पर आधारित है उदाहरण के लिए मेरे 64 बिट लिनक्स प्लेटफ़ॉर्म में कमी 2 61 -1 है, जो 2305843009213693951 :

>>> 2**61 - 1
2305843009213693951

इसके अलावा आप math.frexp और sys.maxint एक्सपोनेंट प्राप्त करने के लिए math.frexp का उपयोग कर सकते हैं, जो 64 बिट मशीन के लिए दिखाता है कि अधिकतम int 2 63 है :

>>> import math
>>> math.frexp(sys.maxint)
(0.5, 64)

और आप एक साधारण परीक्षण से अंतर देख सकते हैं:

>>> hash(2**62) == 2**62
True
>>> hash(2**63) == 2**63
False

पाइथन हैशिंग एल्गोरिदम https://github.com/python/cpython/blob/master/Python/pyhash.c#L34 बारे में पूरा दस्तावेज पढ़ें

जैसा कि टिप्पणी में उल्लिखित है, आप sys.hash_info (पायथन 3.X में) का उपयोग कर सकते हैं जो आपको हैश कंप्यूटिंग के लिए उपयोग किए गए पैरामीटर का एक स्ट्रक्चर अनुक्रम देगा।

>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>> 

मॉड्यूलस के साथ जो मैंने पिछली पंक्तियों में वर्णित किया है, आप निम्न मान को निम्न मान भी प्राप्त कर सकते हैं:

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159




python-internals