c - 确定与等价函数的一对一对应关系的算法

Question

假设我有两组项目，并且有一个函数来检查两个项目的等价性(不是严格相等，所以一个项目可能等价于另一组中的多个项目)，我想确定是否有一个一对一的对应关系，这样等价性对每一对都成立。

这个问题是否有任何既定/最佳解决方案？

---

这个问题最初来自确定两个 C union 类型是否兼容，为此标准要求这样的对应关系，但是事情变得棘手，因为 union 成员可以是匿名的，所以一个项目的等价项目可以有多种可能性。目前我正在采用一种天真的方法，但我想知道是否有任何确定的讨论/解决方案。

Answer 1

一种解决方案是实现具有两个属性的哈希函数:

1. 等价的项目具有相同的哈希值
2. 不等价的项目很少有相同的散列值

请注意，完美的哈希函数永远不会为不相同的项目生成相同的哈希值。

一旦有了散列函数，就可以按散列值对列表进行排序。如果您的散列是完美的，则检查一对一对应关系是微不足道的。如果哈希函数不够完美，当您找到 n 对 n 的对应关系时，代码将需要回退到对那些 n 项的蛮力 O(n^2) 等价性检查.

运行时间是以下任务的总和

• O(N) 生成哈希值
• O(NlogN) 对列表进行排序
• M * O(n^2) 用于暴力检查(如果哈希函数不完美)

因此，完美哈希函数的总运行时间为 O(NlogN)，而暴力比较的运行时间为 O(N^2)。