为什么python中的hash()函数对可变长度的字符串进行运算需要常数时间?
Why does the hash() function in python take constant time to operate on strings of variable length?
从运行时期的程序包括对可变长度字符串的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.
生成的图如下-
由于字符串是不可变的,因此字符串的哈希码仅计算一次并在之后缓存。
更好的基准测试方法是生成长度为 k 的不同(唯一)字符串并平均它们的哈希时间,而不是多次调用同一字符串的哈希。
从运行时期的程序包括对可变长度字符串的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.
生成的图如下-
由于字符串是不可变的,因此字符串的哈希码仅计算一次并在之后缓存。
更好的基准测试方法是生成长度为 k 的不同(唯一)字符串并平均它们的哈希时间,而不是多次调用同一字符串的哈希。