Re: g_str_hash

["B. Scott Michel" <scottm CS UCLA EDU>]

BTW: "feedback shift register" == CRC generator == GF(2) poly
division.

"B. Scott Michel" wrote:
> 
> Tim Janik wrote:
> > it of course depends on what kind of string you want to hash, for
> > strings where you mostly care about the tails, you're certainly willing
> > to trade some of the higher bits and thus allow hash collisions for
> > strings that only differ in the beginning characters.
> 
> One could simply code up a 32-bit CRC generator which works nicely
> as a hash function and also takes 5 or so lines (depending on how
> you perform the calculation.) If you want a small number of bits
> for the hash code instead of all 32, mask what you need. Smaller
> bit CRC functions can be had by using invariant polys of smaller
> degree from the back of any good error correction book. And the
> really cool part is that the prob of a collision is 2^{-L}, where
> L is the number of bits in the CRC.
> 
> And it works well with strings and incremental hashing.
> 
> -scooter
> 
> --
>          To unsubscribe: mail gtk-devel-list-request@redhat.com with
>                        "unsubscribe" as the Subject.