[boost] Re: any interest in immutable_string/string pooling ?

From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-10-07 08:58:21

"Bohdan" <warever_at_[hidden]> wrote in message
news:anrvs5$nc4$1_at_main.gmane.org...
> I have question to your implementation. Line from crc_string.hpp :
>
> <code>
> bool operator==(const crc_string<CharT> &other) const  { return crc_ ==
> other.crc_; }
> <\code>
>
> I'm not expert on CRC, but is it correct ? Does crc equality guarantees
100%
> strinds
> equality ? I have doubts about it.

CRC does not have 100% guarantee uniqueness. My implementation is used in a
scenario where I know that the strings must be unique, and so can get away
with this. In a generic solution, the case would need to be handled, perhaps
by comparing the length of the strings and if they are equal, then the
contents should be compared with a standard memcmp(). This will, of course,
add overhead to the algorithm, but the obvious no-match cases will be
handled very efficiently.

Unforunately your has algorithm does not 100% guaranteed unique either.
However, it will (probably) cause less collisions than the CRC value because
of the size of the hash. I use a 16-bit CRC despite storing it in a 32-bit
value - this is just an oversight in my code. I suggest you take a look at
the SAH1 algorithm - this has not, AFAIK, ever been seen to generate a
duplicate value; unlike MD5.

-- Craig