散列表达式树

Question

我正在致力于将一些伪智能缓存构建到LINQ query provider中。我想要做的(理想情况下)是在某些场景中使用给定查询的表达式树作为缓存键。但是，我不想存储整个对象图本身，那么从表达式树中获取类似于hashsum的值的快速方法是什么？或者如果我走错了方向，有没有更好的选择？

Answer 1

嗯，其实我觉得这可能很简单。

Expression对象的ToString()方法将为您提供表达式的文本表示，如果您想要的只是计算一个键的等价性，则可以对其进行散列处理。

Answer 2

让我们考虑一下这个问题。假设您希望将(表达式树的散列，结果)存储在映射中。

如果不存储整个树，就无法区分相同的树和散列冲突。

根据定义，散列将较大的集合映射到较小的集合(这就是散列有用的原因)，因此根据定义，您将(至少有可能发生)冲突。

当您获得表达式树时，您将对其进行散列，然后在您的map中查找结果，这将导致两种可能性：

1. 这是一个没有出现在地图中的散列，你以前没见过。你必须让这个表达式运行，因为你没有缓存的结果。
2. 它是映射中的一个散列，但是由于你没有在你的映射中存储产生散列的旧表达式树，所以没有办法比较新传递的表达式和旧的表达式。你可能有一个匹配，也可能有一个冲突，但没有办法区分这两种可能性。无法返回缓存结果，因为它可能是冲突。

此外，即使它不是冲突，即使它与您上次看到的表达式树完全相同，我们如何知道支持对象-数据库、列表等*没有添加、删除或修改元素，使得表达式返回的结果可能与缓存的结果不同？

也就是说，你可以递归地散列一棵树：

hashATree:
if leaf node
  return hash(node)
else
  return hash(node) *OP* hashATree(left.child) *OP* hashATree(right.child)

其中OP是某种运算(可能是乘法)，或者更一般的是hash(node) *OP* accumulate( children.begin(), children.end(), *OP* );

当然，这与我们用来计算表达式树的递归是相同的(除了我们调用node.eval( children);)

Answer 3

您可能可以使用这里提供的代码来完成此任务。http://petemontgomery.wordpress.com/2008/08/07/caching-the-results-of-linq-queries/

这展示了如何解决闭包问题，并支持本地集合。