如何处理散列冲突？ [英] How to handle hash collisions?

问题描述

我正在开发一款游戏，游戏世界中的每件事物都由一个全球唯一的标识符表示。

这些id每个都是64位，通过哈希产生创建时间，机器网络地址和一个随机数。根据维基百科关于生日问题的文章，散列冲突的概率为0.1％两亿记录。

由于我不太可能得到那么多记录，所以可以认为没有哈希会碰撞。但我不希望这样，但让我的应用程序处理一个id冲突的罕见情况，从而哈希碰撞。

否则，行为将是非常因为游戏世界中的两件独立事物会有联系，因此可以共享它们的属性，如位置，动作，健康点等等。

如何处理散列碰撞？它们是如何处理的？

解决方案

通常情况下，散列冲突有两种处理方式：

1. 使用较大的散列，因此碰撞实际上是不可能的。

非唯一的，并使用相等比较器来确定唯一性。




128位GUID使用第一种方法。 .NET中的 HashSet< T> 类是第二种方法的示例。




I am developing a game where every thing in the game world is represented by an global unique identifier.

Those ids each measure 64 bits and are generated by hashing together the time of creation, the machines network address and a random number. According to Wikipedia's article on the Birthday problem, the probability of a hash collision is 0.1% for two hundred million records.

Since it is unlikely that I'm going to get that much records, one could consider that no hash would ever collide. But I don't want to hope for that, but let my application handle the rare case of a id collision, thus hash collision.

Otherwise, the behavior would be very undesired because two independent things in the game world would have a connection, thus share their properties like position, movement, health points, and so on.

How can I handle hash collisions? How are they handled typically?

解决方案

Typically hash collisions are handled in two ways:

1. Use a larger hash, so that collisions are practically impossible.

2. Consider hash codes to be non-unique, and use an equality comparer for the actual data to determine uniqueness.

A 128 bit GUID uses the first method. The HashSet<T> class in .NET is an example of the second method.

这篇关于如何处理散列冲突？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！