6.1 自动完成

在网络世界中，自动完成 是一种让我们无需搜索即可快速查找想要查找内容的方法。 通常，它的工作原理是获取我们正在键入的字母，然后查找所有以这些字母开头的单词。 有些自动完成工具甚至可以让我们输入短语的开头，并为我们完成短语。 例如，Google 搜索中的自动完成功能向我们表明，即使几年后，贝蒂·怀特的 SNL 出场仍然很受欢迎（这不足为奇 - 她是个厉害人物）。 它向我们显示了我们最近访问过并想在地址栏中键入时重新访问的 URL，并且它可以帮助我们记住登录名。 所有这些功能都是为了帮助我们更快地访问信息而构建的。 其中一些，例如 Google 的搜索框，由数 TB 的远程信息支持。 其他一些，例如我们的浏览器历史记录和登录框，由小得多的本地数据库支持。 但它们都让我们以更少的工作量获得我们想要的东西。

在本节中，我们将构建两种不同类型的自动完成。 第一种使用列表来记住用户最近通信过的 100 个联系人，尽量减少内存使用。 我们的第二个自动完成为更大的列表提供更好的性能和可扩展性，但每个列表使用更多的内存。 它们的结构、使用的方法以及完成操作所需的时间都不同。 让我们首先从最近联系人的自动完成开始。