保持数学相等的哈希函数（特别是对于集合）

Question

我正在开发一种基于数学的编程语言（用 Rust 编写），它使用集合而不是类型。其中，变量或值属于一组值（例如

x : {1, 2, 3}

或

msg : Str

）。用户可以创建有限集（例如

x = {1, 2, 3, false, "hi"}

），将值内部存储在

HashSet

中，并对值进行哈希处理。然而，该语言也有无限集的概念，如

Nat

、

Int

、

Real

、

Complex

、

Str

等。我的问题是我不知道如何最佳地表示这些无限集当在另一个集合中时（即通过散列）。

我目前的想法是设置eg的散列。

Nat

为 0，

Int

为 1，依此类推，但这 只是感觉不对。此外，计算结果为等效集合的表达式应该具有相同的哈希值，而计算结果为不同集合的表达式必须具有不同的哈希值，因此我当前的实现将不起作用：

// Reals except those that are Ints
A = Real \ Int
// hash of A should vary from the hash of Real and Int (what would its hash be though?)
B = Real \ A
// hash of B should be the same as hash of Int

在这个例子中，可以以某种方式进行简化，尽管在更复杂的表达式中，我不知道它们是否总是可以简化为具有相等哈希值的东西。另外，对于

A

，使用我的方法，我不知道如何计算哈希值。

我的问题是：我是否应该使用一些具有此功能的哈希函数，或者是否应该使用其他一些算法或数据结构来实现此功能，或者我是否完全偏离了轨道，应该实现整个过程以不同的方式做事？

Answer 1

框架挑战：这不是关于散列，这是关于规范化。

散列（或实习）接受输入并为其分配一个整数值。如果您想要保证相等的哈希值/实习，那么您需要首先提供保证相等的输入。

因此，你的问题是创建一个算法，为任何输入生成“规范”形式。在给出的例子中：

A = Real \ Int => Real \ Int
B = Real \ A => Int

然后，对规范形式进行散列或驻留将导致一个等于所有“规范相等”集合的整数 - 无论使用哪种散列/驻留算法。