python - Python 中的长数字散列复杂性

Question

Python 如何散列长数字？我猜 32 位整数需要 O(1) 时间，但长整数在 Python 中的工作方式让我认为复杂性不是它们的 O(1)。我已经在相关问题中寻找答案，但没有找到足够直截了当让我有信心的答案。先感谢您。

Answer 1

long_hash() function确实循环并取决于整数的大小，是的:

/* 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 是“对象大小”，例如用于表示数字的位数，其中数字的大小取决于您的平台。