What's the fastest way to figure out if a poin

Question

Given a pointer on a struct, I need to very quickly find whether it is part of a set (that I have to define/implement myself). I may consider a technique like Bloom Filter, but don't really know how to do it on a pointer.

The solution needs to work on 32 and 64 bits machine.

Edit: All those pointers (2k-5k of them) points to various random memory addresses since they target an element of a doubly linked list I have no control on. This can be rephrased as: "How to find in an element is part of a read-only doubly linked list by creating another structure aside?"

Edit 2: The doubly linked list may growth with the time, but not the set I am controlling.

Answer 1

From the page you referenced:

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.

If you only have 2k-5k items then I doubt you're talking about an "impracticably large hash area in memory".

In short, I'd recommend a hash table. You'd need to do one O(n) pass over the data to build the table, and then lookups would be O(1).