Python中的长数哈希复杂性

Question

Python如何散列长数？我想32位整数需要O(1)时间,但长整数在Python中工作的方式让我觉得复杂性不是O(1).我在相关问题中寻找答案,但没有发现任何直截了当的问题让我充满信心.先感谢您.

Answer 1

该long_hash()功能确实循环,并依赖于整数的大小,是:

/* The following loop produces a C unsigned long x such that x is
   congruent to the absolute value of v modulo ULONG_MAX.  The
   resulting x is nonzero if and only if v is. */
while (--i >= 0) {
    /* Force a native long #-bits (32 or 64) circular shift */
    x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
    x += v->ob_digit[i];
    /* If the addition above overflowed we compensate by
       incrementing.  This preserves the value modulo
       ULONG_MAX. */
    if (x < v->ob_digit[i])
        x++;
}

i"对象大小" 在哪里,例如用于表示数字的位数,其中数字的大小取决于您的平台.