对一个表达式树进行哈希处理

Question

我正在构建一些伪智能缓存到一个 LINQ 查询提供程序 中。理想情况下，我想在某些场景中使用给定查询的表达式树作为缓存键。然而，我不想存储整个对象图本身，那么从表达式树获取类似哈希值的快速方法是什么？或者，如果我走错了方向，有更好的选择吗？

- Rex M

Answer 1

你可以使用这里提供的代码来实现它。 http://petemontgomery.wordpress.com/2008/08/07/caching-the-results-of-linq-queries/

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

- Pete Montgomery

---

如果您能在这里包含相关的部分，那就太好了。人们来这里是为了寻找答案，而不是链接...除非您能保证您的博客将永远存在，否则如果它关闭了，这个答案将变得无用。 - cHao

他基本上使用.ToString()。 - Sedat Kapanoglu

Answer 2

让我们来思考一下。你想在一个映射中存储（表达式树的哈希值，结果）。

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

按照定义，哈希将一个更大的集合映射到一个较小的集合中（这就是为什么哈希很有用），所以按照定义，会发生（至少可能发生）冲突。

当你得到一个表达式树时，你会对它进行哈希，然后在映射中查找结果，这会导致两种可能性：

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)）

- tpdi

---

就事论事地说，哈希函数并不总是将一个大集合映射到一个小集合，比如完美哈希函数。 - RossFabricant

你说的碰撞问题在理论上是正确的，但实际上并不重要。MD5和SHA也有可能发生碰撞，但我们仍然使用它们，因为它们很实用。我需要一个实用的哈希函数，而不是一个数学上无法发生碰撞的哈希函数。 - Rex M

关于后备存储同步问题的解决，我已经解决了这些问题。然而，我不太放心使用当前的缓存键入方法（存储表达式树本身）进行生产。 - Rex M

Answer 3

嗯，实际上我认为这可能相当简单。

Expression对象的ToString()方法将为您提供表达式的文本表示形式，如果您只想评估密钥的等效性，则可以对其进行哈希处理。

- Tim Jarvis

---

这并没有包含表达式树的完整哈希值...许多表达式树可能具有相同的字符串值，但底层节点不同。你有什么建议吗？我也需要完成这个任务。我在考虑创建一个哈希访问器，它特别知道在ConstantExpressions的基础值上包括并调用GetHashCode。你觉得怎么样？ - Jeff

我的理解是这是表达式树的完整文本，例如，使用带有where子句和projection的查询时，我得到以下结果.....value(Quest.Intersect.Core.DataHubQueryableTable1[Quest.Intersect.TestHarness.Customer]).Where(cust => (cust.LastName = "jarvis")).Select(cust => new <>f__AnonymousType12(CompID = cust.CompanyID, LastName = cust.LastName)) - Tim Jarvis

正如你所看到的，这包含了计算出来的常量和匿名类等。在我看来，这个的哈希应该足够好地成为字典中的一个键......不过话说回来，另一种选择就像你建议的那样，创建一个访问者来创建每个节点/叶子的复合哈希。 - Tim Jarvis