Re: consistant failures on a new kind of spam

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Jem wrote:
> Brian I thought that the built-in hash database (Hashed-array-cached) had a 
> fixed size, presumably because a hash collision just overwrites a hash 
> entry. So I thought whether you clean it or not, a collision will lead to a 
> term being overwritten. Or are you saying it grows to a list at collision?
> 
> If it does become a list, how are you able to maintain a static hash file 
> size?

No, sorry I didn't explain that more clearly.  SP uses a fixed size 
array for its hash table.  A term (word or phrase) is hashed into a 32 
bit hash code.  Then that code is mod'd down into an index in the array. 
  If the slot at that index is full SP tries the next index until it 
finds an empty slot (wraps around at end).  That's what I meant about a 
hash table degenerating into a list if the file is nearly full.  SP 
would try all of the slots in the file one after another looking for an 
empty one.  Same thing on look ups.  So an O(1) data structure can 
degenerate into an O(N) one.

It's always best to keep the table about half empty to make collisions
unlikely.  A few collisions here and there don't hurt but a nearly full 
file would be a Bad Thing indeed.

The hash format is designed to be highly resilient.  There are no 
central tables to become inconsistent with the actual contents of the 
file.  That is good in case SP crashes but bad since SP can't tell in 
constant time how many or which slots are actually taken.  That was a 
trade-off I made when I designed the file format.

All the best,
++Brian

-----BEGIN PGP SIGNATURE-----
Version: PGP Desktop 9.5.1 (Build 1557)
Charset: ISO-8859-1

wsBVAwUBRVtFHzxRyEoJfXIFAQh6MQf8D6KiwHX6y9EFOJwtwoM6ZgrsxLVWu33e
3yA9y9u7PaR5kjkSxwrlumd2SBQPLzN0YtTGom03k4ogmrnMjWwsGhnjkQxBp45O
D9Oah6M1LmhnlhW+7SOsm7x5bYREL20FLXaGqV4X1k/eTl1b0TgbXh8zI+RU74mi
HHZvR9WwH5tDk3eJ5KG+1mhVPHgwhLM6izKODzFY06X4cQdmPi2uwnnkMEKXhlMH
wV8XwX624aqE3UYRYTQBhAGLpu4/GHK5Ilac9/kZNtXhianGNTfWIgrzMrnvbibI
4FIZ5SvQEjzUM3ppOtD8eoMLfpWHkfiy5JN1F0qabldjF4C9jCqn5A==
=M5gz
-----END PGP SIGNATURE-----

-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV