表达式文字的哈希函数
Hash function for expression literals
我的 DSL 由下一个运算符组成 AND、OR、>、<、>=、<=、=,!=,&
& 表示交集。
在我的系统中，我需要跟踪每个单独的子表达式，例如不能有重复的表达式。我存储了 hash => node_ptr 的全局哈希映射以在树中检索请求的子表达式。
(name = "John" OR age > 25) AND (interests & ["sport", "education"])
包括：
name = "John"、age > 25、name = "John" OR age > 25、interests & ["sport", "education"]，原来的(name = "John" OR age > 25) AND (interests & ["sport", "education"])
总共有5个子表达式需要被散列。
对于谓词很简单，我可以对谓词的文字（字符串形式）进行哈希处理，例如
int <= hash("attr>=100") 或 int <= hash("attr&{'a','b','c'}").
但它不适用于P1 AND P2等复杂表达式，因为P1 AND P2和P2 AND P1实际上是相同的。
这个想法是用乘法替换每个 OR 运算符，用加法替换每个 AND 运算符，例如
(P1 OR P2) AND (P4 OR P3) 转换为 hash(P1) * hash(P2) + hash(P4) * hash(P3)。
整数溢出可能是一个可能的问题。
是否有任何适合我的目的的哈希函数或者更好的方法来做我想做的事情？
如果我理解正确的话，您正在创建某种规则引擎，您必须在其中存储预定义的规则，并在数据流入时触发适当的规则。为此，您必须知道每次新数据到达时要执行哪些计算，这就是全局哈希映射的目的。
您遇到的问题是由于两个句法不同的逻辑公式在逻辑上可能是等价的。例如，正如您提到的，(P1 AND P2) 等价于 (P2 AND P1)，但还有更多可能的等价形式，例如 (P1 > a OR P1 = a) 和 (P1 >= a)。由于您的 DSL 不包含 NOT 运算符（否则可能会有更多的逻辑等价），问题得到了缓解，但这并没有完全消除它。
一种可能是取消不能有重复表达式的限制。这会导致一些冗余计算，但这可能是最简单的方法。
如果要使表达式在逻辑上不同，则必须以某种规范形式来表达它们。一种可能是采取以下步骤：
首先，缩小 DSL 的范围，为逻辑上等价的表达式腾出更少的空间。例如，如果DSL有=和>这两个操作符，那么>=就不需要了（当然你可以在用户界面中保留多余的操作符，以保持良好的用户体验，但在您的哈希图中，您可以将这些运算符转换为更基本的运算符）。
其次，您应该为逻辑公式选择规范形式。例如，DNF 或 CNF 将是合适的。
第三，为了使表示中的表达式顺序唯一，您可以利用可以为原子表达式计算哈希值的事实，然后按照哈希值升序对规范表示中的表达式进行排序，例如。
维护非重复表达式的约束需要付出一定的代价，但繁重的计算会在创建新规则时发生，而不是在新数据到达且系统必须尽快触发事件时发生。
我的 DSL 由下一个运算符组成 AND、OR、>、<、>=、<=、=,!=,&
& 表示交集。
在我的系统中，我需要跟踪每个单独的子表达式，例如不能有重复的表达式。我存储了 hash => node_ptr 的全局哈希映射以在树中检索请求的子表达式。
(name = "John" OR age > 25) AND (interests & ["sport", "education"])
包括：
name = "John"、age > 25、name = "John" OR age > 25、interests & ["sport", "education"]，原来的(name = "John" OR age > 25) AND (interests & ["sport", "education"])
总共有5个子表达式需要被散列。
对于谓词很简单，我可以对谓词的文字（字符串形式）进行哈希处理，例如
int <= hash("attr>=100") 或 int <= hash("attr&{'a','b','c'}").
但它不适用于P1 AND P2等复杂表达式，因为P1 AND P2和P2 AND P1实际上是相同的。
这个想法是用乘法替换每个 OR 运算符，用加法替换每个 AND 运算符，例如
(P1 OR P2) AND (P4 OR P3) 转换为 hash(P1) * hash(P2) + hash(P4) * hash(P3)。
整数溢出可能是一个可能的问题。
是否有任何适合我的目的的哈希函数或者更好的方法来做我想做的事情？
如果我理解正确的话，您正在创建某种规则引擎，您必须在其中存储预定义的规则，并在数据流入时触发适当的规则。为此，您必须知道每次新数据到达时要执行哪些计算，这就是全局哈希映射的目的。
您遇到的问题是由于两个句法不同的逻辑公式在逻辑上可能是等价的。例如，正如您提到的，(P1 AND P2) 等价于 (P2 AND P1)，但还有更多可能的等价形式，例如 (P1 > a OR P1 = a) 和 (P1 >= a)。由于您的 DSL 不包含 NOT 运算符（否则可能会有更多的逻辑等价），问题得到了缓解，但这并没有完全消除它。
一种可能是取消不能有重复表达式的限制。这会导致一些冗余计算，但这可能是最简单的方法。
如果要使表达式在逻辑上不同，则必须以某种规范形式来表达它们。一种可能是采取以下步骤：
首先，缩小 DSL 的范围，为逻辑上等价的表达式腾出更少的空间。例如，如果DSL有=和>这两个操作符，那么>=就不需要了（当然你可以在用户界面中保留多余的操作符，以保持良好的用户体验，但在您的哈希图中，您可以将这些运算符转换为更基本的运算符）。
其次，您应该为逻辑公式选择规范形式。例如，DNF 或 CNF 将是合适的。
第三，为了使表示中的表达式顺序唯一，您可以利用可以为原子表达式计算哈希值的事实，然后按照哈希值升序对规范表示中的表达式进行排序，例如。
维护非重复表达式的约束需要付出一定的代价，但繁重的计算会在创建新规则时发生，而不是在新数据到达且系统必须尽快触发事件时发生。