随着子字符串大小的增加，如何找到本节代码的复杂性？
if size > 160:
sub = (hashlib.sha1(sub.encode('utf-8')).hexdigest())
当我发现我的程序正在运行，就像哈希函数在恒定时间内执行时，我感到好奇。对于我的程序，如果“大小”为165，则在最坏的情况下，上述代码将执行165x。我刚刚进行的测试显示，sha1与长度的关系不稳定。
Length Time
0 0
1 0.015000105
2 0.016000032
3 0.046000004
4 0.046999931
5 0.062000036
6 0.078000069
7 0.078000069
8 0.07799983
9 0.108999968
测试代码：
import string
import random
import hashlib
import time
def randomly(size=6, chars=string.ascii_uppercase + string.digits):
return ''.join(random.choice(chars) for _ in range(size))
for i in range(1, 10000001, 1000000):
random_str = randomly(i)
start = time.time()
str_hash = hashlib.sha1(random_str.encode('utf-8')).hexdigest()
print time.time() - start
我不同意DarthGizka。这是来自同一维基百科文章的更多描述：
Pre-processing:
append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits.
append 0 ≤ k < 512 bits '0', thus the resulting message length (in bits)
is congruent to 448 (mod 512)
append ml, in a 64-bit big-endian integer. So now the message length is a multiple of 512 bits.
Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15
Extend the sixteen 32-bit words into eighty 32-bit words:
for i from 16 to 79
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
......
填充工作只是一个预处理。在内完成更多工作for each chunk。由于mattkaeo的数据大小大于1000000个字符（第一个字符除外），for循环应该消耗最多的时间，而填充的消耗可以忽略不计。
我相信，mattkaeo的结果不是很线性，因为他只对每个样本运行一次，因此系统噪音（例如OS和其他进程共享CPU能力）非常重要。我将每个样本运行200次：
import timeit
for i in range(1, 10000001, 1000000):
random_str = randomly(i)
print timeit.timeit('hashlib.sha1(random_str).hexdigest()',
setup='import hashlib; random_str="%s".encode("utf-8")' % random_str,
number=200)
结果更加线性：
0.000172138214111
0.303541898727
0.620085954666
0.932041883469
1.29230999947
1.57217502594
1.93531990051
2.24045419693
2.56945014
2.95437908173
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句