如何在前缀树中实现表达式树的缓存策略？

本文共计2319个文字，预计阅读时间需要10分钟。

在上文中，我们提出了一种方法，将前缀树结构转化为一个唯一的字符串，并将该字符串作为key存储在字典中。这种方法非常直接，操作也不复杂（尤其在遍历时间记录详细信息的场景中便于实现）。实际上，这种方法相当简单。

在上一篇文章里我们设法将前缀树构造为一个唯一的字符串，然后使用字符串作为key缓存在字典中。这个想法非常直接，做法也不困难（在遍历时记录详细信息便可）。不过事实上，老赵在思考表达式树的缓存问题时，这种字符串拼接的方式只存在于脑海当中，而上文的实现是为了这一系列文章的完整性而特地编写的。这是因为它的缺点较为明显，正如上文所述，字符串拼接操作较为耗时耗资源，且很容易生成一个长度可观的字符串（并非不能优化，不过实现就复杂了）。于是我们现在设法选择另一个解决方案来处理这个问题。

不过现在，我们先来考虑另一个问题：比较两个字符串是否相同（例如实现一个String.Equals方法）。此时，我们往往会分几步进行：

1. 判断字符串长度是否相等，如果不等，则两个字符串肯定不同。
2. 从头遍历两个字符串，如果找到某一位不相同，则两个字符串不相同。
3. 如果完整遍历完整个字符串，则两者相同。

以上算法基本上是我们可以写出的最高效的比较算法。为什么这么说呢？原因主要有以下两点：

• 我们在比较时，首先使用最容易获得的信息（长度）进行判断，并且在合适的时候（发现某一位不同）及时返回，节省了时间。
• 比较时不需要保存完整信息（比较字符串的第n位时，从0到n-1位字符无需保留），这样在空间上也节省了下来。