Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #17682

Re: hashCode

Path csiph.com!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail
From Jan Burse <janburse@fastmail.fm>
Newsgroups comp.lang.java.programmer
Subject Re: hashCode
Date Sat, 11 Aug 2012 18:58:04 +0200
Organization albasani.net
Lines 25
Message-ID <k062us$4ei$1@news.albasani.net> (permalink)
References <563f186a-edb3-4311-ae48-3af7decfce2c@googlegroups.com> <qgna285gdrh2ckdr3f7ct2sp9bneaamo94@4ax.com> <feb852c5-c9aa-439a-94eb-339c5e213ccf@googlegroups.com> <hnhc28hld8lc3ln3qe3cg044br2t6r03gr@4ax.com>
Mime-Version 1.0
Content-Type text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding 7bit
X-Trace news.albasani.net kHM1q2XRnxCuhdBq8bNLfFRIuCwrYRqp3ybgYL7Ls5vXjDaVzu/nAPDoHxl309FJnvuDYYr0/AGkf65GB0Dz2OsNv1N2+dLpM1l7omxzTv6MP4fIBPQiLzS2kijRbGL0
NNTP-Posting-Date Sat, 11 Aug 2012 16:58:05 +0000 (UTC)
Injection-Info news.albasani.net; logging-data="T+rYf/cNklFvRLi/BYOGfxCocZ2mKCMJBMrfcKTkRadjHhyxjeOjHyZcC+kpPcmzxOtpSAZFtrTQr+vV/1aF65nTDwP8Fb0slb525VtFRu/+7/DtysvmxdkAaC090EJW"; mail-complaints-to="abuse@albasani.net"
User-Agent Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:14.0) Gecko/20120715 Firefox/14.0.1 SeaMonkey/2.11
In-Reply-To <hnhc28hld8lc3ln3qe3cg044br2t6r03gr@4ax.com>
Cancel-Lock sha1:JLoxyR1DUlTs0VrCv/kr0YscGVg=
Xref csiph.com comp.lang.java.programmer:17682

Show key headers only | View raw

Roedy Green schrieb:
> If you had a
> large number of fields, the multiply effect could fall off the left
> hand end.

Actually this does not happen, since you multiply with 31,
which is 1+2+4+8+16. So that:

     a*31+b = a*16+a*8+a*4+a*2+a+b

So for a HashMap that uses an index = hash & (2^n - 1) (which is
the same as hash mod 2^n), the impact of a will be still seen,
even when it occurs at the very left hand side.

There is some Microsoft C# HashMap implementation which does
not use mod 2^n, but instead some primes. In case the
implementation choses 31 as the designated prime, all
information but for the first field will be lost. But since
mod 2^32 is also applied, this might not be completely true.

For 2^n I don't know exactly how the impact could be
described. I guess in a HashMap with index = hash mod 2^1 the
hash amounts to a parity bit, since the sum in a+b acts like
an xor on the first right hand bit. But 2^n with n>1 the
31 multiplication is a little more crude.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

hashCode bob smith <bob@coolfone.comze.com> - 2012-08-10 08:47 -0700
  Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 12:13 -0400
    Re: hashCode markspace <-@.> - 2012-08-10 10:13 -0700
      Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 13:38 -0400
        Re: hashCode rossum <rossum48@coldmail.com> - 2012-08-11 10:36 +0100
  Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-10 12:34 -0400
    Re: hashCode bob smith <bob@coolfone.comze.com> - 2012-08-10 15:22 -0700
      Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-10 15:32 -0700
        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 19:30 -0400
          Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:24 -0700
            Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:15 -0400
              Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:29 -0400
                Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-11 22:43 -0400
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:54 -0400
                Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 21:46 -0700
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 16:53 -0400
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 17:00 -0400
      Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 19:27 -0400
        Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-12 17:06 +0200
          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 16:59 -0400
            Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-13 19:17 +0200
              Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-19 19:42 -0400
                Re: hashCode Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-21 10:30 +0000
              Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-19 19:47 -0400
                Re: hashCode Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-21 10:43 +0000
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-27 19:04 -0400
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-27 16:55 -0700
                Re: hashCode markspace <-@.> - 2012-08-27 17:03 -0700
                Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-27 17:49 -0700
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-27 21:37 -0400
                Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-27 18:58 -0700
                Re: hashCode markspace <-@.> - 2012-08-27 21:19 -0700
                Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-28 01:06 -0700
                Re: hashCode markspace <-@.> - 2012-08-28 09:19 -0700
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-28 16:33 -0700
                Re: hashCode markspace <-@.> - 2012-08-28 17:02 -0700
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 11:06 -0700
                Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-29 14:49 -0400
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 13:40 -0700
                Re: hashCode Gene Wirchenko <genew@ocis.net> - 2012-08-29 18:02 -0700
                Re: hashCode Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2012-08-31 00:52 +0200
                Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-30 21:43 -0400
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-30 21:52 -0400
                Re: hashCode Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2012-08-31 04:18 +0200
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 09:08 -0600
                Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-31 11:38 -0400
                Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-31 17:55 +0200
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 09:56 -0600
                Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-31 14:32 -0400
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 14:38 -0600
                Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-31 15:33 -0700
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 16:41 -0600
                Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-31 16:26 -0700
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-09-02 11:54 -0600
                Re: hashCode Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2012-09-03 00:47 +0200
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-09-03 21:44 -0600
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-31 09:08 -0600
                Re: hashCode Robert Klemme <shortcutter@googlemail.com> - 2012-08-31 17:58 +0200
                Re: hashCode markspace <-@.> - 2012-08-29 11:51 -0700
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 13:28 -0700
                Re: hashCode markspace <-@.> - 2012-08-29 16:05 -0700
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-29 16:23 -0700
                Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-29 20:56 -0400
                Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-30 11:19 +0200
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-30 10:03 -0700
                Re: hashCode Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 18:34 +0000
                Re: hashCode Jim Janney <jjanney@shell.xmission.com> - 2012-08-30 08:11 -0600
                Re: hashCode Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-30 10:06 -0700
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-30 19:16 -0400
                Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-28 13:58 -0700
                Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-28 13:56 -0700
                Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-28 14:07 -0700
                Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-28 14:38 -0700
                Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-27 21:12 -0400
      Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-11 07:58 -0400
        Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:29 -0700
          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:16 -0400
      Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-12 03:46 -0700
      Re: hashCode Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-08-12 12:23 -0400
        Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-12 09:40 -0700
          Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-12 13:59 -0400
            Re: hashCode Patricia Shanahan <pats@acm.org> - 2012-08-12 11:17 -0700
          Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 17:02 -0400
        Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-12 19:03 +0200
  Re: hashCode Roedy Green <see_website@mindprod.com.invalid> - 2012-08-10 12:17 -0700
    Re: hashCode Lew <lewbloch@gmail.com> - 2012-08-10 12:45 -0700
      Re: hashCode Roedy Green <see_website@mindprod.com.invalid> - 2012-08-11 04:54 -0700
        Re: hashCode Joerg Meier <joergmmeier@arcor.de> - 2012-08-11 18:25 +0200
          Re: hashCode Mike Winter <usenet@michael-winter.me.invalid> - 2012-08-11 18:53 +0100
        Re: hashCode Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-08-11 09:56 -0700
        Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-11 18:58 +0200
        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:40 -0400
      Re: hashCode rossum <rossum48@coldmail.com> - 2012-08-11 18:47 +0100
    Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-10 19:25 -0400
      Re: hashCode Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-08-11 08:00 -0400
        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 09:49 -0400
  Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-11 15:33 +0200
    Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-11 15:34 +0200
    Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:34 -0700
      Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 16:37 -0700
      Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-11 22:19 -0400
        Re: hashCode Lew <noone@lewscanon.com> - 2012-08-11 21:48 -0700
    Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-12 12:08 +0200
      Re: hashCode Jan Burse <janburse@fastmail.fm> - 2012-08-12 12:18 +0200
      Re: hashCode Lew <noone@lewscanon.com> - 2012-08-12 11:27 -0700
        Re: hashCode Arne Vajhøj <arne@vajhoej.dk> - 2012-08-12 17:11 -0400

csiph-web