从问题" 分区比排序更容易吗？ ":
假设我有一个项目列表和它们的等价关系,并且比较两个项目需要恒定的时间.我想返回项目的分区,例如链接列表列表,每个列表包含所有等效项目.
这样做的一种方法是将等价扩展到项目的排序并对它们进行排序(使用排序算法); 那么所有等价物品都会相邻.
(请记住平等和等同之间的区别.)
显然,在设计排序算法时必须考虑等价关系.例如,如果等价关系是"同一年出生的人是等价的",则根据人名进行排序是不合适的.
您能否建议一种数据类型和等价关系,以便无法创建排序？
怎么样的数据类型和等价关系在那里是可以创建这样的排序,但它是不是可以对将映射等价物品相同的散列值的数据类型定义的哈希函数.
(注意:如果非等价项映射到相同的散列值(碰撞),则可以 - 我不是要求解决碰撞问题 - 但另一方面,hashFunc(item) { return 1; }是作弊.)
我怀疑对于任何可以定义排序的数据类型/等价对,也可以定义合适的散列函数,并且它们将具有类似的算法复杂度.这个猜想的一个反例就是启发!