Re: Deletions from hash table

John Chandler wrote:
>>Date: Wed, 30 Mar 2005 15:09:53 -0500
>>From: Brian Burton <[email protected]>
> I gather that the hashing is into a table of fixed size, 
> with linear probing to resolve collisions.
> 
> This might be an ignorant question,
> but as a matter of academic interest, how are deletions handled?
> How is the breaking of a chain of linear probes avoided?
> (If there's a reference I should read, just tell me where to look.)

Sorry that's proprietary information available only with a source 
license.  BWAHAHAHA  sorry - feeling silly today :-)

When deleting terms from the hash table I simply zero out the counts in 
their records.  The next time cleanup (or purge) is run the hash file is 
rebuilt by creating an empty one and copying over all records with 
non-zero counts (rehashing in the process).

That method leaves the keys for any removed records in place both to 
preserve the chains and to allow the term to be readded (is that a 
word?) before the next cleanup is done (for example, when correcting a 
misclassified message).

All the best,
++Brian


-------------------------------------------------------
This SF.net email is sponsored by Demarc:
A global provider of Threat Management Solutions.
Download our HomeAdmin security software for free today!
http://www.demarc.com/info/Sentarus/hamr30