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

Re: how to allow integer overflow for calculating hash code of a string?

From: Haifeng Liu <liuhaifeng(at)live(dot)com>
To: Craig James <cjames(at)emolecules(dot)com>
Cc: "pgsql-admin(at)postgresql(dot)org" <pgsql-admin(at)postgresql(dot)org>
Subject: Re: how to allow integer overflow for calculating hash code of a string?
Date: 2012-09-21 02:56:10
Message-ID: BLU0-SMTP13034F84D37BB33ECC7F238B9990@phx.gbl (view raw, whole thread or download thread mbox)
Lists: pgsql-admin
On Sep 20, 2012, at 10:34 PM, Craig James <cjames(at)emolecules(dot)com> wrote:

> On Thu, Sep 20, 2012 at 1:55 AM, Haifeng Liu <liuhaifeng(at)live(dot)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.

In response to


pgsql-admin by date

Next:From: Rural HunterDate: 2012-09-21 09:16:46
Subject: Re: [ADMIN] pg_upgrade from 9.1.3 to 9.2 failed
Previous:From: Craig RingerDate: 2012-09-21 01:18:29
Subject: Re: Backup and Restore from 8.3.0 to 9.1.3

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