具有 O(1) 分期关联查找的静态函数数据结构

Question

我正在寻找具有摊销常数时间关联查找的静态数据结构。我想要执行的唯一操作是查找和构造。功能性也是必须的。我看过手指树，但我似乎无法理解它们。是否有关于它们的任何好的文档，或者更好的是，是否有更简单的静态函数数据结构？

Answer 1

我假设 "functional" 和 "static" 是指不可变结构，在构建后无法修改，"lookup" 是指类似字典的键-值查找和 "construction" 你的意思是从一组给定的元素开始构建数据结构。

在那种情况下，基于哈希表的不可变字典会起作用。这样做的缺点是插入和删除是 O(N)，但您声明这在您的情况下是可以接受的。

根据您使用的编程语言，可用于实现此目的的数据类型可能可用也可能不可用。在 Erlang 中可以使用元组。 Haskell 在 Data.Array.IArray 中有一个不可变数组。

Answer 2

您必须从信息理论的角度来看待这个问题：您存储的 key/value 对越多，您在关联查找中必须识别的键就越多。因此，无论您做什么，您拥有的键越多，您的查找就会越复杂。

只有当您的密钥直接为您提供了您要查找的元素的地址（或类似的东西）时，才有可能进行恒定时间查找。