c - 查找大量数据的数据结构

Question

我需要根据大量数据进行查找。该数字可能在 1 - 2^32 范围内。根据输入，我需要返回一些其他数据结构。我的问题是我应该使用什么数据结构来有效地保存它？

如果数字在 1 到 5000 的范围内，我会使用一个给我 O(1) 查找的数组。但是当我的输入数字变大时，使用数组变得不切实际，因为内存需求会很大。

因此，我试图研究一种能够快速产生结果并且不是很重的数据结构。

任何线索任何人？

编辑：

使用数组是没有意义的，因为我可能只有 100 或 200 个索引要存储。

阿布舍克

score 1 · Accepted Answer

unordered_map 或 map，取决于您使用的 C++ 版本。

C 中的一个简单解决方案，假设您已经声明最多 200 个元素只是一个具有索引和数据指针的结构数组（或两个数组，一个索引和一个数据指针，其中 index[i] 对应于数据[一世]）。线性搜索数组以查找所需的索引。使用少量元素（200），这将非常快。

score 0 · Accepted Answer

一种可能性是Judy Array，它是一个稀疏关联数组。有一个可用的C 实现。我对这些没有任何直接的经验，尽管它们看起来很有趣，如果你有时间的话可能值得一试。

另一个（可能更正统的）选择是hash table。哈希表是将键映射到值的数据结构，并提供快速查找和插入时间（前提是选择了一个好的哈希函数）。然而，他们没有提供的一件事是有序遍历。

有许多 C 实现。一个快速的谷歌搜索出现了uthash这似乎是合适的，特别是因为它允许您使用任何值类型作为键（许多实现假定字符串作为键）。在您的情况下，您想使用整数作为键。

2 回答 2