CODEWITHSUNDEEP
pythonhashtime-complexity
Eli Korvigo
Eli Korvigo

Reputation: 10513

Long numbers hashing complexity in Python

How does Python hash long numbers? I guess it takes O(1) time for 32-bit ints, but the way long integers work in Python makes me think the complexity is not O(1) for them. I've looked for answers in relevant questions, but have found none straightforward enough to make me confident. Thank you in advance.

Upvotes: 1

Views: 435

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1124668

The long_hash() function indeed loops and depends on the size of the integer, yes:

/* 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++;
}

where i is the 'object size', e.g. the number of digits used to represent the number, where the size of a digit depends on your platform.

Upvotes: 5

Related Questions