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

From: Bohdan (warever_at_[hidden])
Date: 2002-10-07 11:43:07

"Craig Henderson" <cdm.henderson_at_[hidden]> wrote in message
news:ans3st$4fe$1_at_main.gmane.org...
>
> "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.

Which algorithm ?
     ... If you are talking about hashof_ method than it doesn't
need to give absolutely unique values. And it is not my, i borrowed it from one
of stl implementations. I'm sure there no crc or hash algorithms that give you
100% unique values :o), so you should add "&& <real string comparison>" to make
crc_string correct.
     ... If you are talking about whole immutable_string / value pooling than
you are wrong. It guarantees string equality from references equality since
all used immutable_string values are uniquelly present in values pool.
Again this is not my idea :)

> 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.

As i said i'm not expert neither in crc nor in cryptography :( , but using crc
as
hash code seems interesting. I'll look at SAH1, MD5, boost::crc when i have
time.

Thanks for help/ideas.

>
> -- Craig
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>