🚀 go-pugleaf

In article <19990713.200500.0AA80202.PEaa@pierrot.co.uk>, Terrance 
Richard Boyes wrote:
> I'm looking for an efficient way to check for duplicate Message-IDs
> in a large NewsHistory file against the output of NEWNEWS (or XOVER
> after extracting the Message-ID).

> Any thoughts on the best way to do it in C ?

That's what hash tables are for, surely. I'm pretty sure that's how 
PERL does it under the hood.

Most C++ libraries include some form of Dictionary, which works like 
the PERL method, and is usually implemented using hash tables. 

I seem to remember standard Unix library functions to do hash tables - 
were they called hcreate/hsearch/hdestroy?

Or, if there isn't anything in your library, look it up in any book on 
algorithms.

The basic idea is that you create an array large enough to hold at 
least the expected number of message ID's. 

You take the ID string, and compute a hash code which is guaranteed to 
be between 0 and the size of the array. You look in the array at that 
slot - if it is empty, you haven't seen that ID before, and you place 
it in the slot. If it is not empty, you compare the actual message ID 
stored in the slot. If it is the same, you have had the ID before. What 
to do if it is different (i.e. your new ID and the one in the slot hash 
to the same value) varies. 

Some algorithms perform some computation on the hash code, to give a 
new slot number, repeating until the ID or an empty slot is found. The 
trick here is to choose a computation which will eventually visit all 
the slots only once - usually a prime number of slots is chosen, and 
the computation is a simple addition.

Other algorithms make each slot actually a linked list of all ID's that 
hash to the same code, and the list is searched linearly. This method 
allows the initial array to be smaller than the number of ID's, and is 
particularly good if the number of ID's is not known in advance.

The efficiency of the hash table depends heavily on the suitability of 
the initial hashing algorithm - if the ID's all hash to different 
numbers, it is very fast. If they all hash to the same number, it is as 
slow as a linear search.

-- 
Nikki Locke, Trumphurst Ltd.      PC & Unix consultancy & programming
nikki@trmphrst.demon.co.uk            http://www.trumphurst.com/