python - متى يكون التجزئة(n)== n في بايثون؟




python-2.7 python-3.x (3)

استنادًا إلى وثائق python في ملف pyhash.c :

بالنسبة للأنواع الرقمية ، يعتمد تجزئة الرقم x على تقليل x modulo P = 2**_PyHASH_BITS - 1 . تم تصميمه بحيث يكون hash(x) == hash(y) عندما يكون x و y متساويين عدديًا ، حتى إذا كان x و 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

لذلك أولاً ، يعتمد الأمر على نظامك الأساسي على سبيل المثال ، في نظام التشغيل 64bit Linux الخاص بي ، يكون التخفيض 2 61 -1 ، وهو 2305843009213693951 :

>>> 2**61 - 1
2305843009213693951

كما يمكنك استخدام math.frexp أجل الحصول على sys.maxint لـ sys.maxint الذي يظهر في الجهاز 64 بت أن الحد الأقصى هو 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 (في python 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)
>>> 

إلى جانب المعامل التي وصفتها في الأسطر السابقة ، يمكنك أيضًا الحصول على قيمة inf كما يلي:

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

لقد لعبت مع وظيفة التجزئة بيثون. للأعداد الصحيحة الصغيرة ، يبدو 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)] لتقدير مدى دالة هاش. الحد الأقصى هو باستمرار أدناه ن أعلاه. عند مقارنة الدقائق ، يبدو أن تجزئة Python 3 لها قيمة إيجابية دائمًا ، في حين أن تجزئة Python 2 يمكن أن تأخذ قيمًا سلبية.


تقوم دالة Hash بإرجاع 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 - أعتقد أن التجزئة قد تتجاوز النطاق - -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.


2305843009213693951 هو 2^61 - 1 . إنه أكبر عدد من مرسين يناسب 64 بت.

إذا كان عليك عمل تجزئة فقط من خلال أخذ قيمة بعض الأرقام المعدلة ، فإن براعة Mersenne الكبيرة تعد خيارًا جيدًا - من السهل حسابها وتضمن توزيعًا متساويًا للإمكانيات. (على الرغم من أنني شخصياً لن أصنع علامة تجزئة بهذه الطريقة)

انها مريحة خاصة لحساب معامل لأرقام الفاصلة العائمة. لديهم مكون الأسي الذي يضاعف عدد صحيح ب 2^x . بما أن 2^61 = 1 mod 2^61-1 ، ما عليك سوى مراعاة (exponent) mod 61 .

راجع: https://en.wikipedia.org/wiki/Mersenne_prime







python-internals