Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29])
	by malur.postgresql.org with esmtp (Exim 4.72)
	(envelope-from <liuhaifeng@live.com>) id 1TEtPp-0000lX-93
	for pgsql-admin@postgresql.org; Fri, 21 Sep 2012 02:56:29 +0000
Received: from blu0-omc1-s7.blu0.hotmail.com ([65.55.116.18])
	by magus.postgresql.org with esmtp (Exim 4.72)
	(envelope-from <liuhaifeng@live.com>) id 1TEtPj-000407-Eq
	for pgsql-admin@postgresql.org; Fri, 21 Sep 2012 02:56:27 +0000
Received: from BLU0-SMTP130 ([65.55.116.7]) by blu0-omc1-s7.blu0.hotmail.com
	with Microsoft SMTPSVC(6.0.3790.4675);
	Thu, 20 Sep 2012 19:56:19 -0700
X-Originating-IP: [61.170.253.133]
X-EIP: [2uU8lSl4b5g++akXs2MdqYfbYe3svKbj]
X-Originating-Email: [liuhaifeng@live.com]
Message-ID: <BLU0-SMTP13034F84D37BB33ECC7F238B9990@phx.gbl>
Received: from [172.16.224.42] ([61.170.253.133]) by
	BLU0-SMTP130.blu0.hotmail.com over TLS secured channel with
	Microsoft SMTPSVC(6.0.3790.4675); Thu, 20 Sep 2012 19:56:18 -0700
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_770141B3-E581-478E-8475-6E2DF24ABBF1"
MIME-Version: 1.0 (Mac OS X Mail 6.1 \(1498\))
Subject: Re: how to allow integer overflow for calculating hash code of a
	string?
From: Haifeng Liu <liuhaifeng@live.com>
In-Reply-To: 
 <CAFwQ8rcdk68h5kC+77VdPqwPmju3KD1BTkm6Sh4_YYEzcBwcwA@mail.gmail.com>
Date: Fri, 21 Sep 2012 10:56:10 +0800
CC: "pgsql-admin@postgresql.org" <pgsql-admin@postgresql.org>
References: <BLU0-SMTP486A3A8F157C95DD76E23EB99A0@phx.gbl>
	<CAFwQ8rcdk68h5kC+77VdPqwPmju3KD1BTkm6Sh4_YYEzcBwcwA@mail.gmail.com>
To: Craig James <cjames@emolecules.com>
X-Mailer: Apple Mail (2.1498)
X-OriginalArrivalTime: 21 Sep 2012 02:56:18.0757 (UTC)
	FILETIME=[AC77B750:01CD97A4]
X-Pg-Spam-Score: -1.9 (-)
X-Archive-Number: 201209/119
X-Sequence-Number: 40060

--Apple-Mail=_770141B3-E581-478E-8475-6E2DF24ABBF1
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="iso-8859-1"


On Sep 20, 2012, at 10:34 PM, Craig James <cjames@emolecules.com> wrote:

>=20
>=20
> 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.
>=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

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.=

--Apple-Mail=_770141B3-E581-478E-8475-6E2DF24ABBF1
Content-Transfer-Encoding: 7bit
Content-Type: text/html; charset="iso-8859-1"

<html><head><meta http-equiv="Content-Type" content="text/html charset=iso-8859-1"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Sep 20, 2012, at 10:34 PM, Craig James &lt;<a href="mailto:cjames@emolecules.com">cjames@emolecules.com</a>&gt; wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><br><br><div class="gmail_quote">On Thu, Sep 20, 2012 at 1:55 AM, Haifeng Liu <span dir="ltr">&lt;<a href="mailto:liuhaifeng@live.com" target="_blank">liuhaifeng@live.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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.<br>

<span class="HOEnZb"></span><br></blockquote></div><br>Use the bitwise AND operator to mask the hash value with 0x3FFFFFF before each iteration:<br><br>&nbsp; hash = (hash &amp; 67108863) * 31 + s.charAt(i);<br><br>Craig<br>
</blockquote></div><br><div>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, &nbsp;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(). &nbsp;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.</div></body></html>
--Apple-Mail=_770141B3-E581-478E-8475-6E2DF24ABBF1--