python - 如何处理包含 2^50 个元素的字典变量？

Question

我必须找到 2^25 个随机字符串的 SHA256 哈希值。然后寻找冲突(使用生日悖论来处理最后的哈希值，比如说，仅 50 位)。

我将字符串:哈希对存储在字典变量中。然后使用值(而不是键)对变量进行排序，然后使用 O(n) 循环查找冲突。

问题是因为有 2^25 个字符串和它们的 2^25 个散列，所以 dict 变量有 2^50 个值。这是非常耗费资源的。那么，如何使用有限的 RAM(例如 1GB 左右)执行此操作？

我已经尝试过的:
1. 使用 6GB 交换空间运行它。程序连夜运行，仍未完成。这实际上比 O(n_square) 搜索还要慢!哈希值是根据大约 3.2 GB 的 RAM 使用量计算得出的。但是在那之后，当涉及到排序命令时，使用的 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 次传递，并且在每次传递中只保留那些与传递数匹配的高位半字节的散列。