具有相同哈希值的python哈希函数

我有一个python哈希函数，我试图用相同的哈希值得到10个密钥，但是我找不到。具有相同哈希值的python哈希函数

这里是我的功能：

import math 
def h(x): 
    return math.floor((2**14)*((x*2654435769.0/(2**32)) %1))

来源

2015-02-10 Nick

你能解释一下你想要做什么。示例输入和预期输出。 – Marcin 2015-02-10 02:00:25

在你的代码中，你做的是mod 1，它根本没有意义，因为它总是会导致0.你也乘以结果。根据你的区块中的代码，你可能会返回0，这是没有意义的。如果您正在尝试查找多个会导致相同散列值的值，则完全取决于您使用的散列函数。任何常用的散列函数都设计得非常精巧，可以防止（碰撞），而不需要大量的计算时间。 – Goblinlord 2015-02-10 02:34:30

我可以采取一些整数输入像1,5,10,11。其实任何数字都可以。如果我使用h（）来处理数字x和y，它们与h（x）== h（y）相同，那么它们具有相同的散列值。我需要找到10个数字h（x）== h（y）== h（z）== h（a）== h（b）等找出x，y，z，a，b的值etc. – Nick 2015-02-10 02:38:27

我已经修改了你的哈希函数返回一个int，而不是float。而且我已经预先定义了这些常量，因此在每次调用函数时都不需要计算它们。

（编辑常数的预定义可能不是严格必要的，Python的常量折叠可之后找我们。）

我们通过喂食随机X的的功能和存储结果发现碰撞在列表的字典中，散列值作为字典键，x存储在列表中。为了保持代码简单，我使用了defaultdict，但代码可以很容易地修改为使用标准字典。

下面的代码可以在几秒钟内找到10个碰撞键的列表。

#!/usr/bin/env python 

import math 
import random 
import sys 
from collections import defaultdict 

k14 = 1 << 14 
phibar = 2654435769.0/(1 << 32) 

def h(x): 
    return int(math.floor(k14 * ((x * phibar) % 1))) 

#random.seed(163) 

hi = sys.maxint 
rand = random.randint 

d = defaultdict(list) 
for i in range(100000): 
    x = rand(0, hi) 
    v = h(x) 
    d[v].append(x) 
    if len(d[v]) == 10: 
     print i 
     print v, d[v] 
     break

典型输出

26580 
4695 [2117596615, 363105812, 629092494, 1450847021, 749292969, 1735204492, 21338856, 1153043351, 1047107585, 138752460]

来源

2015-02-10 03:01:57

哦，谢谢。这很酷 – Nick 2015-02-10 03:21:37

具有相同哈希值的python哈希函数

回答

相关问题