Path: csiph.com!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail From: Jan Burse Newsgroups: comp.lang.java.programmer Subject: Re: hashCode Date: Sat, 11 Aug 2012 18:58:04 +0200 Organization: albasani.net Lines: 25 Message-ID: References: <563f186a-edb3-4311-ae48-3af7decfce2c@googlegroups.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: Cancel-Lock: sha1:JLoxyR1DUlTs0VrCv/kr0YscGVg= Xref: csiph.com comp.lang.java.programmer:17682 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.