performance - 快速搜索的数据结构

Question

如果我必须为研究所的数据网格站开发应用程序。应用程序的目的是每周在上午 10 点到 10 点 30 分之间从数据网格站接收一次数据，然后将其存储到数据结构中，数据仅由数字组成，但数字可能非常长那么从数组、列表、链表、双向链表、队列、优先级队列、堆栈、二叉搜索树、AVL 树、线程二叉树、堆、排序顺序数组和跳过列表中，哪种数据结构最适合给定场景

我想存储排序的数字。排序后的数据可以按升序或降序排列，主要关注的是“快速高效的搜索”。

Answer 1

根据您的描述，我了解到您没有使用数字或数字存储任何其他数据。所以基本上你想知道一个数字是否在集合中。

了解这一点的最快方法是为每个数字设置一组标志。假设您处理从 1 到 1000 的数字。您想知道数字 200 是否在集合中。查看位置 200 标志是真还是假。你看，这是最快的方法，因为你只查一个地方。

当我们在这里讨论布尔标志时，存储一点就足够了。您将决定是否将布尔值存储为位、字节、字或其他形式，具体取决于数字的数量、可用内存和机器的架构。

话虽如此，您可能不得不处理如此多的数字，以至于上述方法不再可行。理论上它会是最快的，但是由于内存有限，交换到硬盘，从它读取很多很多，其他算法可能会更好。您可以选择：

• 连续存储数字并对它们执行二进制搜索
• 将数字存储在二叉树中
• 使用哈希算法

其中哪一个被证明是最有效的，同样取决于您的数据和机器。

Answer 2

这取决于您要执行的搜索类型。如果您只想知道一个数字是否在您的数据集中，那么哈希将非常快并且与数据集的大小无关。而且不需要排序，甚至不需要任何顺序的概念。

如果我可以引用 Perl 的作者 Larry Wall 的话：

对关联阵列进行线性扫描就像试图用加载的 Uzi 将某人打死。

（关联数组是哈希的同义词。）