嵌套作用域内查找的最佳数据结构

Question

例如，有一个树数据结构，其中的每个叶定义了一组用于查找的键：

*
|- A = 1, B = 2
|- *
   |- C = 4
   |- *
      |- D = 5
      |- D = 6, E = 7

我需要一种方法，为任何给定的叶子找到键的价值，而树是被遍历的深度-首先。

我想到了两种方法：

1. 如果在当前叶中找不到该值，请检查其父表的字典等，然后返回到树根。
2. 有一个全局字典，每个叶在被遍历时插入/移除其键。在此全局字典中执行的查找。

最有可能的情况是，每个键都有几个键，每个键大约有3-4个查找。

哪种方法更有效？或者，也许还有另外一种比两者都更好的方法？

Answer 1

您正在实现的编程语言肯定会为名称解析定义精确的规则。我不认为这会导致深度优先搜索。名称解析规则，非常节俭，看起来像这样的想法：

1. 搜索当前的范围，经常只考虑从源代码中当前位置上声明的内容；
2. 当满足某些特定规则时，例如存在某种形式的using / import或其他任何链接到其他作用域的构造，则在该其他范围内执行搜索(所有这些范围，顺序)，并在其中递归：
   1. 搜索给定的范围，
   2. 任何相关嵌套作用域的递归；

​

1. 立即进入包围范围；
2. 从(1)重复，其中“当前”范围是在(3)中确定的。

换句话说，您将逐渐上升到包围作用域的树中，并决定是否搜索任何“外部”引用的范围。像using / import这样的语句会导致作用域之间的引用，这反过来又会导致被视为作用域树的实际上是有向图。

关于查找表的构造，我从一个简单的哈希表开始。对于这些场景，前缀树(尝试)也能很好地工作。

最后但并非最不重要的一点是，除非我在编译几十行或数十万行代码时遇到真正的性能问题，否则我不会太在意查找性能。