c - 大数据集散列和C实现

Question

我有大量值，范围从 0 - 5463458053。对于每个值，我希望映射一个包含字符串的集合，以便操作查找，即。 e.查找字符串是否存在于该集合中花费的时间最少。请注意，这组值可能不包含 (0 - 5463458053) 中的所有值，但是是的，其中包含大量值。

我目前的解决方案是散列这些值(在 0 - 5463458053 之间)，并且对于每个值，都有一个与该值对应的字符串链表。每次，我想检查给定集合中的字符串，我对值(0 - 5463458053 之间)进行哈希处理，获取链表，然后遍历它以找出它是否包含上述字符串。

虽然这看起来更容易，但有点耗时。你能想到一个更快的解决方案吗？此外，碰撞将是可怕的。它们会导致错误的结果。

另一部分是关于在 C 中实现它。我将如何去做呢？

注意:有人建议改用数据库。我想知道这是否有用。

我有点担心 RAM 自然耗尽。 :-)

Answer 1

你可以有一个哈希集的哈希表。第一个哈希表的键是你的整数。其中的值是哈希集，即以字符串为键的哈希表。

你也可以有一个散列集，键是整数和字符串对。

有许多实现此类数据结构的库(在 C++ 中，标准库正在实现它们，如 std::map 和 std::set)。对于 C，我在想 Glib来自 GTK。

使用哈希技术，内存使用与所考虑的集合(或关系)的大小成正比。例如，您可以接受 30% 的空置率。