From: Haifeng Liu <liuhaifeng@live.com>
To: Craig James <cjames@emolecules.com>
Cc: pgsql-admin@postgresql.org <pgsql-admin@postgresql.org>
Subject: Re: how to allow integer overflow for calculating hash code of a string?
Date: Mon, 29 Oct 2012 19:07:51 +0800
Message-ID: <BLU0-SMTP411D38C917CB53CD74B137CB9620@phx.gbl> (raw)
In-Reply-To: <CAFwQ8rdvACJpQB=2y7UyUzxTq4XqA7mRQ3Nm4HxtFNFhFkeLrA@mail.gmail.com>
References: <BLU0-SMTP486A3A8F157C95DD76E23EB99A0@phx.gbl>
<CAFwQ8rcdk68h5kC+77VdPqwPmju3KD1BTkm6Sh4_YYEzcBwcwA@mail.gmail.com>
<BLU0-SMTP13034F84D37BB33ECC7F238B9990@phx.gbl>
<CAFwQ8rdvACJpQB=2y7UyUzxTq4XqA7mRQ3Nm4HxtFNFhFkeLrA@mail.gmail.com>
I got a way which works fine: use bigint first, and then convert it to bit(32), and convert it to int4 at last.
declare i integer := 0;
declare h bigint := 0;
begin
for i in 1..length(str) loop
h = (h * 31 + ascii(substring(str, i, 1))) & 4294967295;
end loop;
return cast(cast(h as bit(32)) as int4);
end;
I did some tests which include both positive and negative results, seems all Ok.
On Sep 21, 2012, at 11:21 PM, Craig James <cjames@emolecules.com> wrote:
> On Thu, Sep 20, 2012 at 7:56 PM, Haifeng Liu <liuhaifeng@live.com> wrote:
>
> On Sep 20, 2012, at 10:34 PM, Craig James <cjames@emolecules.com> wrote:
>
>>
>>
>> On Thu, Sep 20, 2012 at 1:55 AM, Haifeng Liu <liuhaifeng@live.com> wrote:
>> I want to write a hash function which acts as String.hashCode() in java: hash = hash * 31 + s.charAt(i)... but I got integer out of range error. How can I avoid this? I saw java do not care overflow of int, it just make the result negative.
>>
>>
>> Use the bitwise AND operator to mask the hash value with 0x3FFFFFF before each iteration:
>>
>> hash = (hash & 67108863) * 31 + s.charAt(i);
>>
>> Craig
>
> Thank you, I believe your solution is OK for a hash function, but I am aiming to create a hash function that is consistent with the one applications use. I know postgresql 9.1 has a hash function called hashtext, but I don't know what algorithm it use, and I also see that it's not recommended to relay on it. So I am trying to create a hash function which behaves exactly the same as java.lang.String.hashCode(). The later one may generate negative hash value. I guess when the number is overflowing, the part out of range will be ignored, and if the highest bit get 1, the hash value turn to negative value.
>
> You are probably doing something where you want the application and the database to implement the exact same function, but if you stick to the Java built-in function, you will only have control over one implementation of that function. What happens if someone working on Java changes the how the Java internals work?
That's not the trouble, just create a hash tool which copies the code of java.lang.String.hashCode() and use that tool instead will resolve this. The key is, I know and I can reimplement the algorithm.
>
> A better solution would be to implement your own hash function in Postgres, and then once you know exactly how it will work, re-implement it in Java with your own code. That's the only way you can ensure consistency between the two.
>
> Craig
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-admin@postgresql.org
Cc: liuhaifeng@live.com, cjames@emolecules.com
Subject: Re: how to allow integer overflow for calculating hash code of a string?
In-Reply-To: <BLU0-SMTP411D38C917CB53CD74B137CB9620@phx.gbl>
References: <BLU0-SMTP486A3A8F157C95DD76E23EB99A0@phx.gbl> <CAFwQ8rcdk68h5kC+77VdPqwPmju3KD1BTkm6Sh4_YYEzcBwcwA@mail.gmail.com> <BLU0-SMTP13034F84D37BB33ECC7F238B9990@phx.gbl> <CAFwQ8rdvACJpQB=2y7UyUzxTq4XqA7mRQ3Nm4HxtFNFhFkeLrA@mail.gmail.com> <BLU0-SMTP411D38C917CB53CD74B137CB9620@phx.gbl>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox