Re: performance of HashSet with strings and integers

From:

Lew <lew@lewscanon.com>

Newsgroups:

comp.lang.java.programmer

Date:

Wed, 7 Oct 2009 08:16:47 -0700 (PDT)

Message-ID:

<7e5971f7-e672-4971-807d-0c9cedad8580@k41g2000vbt.googlegroups.com>

On Oct 7, 10:59 am, Patricia Shanahan <p...@acm.org> wrote:

Pascal Lecointe wrote:

On 7 oct, 16:06, Patricia Shanahan <p...@acm.org> wrote:

The equals method only gets called if the HashSet contains an element
whose hash code is equal to the probe's hash code but that is not the
same object as the probe. That is very unlikely in a test with so few
objects.

Not really. If I remember correctly, the equals is always called
(because same
hash not imply same object). But in this case, the equals first test
that the
references are the same. As the Strings of the example are all in the
constant pool,
the references are the same, and so the equals test is fast.

The match test in HashMap's getEntry is such that either hash code
mismatch or reference equality prevents execution of the equals call.
The implementation of the HashSet contains uses the HashMap containsKey,
which uses getEntry.

Note also that typical implementations of 'equals()' that do not do
mere reference equality do check reference equality first, and only
compare attributes if the references differ. Of course, there's no
guarantee that any particular 'equals()' implementation does this. In
the case of the logic just described, it may well be that reference
equality is checked twice - once by the 'Map' and once by the element
- before value equality is finally invoked.

To review:

HashMap equality checks:
  hashCode(): if unequal, no need to continue
  reference == : if 'true', no need to continue
  value equality: return result

--
Lew