Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TTAJD-0002tU-RN for pgsql-admin@postgresql.org; Tue, 30 Oct 2012 11:48:39 +0000 Received: from blu0-omc1-s21.blu0.hotmail.com ([65.55.116.32]) by magus.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TTAJ8-0005jn-5T for pgsql-admin@postgresql.org; Tue, 30 Oct 2012 11:48:39 +0000 Received: from BLU0-SMTP411 ([65.55.116.8]) by blu0-omc1-s21.blu0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4675); Tue, 30 Oct 2012 04:48:29 -0700 X-Originating-IP: [61.170.228.55] X-EIP: [Q0s12b83bPC+AhjNY2N0XuKD21Y2jPSX] X-Originating-Email: [liuhaifeng@live.com] Message-ID: Received: from [172.16.224.42] ([61.170.228.55]) by BLU0-SMTP411.blu0.hotmail.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Tue, 30 Oct 2012 04:48:28 -0700 Content-Type: multipart/alternative; boundary="Apple-Mail=_BE68438F-1753-4B7A-B3EE-4A0554377234" MIME-Version: 1.0 (Mac OS X Mail 6.2 \(1499\)) Subject: Re: how to allow integer overflow for calculating hash code of a string? From: Haifeng Liu In-Reply-To: Date: Mon, 29 Oct 2012 19:07:51 +0800 CC: "pgsql-admin@postgresql.org" References: To: Craig James X-Mailer: Apple Mail (2.1499) X-OriginalArrivalTime: 30 Oct 2012 11:48:28.0971 (UTC) FILETIME=[7A77F7B0:01CDB694] X-Pg-Spam-Score: -0.6 (/) X-Archive-Number: 201210/126 X-Sequence-Number: 40242 --Apple-Mail=_BE68438F-1753-4B7A-B3EE-4A0554377234 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="us-ascii" 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 :=3D 0; declare h bigint :=3D 0; begin for i in 1..length(str) loop h =3D (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 wrote: > On Thu, Sep 20, 2012 at 7:56 PM, Haifeng Liu = wrote: >=20 > On Sep 20, 2012, at 10:34 PM, Craig James = wrote: >=20 >>=20 >>=20 >> On Thu, Sep 20, 2012 at 1:55 AM, Haifeng Liu = wrote: >> I want to write a hash function which acts as String.hashCode() in = java: hash =3D 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. >>=20 >>=20 >> Use the bitwise AND operator to mask the hash value with 0x3FFFFFF = before each iteration: >>=20 >> hash =3D (hash & 67108863) * 31 + s.charAt(i); >>=20 >> Craig >=20 > 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. >=20 > 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. >=20 > 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. >=20 > Craig --Apple-Mail=_BE68438F-1753-4B7A-B3EE-4A0554377234 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii" 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 =3D 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 =3D (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

= --Apple-Mail=_BE68438F-1753-4B7A-B3EE-4A0554377234--