python - कब हैथ(n)== n पायथन में?




python-2.7 python-3.x (3)

हैश फंक्शन सादा 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 पर जाएगा -sys.maxint..+sys.maxint n बार जब तक यह उस सीमा में सादे पूर्णांक पर नहीं रुकता है, जैसे कोड स्निपेट में ऊपर..

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

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

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

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

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

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

मैंने सबसे छोटी संख्या 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 से कम है

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

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


pyhash.c फ़ाइल में अजगर प्रलेखन के आधार पर:

संख्यात्मक प्रकारों के लिए, संख्या x का हैश x P = 2**_PyHASH_BITS - 1 प्राइम P = 2**_PyHASH_BITS - 1 की कमी पर आधारित है। इसे ऐसे बनाया गया है कि जब भी x और y अलग-अलग प्रकार के होते हैं, तो 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 और प्रतिपादक को प्राप्त करने के लिए 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
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

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

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

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

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






python-internals