假设我有两个项集，并且有一个函数来检查两个项的等价性（不是严格的相等性，这样一个项可能等价于另一个集中的多个项），我想确定是否存在一对一的对应关系，以便等价性适用于每一对项。
这个问题有什么确定的/最佳的解决方案吗？
这个问题最初来自于确定两个C union类型是否兼容，对于这两个类型，标准要求这样的对应关系，但是事情变得棘手，因为union成员可以是匿名的，因此一个项的等价项可以有多种可能目前，我采用的是一种幼稚的方法，但我想知道是否有任何既定的讨论/解决方案。
最佳答案
一种解决方案是实现具有两个属性的哈希函数：
等价项具有相同的哈希值
不等价的项很少具有相同的哈希值
请注意，一个完美的哈希函数永远不会为不等价的项生成相同的哈希值。
一旦有了散列函数，就可以按散列值对列表进行排序。如果你的散列是完美的，那么检查一对一的通信就很简单了。如果hash函数不够完美，当您找到n对n的对应关系时，代码将需要返回到对那些n项的蛮力O（n^2）等价性检查。
运行时间是以下任务的总和
o（n）生成哈希值
o（nlogn）对列表进行排序
m*o（n^2）用于暴力检查（如果哈希函数不完美）
因此，对于蛮力比较，使用完美哈希函数的总运行时间是o（nlogn），而运行时间是o（n^2）。