If I have an array of keys M, and an array of targets N, how can I verify that M[i] exists in N before searching it?

Question

Like the title says, I'm trying to find elements of M that exist in the large constant array N. Most of the time, no element of M will exist in N, so the vast majority of searches done on M are a waste of time.

I'm looking for some way to create an index to check before doing a full-scale search of M. A project similar to mine creates a bit array from the first few bytes of every element of M, and from what I understand, leverages bit level parallelism to search it quickly. I don't understand entirely how this works.

So what tricks can I use to cut down the chance of searching M unnecessarily?

This is a mostly language independent question, but just to be as complete as possible, I'm using C++.

Answer 1

You could build a hashtable with with the values of N as keys.

Then you try to access hash[M[i]], if it returns a value then it exists, that is O(1) (disregarding collisions.)

Answer 2

Since N is static you might consider creating a Perfect Hash function for N. This will make your search guaranteed O(1) time.

The CLR book on algorithms has a chapter on this and wiki page above has links which you might find useful. It might be too complicated, though and you might be hard pressed to find a useful implementation.. Look at Gperf for an implementation.

You could always use a commonly available hash table with expected O(1) though.

I suppose you are storing some extra information which you want to retrieve knowing that it is there? How are you storing those?

You might find a B-Tree useful in that case (industry standard databases usually use a some variant of those), which could even serve as the index! So, you search, and if you find it, you have the data/pointer to it. You will find many implementations for these on the web.

Answer 3

You might be thinking of Bloom filters, which are used for exactly this case. They can give you false positives, in which case you have to search in the real table, but in most cases will tell you from the start if you don't have the item stored.

Hash tables are usually the best option for storage; but if your key space is vastly larger than the number of targets, you'll have a sizable number of hash collisions where you'll have to check if the target stored there is really the key you're looking. If key comparison is expensive, it can quickly become a factor.