y**b 发帖数: 10166 | 1 http://www.boost.org/doc/libs/1_51_0/doc/html/unordered.html
a hash table only needs an equality function and a hash function for the key.
简言之,哈希表只需等式函数和哈希函数。
http://www.boost.org/doc/libs/1_51_0/doc/html/hash/custom.html
When writing a hash function, first look at how the equality function works.
Objects that are equal must generate the same hash value.
When objects are not equal they should generate different hash values.
简言之,写哈希函数,先参考等式函数。
相等的对象必须产生相等的哈希值;
不等的对象应该产生不同的哈希值。
我有一个unordered_set, 前面都满足,但不同的对象偶尔会产生相同的哈希值,
比如(3,100)和(5,60)是两个不同的对象,按我定义的哈希函数,3*100 = 5*60,
产生相同的哈希值。(3,100)和(5,60)能顺利插入一个unordered_set。
我想问一下:不等的对象应该产生不同的哈希值,这个要求有多严格?如果在
大量数据中出现少量的“不同的对象偶尔会产生相同的哈希值”,对性能影响
应该很小吧?
谢谢。 | t****t 发帖数: 6806 | 2 it's not good but acceptable.
key.
works.
【在 y**b 的大作中提到】 : http://www.boost.org/doc/libs/1_51_0/doc/html/unordered.html : a hash table only needs an equality function and a hash function for the key. : 简言之,哈希表只需等式函数和哈希函数。 : http://www.boost.org/doc/libs/1_51_0/doc/html/hash/custom.html : When writing a hash function, first look at how the equality function works. : Objects that are equal must generate the same hash value. : When objects are not equal they should generate different hash values. : 简言之,写哈希函数,先参考等式函数。 : 相等的对象必须产生相等的哈希值; : 不等的对象应该产生不同的哈希值。
| r*********r 发帖数: 3195 | 3 why not use the provided hash function?
when two different objects have the same hash value, they just go
into the same bucket in the separate chaining scheme, no big deal. |
|