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

Question

假设我有两组项目，以及一个检查两个项目等价的函数（不是严格相等，因此一个项目可能等同于另一个集合中的多个项目），我想确定是否存在一对一- 一个对应关系，使得等价对每一对都成立。

有没有针对这个问题的既定/最佳解决方案？

---

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

Answer 1

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

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

请注意，完美的散列函数永远不会为不等价的项目生成相同的散列值。

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

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

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

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