我必须找到2 ^ 25个随机字符串的SHA256散列。然后寻找冲突（最后一次使用生日悖论，例如，仅哈希的50位）。
我将string：hash对存储在dict变量中。然后用值（不是键）对变量进行排序，然后使用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()
我会选择这样的东西：
打开16个文件（以二进制模式打开应该没问题；如果所有字符串的长度都相同，这将是最简单的）。生成字符串和哈希，然后根据哈希的前4位将它们写入文件。然后分别加载和处理每个文件。这会将内存使用量减少16倍。（当然，只要不耗尽文件句柄，就可以使用任意数量的文件。每次访问都必须打开和关闭每个文件会变得很慢。）
如果生成字符串和哈希值相对便宜，那么您甚至不需要文件。只需执行16次传递，并且在每个传递中仅保留那些哈希，其高半字节与传递编号相匹配。
解决问题的一种方法是使用非常长的位域，以便将每个哈希映射到2^25 bits长存储块中的特定位置。
通过Bloom filter或其他概率数据结构完成了解决此类问题的更好的方法，但并非100％保证。
布隆过滤器是一种节省空间的概率数据结构，用于测试元素是否为集合的成员。误报是可能的，但误报是不可能的。即查询返回“内部集合（可能是错误的）”或“肯定不在集合中”。
Bloom过滤器相对于用于表示集合的其他数据结构（例如自平衡二进制搜索树，尝试，哈希表或条目的简单数组或链接列表）具有强大的空间优势。
具有1％错误的Bloom过滤器每个元素仅需要9.6位-不管元素的大小如何。
因此，每2 ^ 25个元素9.6位，仅需要38.4 MiB的内存。
[我认为这里的关键见解-我承认逃避了一段时间，直到几个小时后才回到我的观点-是sha256哈希摘要是它自己的哈希。换句话说，您不必进行任何其他哈希处理或设置创建。您要做的就是使用sha256摘要作为哈希表来创建自定义哈希表。为了节省空间，请不要存储字符串。只需创建一个位数组（使用对用table = numpy.zeros(table_size / bits_per_int + 1, dtype='i')创建的int数组中的整数进行移位操作）来检测冲突，然后将冲突的字符串保存在dict映射为哈希的字符串中，以便在第二遍中进行查找。
table_size应该是一个大素数-我选择了一个略大于2 ** 31的素数，它构成了268MB的表-因为它将产生很少的新冲突/误报（由哈希的模运算引入） ）。您可以将字符串本身保存到文本文件中，然后进行迭代。
因此，对于任何字符串，要设置的相应位的索引将为index = int(hashlib.sha256('foo').hexdigest(), base=16) % table_size。然后计算major_index = index / bits_in_int和minor_index = index % bits_in_int，对minor_index使用移位和按位运算，以检查并在table[major_index]的int中存储正确的位，依此类推。
现在通过字符串进行传递。每当字符串生成的哈希值映射到已设置的位时，就将hash:string对存储在字典中。或者更好的方法是，存储hash:[string_list]对，在发生多次冲突的情况下将新字符串追加到列表中。现在，对于任何冲突的字符串对（a，b），字典将包含b的哈希值和值。然后第二遍遍字符串，依次对每个哈希进行哈希处理，并检查字典中的每个哈希值。如果哈希在字典中，并且字符串不在相应的列表中，则将该字符串添加到列表中。词典中的某些字符串将不对应于真正的冲突。这些杂凑中的大多数的[string_list]只有一个项目长，并且这些hash:[string_list]对可能会被丢弃。其他冲突可能是由散列函数本身而非模运算引起的真实冲突。但是，在同时存在真假判断的情况下，您可能仍有一些误报要清除。您必须仔细检查结果列表是否存在误报。
BasicWolf建议使用Bloom过滤器是一个很好的建议，并且可能会导致表较小。但这增加了很多复杂性。我没有打扰。我在从'0\n'到'33554431\n'的换行符终止的字符串上尝试了上述方法，发现两个散列具有54位重叠。花了11分钟，最大内存使用量约为350MB（尽管可能会减少。）我进行了一些分析，发现大部分时间都花在了计算位表的偏移量上。用c进行编码可能会大大提高速度，并且预散列和存储散列以及字符串也将有所帮助。
实际上，我尝试预散列字符串，并用numpy的基于c的扩展模块中的bitarray替换了基于same name的临时位数组。这将运行时间减少到仅2分钟多，同时将内存配置文件保持在350MB左右。
我认为足够接近政府工作。由于这是一项任务，因此我不会发布代码，但是很高兴提供其他指针。
为什么不使用从前50位哈希到字符串的字典？
例如，将散列分割为10个字符。并以这种方式嵌套值，您将具有递归搜索，但它应该更快]