为什么python中的hash()函数对可变长度的字符串进行运算需要常数时间？

Question

从运行时期的程序包括对可变长度字符串的hash()操作我觉得可能是hash()函数对不同长度的字符串进行操作需要常数时间。为了验证我的假设，我制定了以下策略 -

创建长度为 k 的字符串
对字符串进行Hash，记录hash()操作时间t
对于从 0 到 100,00 变化的 k 重复此操作，并生成字符串长度 k 与时间 t 的关系图。

因此，如果我猜测 hash() 函数在对字符串进行操作时是一个常量时间操作是正确的，请您通俗易懂地解释一下为什么会这样？概念或理论解释而不是对源代码的引用将是更可取的 - 至于即使是大字符串也如何立即产生散列，而不管字符长度。

以下是上述策略的代码实现-

import random
import time
import pylab

def form_str(k, n):
    """
        Form k-length strings of arbitrary characters, n in number.
    """
    for i in range(n):
        random_str = ''
        for j in range(k):
            nextchar = random.choice('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz')
            random_str += nextchar
        yield random_str

def time_hash(k, n):
    """
        Find the total time to hash n strings of k length each.
    """
    
    total_time = 0.0
    for element in form_str(k, n):
        start_time = time.time()
        # Because hash() works almost instantaneously we repeat
        # it 100,000 times to get a non-zero run time.
        for i in range(100000):
            hash(element)
        end_time = time.time()
        total_time += (end_time - start_time)
    return round(total_time, 2)

# print(time_hash(100, 100))  

def plot_time():
    """
        Plots the time vs string length (k) over a range of k-values.
    """
    x_values, y_values = [], []
    for k in range(0, 100000, 5000):
        x_values.append(k)
        y_values.append(time_hash(k, 100))
    # print(y_values)
    pylab.figure(1)
    pylab.title('Hash_Time_Complexity')
    pylab.xlabel('Length of string')
    pylab.ylabel('Time taken to hash string (100 x 100000 times)')
    pylab.plot(x_values, y_values, 'r:', label = 'Hash time')
    pylab.show()

plot_time()
# From the plot it is clear that indifferent of the string length
# hashing takes the same time.

生成的图如下-

Answer 1

由于字符串是不可变的，因此字符串的哈希码仅计算一次并在之后缓存。

更好的基准测试方法是生成长度为 k 的不同（唯一）字符串并平均它们的哈希时间，而不是多次调用同一字符串的哈希。

为什么python中的hash()函数对可变长度的字符串进行运算需要常数时间？

Why does the hash() function in python take constant time to operate on strings of variable length?

python

hash

time-complexity

hash-function

constant-time