Re: [HACKERS] qsort again (was Re: Strange Create

At 12:19 PM 2/16/2006, Scott Lamb wrote:
>On Feb 16, 2006, at 8:32 AM, Ron wrote:
>>Let's pretend that we have the typical DB table where rows are
>>~2-4KB apiece.  1TB of storage will let us have 256M-512M rows in
>>such a table.
>>
>>A 32b hash code can be assigned to each row value such that only
>>exactly equal rows will have the same hash code.
>>A 32b pointer can locate any of the 256M-512M rows.
>>
>>Now instead of sorting 1TB of data we can sort 2^28 to 2^29 32b
>>+32b= 64b*(2^28 to 2^29)=  2-4GB of pointers+keys followed by an
>>optional pass to rearrange the actual rows if we so wish.
>
>I don't understand this.
>
>This is a true statement: (H(x) != H(y)) => (x != y)
>This is not: (H(x) < H(y)) => (x < y)
>
>Hash keys can tell you there's an inequality, but they can't tell you
>how the values compare. If you want 32-bit keys that compare in the
>same order as the original values, here's how you have to get them:
For most hash codes, you are correct.  There is a class of hash or
hash-like codes that maintains the mapping to support that second statement.

More later when I can get more time.
Ron