blocks|key|1271417|text|散列函数的目的是随机地将项分配到容器中。对于任何好的散列函数，哪个容器是哪个容器并不“重要”，因为它们必须是不可区分的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1271418|这不适用于“完美散列”实现，它试图比随机分布做得更好-不像你提到的算法。|1271419|正如Michael提到的，碰撞发生在项目和插槽一样多之前很久。如果您想要处理birthday+paradox，则必须具有优雅的冲突处理(或完美的散列)。|offset|length|1271420|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Birthday_paradox^0|0|0|12|G|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@$F|S|G|T|1|U]]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

The point of a hash function is to randomly distribute items into containers. For any good hash function, it doesn't/shouldn't "matter" which container is which as they must be indistinguishable.

This does not apply to "perfect hash" implementations which attempt to do better than random distribution — unlike the algorithms you mentioned.

As Michael mentioned, collisions happen LONG before there are as many items as slots. You must have graceful collision handling (or a perfect hash) if you want to handle the <a href="http://en.wikipedia.org/wiki/Birthday_paradox" rel="nofollow noreferrer">birthday paradox</a>.

blocks|key|154862|text|如果要散列的项目比插槽多，那么就会发生散列冲突。但是如果你有一个糟糕的散列算法，那么即使当项目/插槽比率非常小的时候，你也会看到冲突。一个好的散列算法(包括您将在野外看到的大多数散列算法)将尝试将产生的散列尽可能均匀地分布在整个输出空间中，从而最大限度地减少冲突。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|154863|请注意，哈希冲突并不是世界末日。例如，当在哈希表中使用时，它只是意味着一个插槽中存储了多个项，并且表代码将不得不更多地遍历以查找或添加目标项，从而略微增加了查找时间。|154864|你会看到人们将MD5称为一种“坏掉的”哈希算法，而实际上，它只是一种糟糕的密码哈希算法。它会比你自己做的要好。|154865|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

If you have more items to hash than you have slots, then you'll have hash collisions. But if you have a poor hashing algorithm, then you'll see collisions even when the items / slots ratio is very small. A good hashing algorithm (including most of the ones you'll see in the wild) will attempt to spread the resulting hashes over the entire output space as evenly as possible, and thus minimize collisions.

Note that a hash collision is not the end of the world. When used in a hash table, for instance, it just means that more than one item is stored in a slot, and the table code will have to traverse a little bit more to find or add the target item, increasing lookup time slightly.

You'll see people refer to MD5 as a "broken" hashing algorithm, when in reality, it's just a poor one to use as a cryptographic hash. It'll be better than one you build yourself.

blocks|key|900067|text|我认为使用哈希函数的应用程序是一个重要的区别。例如，散列容器中频繁的冲突可能会降低性能。密码学中频繁的冲突将产生更具破坏性的后果(参见：cryptographic+hash+function+on+Wikipedia)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|900068|即使使用“像样的”散列算法，冲突也相对容易发生。例如，在Java中，|900069|String+s+=+new+String(new+char[size]);|code-block|syntax|javascript|900070|始终哈希为0。也就是说，在Java语言中，所有只包含\0的字符串都散列为0。|style|CODE|900071|900072|至于“是哪个容器有关系吗？”，这又取决于应用程序。您可以设计散列函数，将“相似”的对象散列到附近的值。例如，当您想要搜索相似的对象时，这是很有用的。只需将它们全部散列，看看它们会落在哪里。在这种情况下，碰撞或接近碰撞是理想的，因为它将相似的对象分组。|900073|在其他应用程序中，您甚至希望对象中最轻微的更改都会导致完全不同的哈希值。例如，在密码学中就是这种情况，您希望尽可能确定某些内容没有被修改。在这种情况下，很难找到散列为相同值的不同对象。|900074|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Cryptographic_hash_function^0|1W|14|0|0|0|0|Q|2|0|0|0|0^^$0|@$1|2|3|4|5|6|7|11|8|@]|9|@$A|12|B|13|1|14]]|C|$]]|$1|D|3|E|5|6|7|15|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|16|8|@]|9|@]|C|$I|J]]|$1|K|3|L|5|6|7|17|8|@$A|18|B|19|M|N]]|9|@]|C|$]]|$1|O|3|-4|5|6|7|1A|8|@]|9|@]|C|$]]|$1|P|3|Q|5|6|7|1B|8|@]|9|@]|C|$]]|$1|R|3|S|5|6|7|1C|8|@]|9|@]|C|$]]|$1|T|3|-4|5|6|7|1D|8|@]|9|@]|C|$]]]|U|$V|$5|W|X|Y|C|$Z|10]]]]

I think which application you're using the hash function for is an important distinction. Frequent collision in hashing containers, for example, can degrade performance. Frequent collision in cryptography will have far more devastating consequences (see: <a href="http://en.wikipedia.org/wiki/Cryptographic_hash_function" rel="nofollow noreferrer">cryptographic hash function on Wikipedia</a>).

Collision happens relatively easily even with "decent" hashing algorithm. For example, in Java,

<pre><code>String s = new String(new char[size]);
</code></pre>

always hashes to 0. That is, all strings containing only <code>\0</code> hash to 0 in Java.

<hr>

As for "does it matter which container will it be?", again it depends on the application. You can design hash functions that would hash "similar" objects to nearby values. This is useful when you want to search for similar objects, for example. Just hash them all and see where they fall. In this case, collisions or near-collisions are desirable, because it groups objects that are similar.

In other applications, you want even the slightest change in the object to result in an entirely different hash value. This is the case in cryptography, for example, where you want to be as certain as possible that something has not been modified. It is far more difficult to find different objects that hash to the same value in this case.

blocks|key|154898|text|根据您的应用程序，像MDA、SHA1/2等加密散列可能不是理想的选择，因为它们看起来似乎完全随机，因此会产生生日悖论所预测的冲突。传统上，使用基于余数操作的简单散列的一个原因是，预期密钥是序列号或类似的，因此余数操作将随机地承受比预期更少的冲突。例如，如果关键字是整数是1..1000，如果你的散列函数是关键字mod+1009，那么在1009大小的容器中可能根本没有冲突。人们有时会通过仔细选择容器大小和散列函数来手动调整系统，以实现均匀拆分。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|154899|当然，如果你必须担心人们恶意选择密钥，这会给你带来困难，或者上游系统发送给你非常有偏差的密钥(因为它有自己的哈希表，并决定一次处理所有散列到X的密钥)。您可能希望使用基于键控加密散列函数的散列来防御这种情况。|154900|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Depending on your application, cryptographic hashes like MDA, SHA1/2 etc. may not be the ideal choice, precisely because they appear as if entirely random, thus giving you collisions as prediced by the birthday paradox. Traditionally, one reason for using simple hashes based on the remainder operation is that keys were expected to be serial numbers or similar, so that a remainder operation would sustain fewer collisions than expected at random. E.g. if the keys are the integers are 1..1000 you might have no collisions at all in a container of size 1009 if your hash function is the key mod 1009. People would sometimes hand-tune systems by carefully picking container size and hash function to achieve an even split.

Of course, if you have to worry about people maliciously choosing keys that will cause you difficulty, or an upstream system sending you very biassed keys (because e.g. it has its own hash table and decides to process all keys that hash to X at once). you may wish to use a hash based on a keyed cryptographic hash function to defend against this.

I understand that according to pigeonhole principle, if number of items is greater than number of containers, then at least one container will have more than one item. Does it matter which container will it be? How does this apply to MD5, SHA1, SHA2 hashes?

When do hashes collide?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我知道，根据归档原理，如果物品的数量大于容器的数量，那么至少一个容器将有多个物品。它是哪个容器有关系吗？这如何应用于MD5、SHA1、SHA2哈希？

问哈希值什么时候会冲突？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问哈希值什么时候会冲突？EN