如何使用2 ^ 50个元素处理dict变量？

Question

我必须找到2 ^ 25个随机字符串的SHA256哈希值.然后寻找碰撞(使用生日悖论的最后一个,比如说只有50位的散列).

我在dict变量中存储字符串:hash对.然后使用值(而不是键)对变量进行排序,然后使用O(n)循环查找冲突.

问题是因为有2 ^ 25个字符串和它们的2 ^ 25个哈希值,所以dict变量中有2 ^ 50个值.这是非常耗费资源的.那么,我如何使用有限的RAM(例如1GB左右)来做到这一点？

我已经尝试过:
1.使用6GB交换空间运行它.该程序一夜之间运行,但仍未完成.这基本上比O(n_square)搜索更慢!哈希计算的RAM使用量约为3.2 GB.但在那之后,当涉及到sort命令时,使用的RAM再次开始拍摄!我虽然python排序使用In-Place-Quicksort :(
2.我只存储了哈希并发现了一个碰撞.但由于没有存储它,所以找不到相应的字符串.

我不应该使用数据库等.最多是一个文本文件,但这没有帮助.另外,我对Python很新,但不要限制你的答案水平.

PS:这是一项任务.有人声称在一分钟内发现了300MB RAM的冲突.不知道这是不是真的.我已经解决了问题,但答案无法实现!在工作中,所以现在无法访问代码.将很快添加.

码:

from Crypto.Hash import SHA256
import os
import random
import string
from operator import itemgetter

def shaa():

    trun=[]
    clist={}
    for i in range(0,33554432):

        sha=SHA256.new(str(i)).hexdigest()
        sha=int(bin(int(sha,16))[-50:],2)
        clist[i]=sha

    print 'Hashes done.'

    clist=sorted(clist.items(), key=itemgetter(1))  
    for i in range(0,33554432):

        if(clist[i]==clist[i+1]):
            #print string[i],string[i+1]
            print clist[i]
            return 1
    return 2

result=2
while(result==2):
    result=shaa()

Answer 1

我会去做这样的事情：

打开 16 个文件（以二进制模式打开应该没问题；如果所有字符串都具有相同的长度，这将是最简单的）。生成字符串和哈希值，并根据哈希值的前 4 位将它们写入文件。然后分别加载和处理每个文件。这将减少 16 倍的内存使用量。（当然，只要不耗尽文件句柄，您可以使用任意数量的文件。每次访问时都必须打开和关闭每个文件，这会变得相当慢。）

如果生成字符串和哈希值相对便宜，您甚至不需要这些文件。只需执行 16 次传递，并且在每次传递中仅保留那些与传递编号匹配的高半字节的哈希值。