c - C 中判断指针是否属于集合的最快方法是什么？

Question

给定一个结构体上的指针，我需要非常快速查找它是否是集合的一部分(我必须自己定义/实现)。我可能会考虑像 Bloom Filter 这样的技术，但真的不知道如何在指针上执行此操作。

该解决方案需要在 32 和 64 位机器上运行。

编辑:所有这些指针(其中 2k-5k)都指向各种随机内存地址，因为它们的目标是我无法控制的双向链表的元素。这可以改写为:“如何通过创建另一个结构来查找元素是只读双向链表的一部分？”

编辑 2:双向链表可能会随着时间的推移而增长，但我控制的集合不会增长。

Answer 1

从您引用的页面:

Bloom proposed the technique for applications where the amount of source data would require an impracticably large hash area in memory if "conventional" error-free hashing techniques were applied. He gave the example of a hyphenation algorithm for a dictionary of 500,000 words, out of which 90% follow simple hyphenation rules, but the remaining 10% require expensive disk accesses to retrieve specific hyphenation patterns.

如果您只有有 2k-5k 个项目，那么我怀疑您正在谈论“内存中不切实际的大哈希区域”。

简而言之，我推荐一个哈希表。您需要对数据进行一次 O(n) 传递来构建表，然后查找的时间将是 O(1)。