1

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

  • 创建长度为 k 的字符串
  • 对字符串进行散列，记录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.

以下是生成的图 - 在此处输入图像描述

4

1 回答 1

3

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

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

于 2020-09-02T06:21:57.020 回答