我有一个需要键入表的自定义对象的问题.我需要生成一个唯一的数字键.我有碰撞问题,我想知道我是否可以利用字典来帮助我.假设我有一个这样的对象:
class Thingy
{
public string Foo;
public string Bar;
public string Others;
}
等等有更多领域.让我们说Foo和Bar是我的关键字段 - 如果它们在两个Thingys之间相等,那么这两个对象应该被认为是相等的(一个可能代表对另一个的更新,其他字段正在更新.)所以我有这些:
public override bool Equals(object obj)
{
Thingy thing = (Thingy)obj; // yes I do type check first
return (this.Foo == thing.Foo && this.Bar == thing.Bar);
}
public override int GetHashCode()
{
return (this.Foo + this.Bar).GetHashCode(); // using default string impl
}
所以这在很大程度上是有效的,但是在极少数情况下,两个实际上不同的Thing具有相同的哈希码.
我的问题是:我可以使用词典<Thingy, int>我放在我的Thingys中,并使用字典中的顺序值作为我的实际键吗？我想知道,当检测到罕见的哈希代码冲突时,字典是否会调用我的Equals方法,确定对象实际上是不同的,并以不同方式存储它们.我在查找时进行成像,它会看到该哈希的桶并搜索正确的Thingy,再次使用Equals进行比较.
这是字典的情况,还是仅解决哈希码不同的冲突,但(哈希值大小)是否相同？如果这不起作用,可能会怎样？
我需要比较大块数据的相等性,我需要每秒快速比较多个数据.每个对象都保证大小相同,并且可能/可能只是略有不同(在未知位置).
我已经看到,从下面的交互式会话中,==如果差异朝向字符串的末尾,则使用字符串字符串的运算符会更慢,并且如果在开始附近存在差异,则可以非常快.
我认为可能有某种方法可以使用某种哈希来加快速度,当然计算md5哈希值并且比较速度较慢,但是python的内置哈希确实可以显着提高速度.
但是,我不知道这个哈希的实现细节,它是否真的像哈希一样,我觉得很可能hash(a) == hash(b)当时a == b很可能？如果哈希冲突相当罕见,我很高兴有一些不正确的结果(在几个小时内需要一个200 PS3阵列才能发生冲突的情况很少见)
In [1]: import hashlib
In [2]: with open('/dev/urandom') as f:
...: spam = f.read(2**20 - 1)
...:
In [3]: spamA = spam + 'A'
In [4]: Aspam = 'A' + spam
In [5]: spamB = spam + 'B'
In [6]: timeit spamA == spamB
1000 loops, best of 3: 1.59 ms per loop
In [7]: timeit spamA == Aspam …我知道散列无限数量的字符串到32b int必须生成碰撞,但我期望从散列函数中得到一些不错的分布.
这两个字符串具有相同的哈希值是不是很奇怪？
size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
//hash0 == hash1
我知道我可以使用boost::hash<std::string>或其他人,但我想知道什么是错的std::hash.我用错了吗？我不应该以某种方式"播种"它吗？
我的自定义结构实现了Hashable Protocol.但是,当在a中插入密钥时发生散列冲突时Dictionary,它们不会自动处理.我该如何克服这个问题？
我之前曾问过这个问题 如何在Swift中为Int数组(自定义字符串结构)实现Hashable Protocol.后来我添加了自己的答案,这似乎有效.
但是,最近我hashValue在使用a时发现了碰撞的微妙问题Dictionary.
我尽可能地将代码简化为以下示例.
定制结构
struct MyStructure: Hashable {
var id: Int
init(id: Int) {
self.id = id
}
var hashValue: Int {
get {
// contrived to produce a hashValue collision for id=1 and id=2
if id == 1 {
return 2
}
return id
}
}
}
func ==(lhs: MyStructure, rhs: MyStructure) -> Bool {
return lhs.hashValue == rhs.hashValue
}
请注意全局函数重载相等运算符(==)以符合 …
为了解决这个问题,我一直在玩一个实现Hashable Protocol的自定义结构.我正在尝试查看等效运算符overload(==)被调用多少次,具体取决于填充a时是否存在哈希冲突Dictionary.
更新
@matt编写了一个更清晰的自定义结构示例,该结构实现了Hashable协议并显示了调用的频率hashValue和==调用次数.我在下面复制他的代码.要查看我的原始示例,请查看编辑历史记录.
struct S : Hashable {
static func ==(lhs:S,rhs:S) -> Bool {
print("called == for", lhs.id, rhs.id)
return lhs.id == rhs.id
}
let id : Int
var hashValue : Int {
print("called hashValue for", self.id)
return self.id
}
init(_ id:Int) {self.id = id}
}
var s = Set<S>()
for i in 1...5 {
print("inserting", i)
s.insert(S(i))
}
这会产生结果:
/*
inserting 1
called …据Slashdot报道,MS发布了ASP.NET更新,以修复今天的哈希冲突攻击.(在链接的Technet页面上列为"HashTable中的冲突可能导致DoS漏洞 - CVE-2011-3414".)
问题是POST数据被转换为使用已知散列算法的散列表.如果攻击者通过制作包含大量冲突的请求来使用此功能,则他很容易导致拒绝服务.
有谁知道该更新究竟是如何解决问题的？
如果我有一个URL索引,并通过SHA1哈希的前8个字符对它们进行ID,那么两个不同URL具有相同ID的概率是多少？
我有一个5,651,744行的表,主键由6列(int x 3,smallint,varchar(39),varchar(2))组成.我希望使用此表和另一个共享此主键的表以及添加的另一列但具有37m行来提高性能.
在预期添加列以创建哈希键时,我进行了分析并发现了18,733次冲突.
SELECT SUM(CT)
FROM (
SELECT HASH_KEY
,COUNT(*) AS CT
FROM (
SELECT CHECKSUM(DATA_DT_ID, BANK_NUM, COST_CTR_NUM,
GL_ACCT_NUM, ACCT_NUM, APPN_CD) AS HASH_KEY
FROM CUST_ACCT_PRFTBLT
) AS X
GROUP BY HASH_KEY
HAVING COUNT(*) > 1
) AS Y
SELECT COUNT(*)
FROM CUST_ACCT_PRFTBLT
它差不多两倍 BINARY_CHECKSUM()
考虑到我所覆盖的目标空间的相对较小量,这看起来是否太高(.33%)？如果碰撞很高,那么在连接中加入这个制造的密钥是否有利于每行额外4个字节的成本,因为你仍然必须加入常规列来处理偶尔的碰撞？
我正在散列大量文件,并且为了避免哈希冲突,我还存储了文件的原始大小 - 这样,即使存在哈希冲突,文件大小也几乎不可能相同.这是声音(哈希冲突同样可能是任何大小),或者我是否需要另一条信息(如果碰撞更可能与原始信息的长度相同).
或者,更一般地说:无论原始文件大小如何,每个文件是否都可能产生特定的哈希值？
以这个哈希为例：
ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad
对于我的目的来说太长了，所以我打算使用其中的一小部分，例如：
ba7816bf8f01
ba7816bf
或者类似的。我的预期用例：
//example.com/video-gallery/灯箱/ ba7816bf8f01
我以为我会将视频的 URL SHA256，使用前几个字符作为临时 ID。我应该从生成的哈希中使用多少个字符，以大大减少冲突的机会？
我从URLs and Hashing by Google 中得到了这个想法。