Python 中的长数字散列复杂度

Question

Python 如何散列长数字？我想 32 位整数需要 O(1) 时间，但长整数在 Python 中的工作方式让我认为复杂性不是它们的 O(1)。我在相关问题中寻找答案，但发现 none 简单明了，足以让我充满信心。先感谢您。

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 是 'object size'，例如位数用于表示数字，其中数字的大小取决于您的平台。

Python 中的长数字散列复杂度

Long numbers hashing complexity in Python

python

hash

time-complexity