Skip site navigation (1) Skip section navigation (2)

Re: cyclical redundancy checksum algorithm(s)?

From: "Marshall" <marshall(dot)spight(at)gmail(dot)com>
To: pgsql-general(at)postgresql(dot)org
Subject: Re: cyclical redundancy checksum algorithm(s)?
Date: 2006-09-27 23:40:11
Message-ID: 1159400411.475689.122570@i42g2000cwa.googlegroups.com (view raw or flat)
Thread:
Lists: pgsql-general
Karen Hill wrote:
> Gene Wirchenko wrote:
>
> > >Yet what happens if there is a collision of the checksum for a row?
> >
> >      Then you get told that no change has occurred when one has.  I
> > would call this an error.
>
> That's exactly what I thought when I read that in his book.  I was
> thinking back to the sha1 and md5 algorithms, maybe a special crc
> algorithm is safe from this.

Because of the Pigeonhole Principle, it is not possible that some
careful selection of hash algorithm will be "safe" from collisions.
Collisions are always possible (assuming the input size is larger
than the output size, which in practice it always is, because hashing
would be pointless otherwise.) One addresses the risk of
collisions probabalistically.

Although sha1 and md5 are currently a la mode, they are
specifically cryptographic hashes, and as a result they have
been chosen for properties that you don't care about if
all you want is a regular hash. CRC is probably a fine
choice; it's popular and well-understood.

The way one deals with the possibility of hash collisions is
to choose an appropriate hash size for the task at hand.

In general, though, I have to agree with Gene; I don't see
that this is a fruitful avenue to pursue unless there are some
*very* specific circumstances that warrant it.


Marshall


In response to

pgsql-general by date

Next:From: Dan LibbyDate: 2006-09-28 02:14:29
Subject: text to point conversion not working. ( cannot cast type text to point )
Previous:From: Lexington LuthorDate: 2006-09-27 23:27:18
Subject: Re: Solution for rolling back many transactions?

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group