Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!news-out.readnews.com!transit3.readnews.com!news-out.news.tds.net!newsreading01.news.tds.net!53ab2750!not-for-mail From: "Jan Burse" Subject: Re: hashCode Message-ID: <50269FD3.56659.calajapr@time.synchro.net> X-Comment-To: Roedy Green Newsgroups: comp.lang.java.programmer In-Reply-To: <50269FD1.56651.calajapr@time.synchro.net> References: <50269FD1.56651.calajapr@time.synchro.net> X-FTN-AREA: COMP.LANG.JAVA.PROGRAMMER X-FTN-MSGID: 1:261/38 cb6d0703 X-FTN-REPLY: 1:261/38 8dbf78a7 Content-Type: text/plain; charset=IBM437 Content-Transfer-Encoding: 8bit X-Gateway: time.synchro.net [Synchronet 3.16a-Win32 NewsLink 1.98] Lines: 31 Date: Sat, 11 Aug 2012 18:17:56 GMT NNTP-Posting-Host: 69.21.70.65 X-Complaints-To: news@tds.net X-Trace: newsreading01.news.tds.net 1344709076 69.21.70.65 (Sat, 11 Aug 2012 13:17:56 CDT) NNTP-Posting-Date: Sat, 11 Aug 2012 13:17:56 CDT Organization: tds.net Xref: csiph.com comp.lang.java.programmer:17712 To: Roedy Green From: Jan Burse 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. --- BBBS/Li6 v4.10 Dada-1 * Origin: Prism bbs (1:261/38) --- Synchronet 3.16a-Win32 NewsLink 1.98 Time Warp of the Future BBS - telnet://time.synchro.net:24