In 'HashMap.put', "if (e.hash == hash && eq(k, e.key))" ?

Discussion in 'Java' started by Red Orchid, Jan 30, 2006.

  1. Red Orchid

    Red Orchid Guest

    The 'HashMap.put' has the code "if (e.hash == hash && eq(k, e.key))".
    Do you think that the 'e.hash == hash' is required ?

    I think that the "if (k == e.key || k.equals(e.key))" is proper.

    For further details,
    the following codes are parts of 'HashMap'.

    <code>
    public V put(K key, V value) {
    K k = maskNull(key);
    int hash = hash(k);
    int i = indexFor(hash, table.length);

    for (Entry<K,V> e = table; e != null; e = e.next) {
    if (e.hash == hash && eq(k, e.key)) { // #1
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
    }
    }
    ...

    static int indexFor(int h, int length) {
    return h & (length-1); // #2
    }

    static boolean eq(Object x, Object y) {
    return x == y || x.equals(y); // #3
    }

    </code>

    The linked list of the 'table' is heterogeneous with
    hash value. That is, when hash value of 'E0' is 5
    and one of 'E1' is 6, both 'E0' and 'E1' can exist in
    the same bucket 'table' because of the above #2
    ( 00 & 10 = 00, 01 & 10 = 00).

    But, it do not justify the code "if (e.hash == hash" of #1.

    Because, ...

    a) The functions of 'Map' puts/gets the value 'V' that is
    mapped by the key 'K', not by the hash value.

    b) The execution time of "k == e.key" by #3 is not large
    than one of 'e.hash == hash'.

    Therefore, I think,
    The code "if (k == e.key || k.equals(e.key))" is proper
    instead of #1. #1 is overabundance.

    I think that if there is overabundance in a library,
    it means that the library is not optimised.

    What is your opinion ?
    Thanks.
    Red Orchid, Jan 30, 2006
    #1
    1. Advertising

  2. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Red Orchid schreef:
    > The 'HashMap.put' has the code "if (e.hash == hash && eq(k, e.key))".
    > Do you think that the 'e.hash == hash' is required ?
    >
    > I think that the "if (k == e.key || k.equals(e.key))" is proper.
    >
    > For further details,
    > the following codes are parts of 'HashMap'.
    >
    > <code>
    > public V put(K key, V value) {
    > K k = maskNull(key);
    > int hash = hash(k);
    > int i = indexFor(hash, table.length);
    >
    > for (Entry<K,V> e = table; e != null; e = e.next) {
    > if (e.hash == hash && eq(k, e.key)) { // #1
    > V oldValue = e.value;
    > e.value = value;
    > e.recordAccess(this);
    > return oldValue;
    > }
    > }
    > ...
    >
    > static int indexFor(int h, int length) {
    > return h & (length-1); // #2
    > }
    >
    > static boolean eq(Object x, Object y) {
    > return x == y || x.equals(y); // #3
    > }
    >
    > </code>
    >
    > The linked list of the 'table' is heterogeneous with
    > hash value. That is, when hash value of 'E0' is 5
    > and one of 'E1' is 6, both 'E0' and 'E1' can exist in
    > the same bucket 'table' because of the above #2
    > ( 00 & 10 = 00, 01 & 10 = 00).
    >
    > But, it do not justify the code "if (e.hash == hash" of #1.
    >
    > Because, ...
    >
    > a) The functions of 'Map' puts/gets the value 'V' that is
    > mapped by the key 'K', not by the hash value.
    >
    > b) The execution time of "k == e.key" by #3 is not large
    > than one of 'e.hash == hash'.
    >
    > Therefore, I think,
    > The code "if (k == e.key || k.equals(e.key))" is proper
    > instead of #1. #1 is overabundance.
    >
    > I think that if there is overabundance in a library,
    > it means that the library is not optimised.
    >
    > What is your opinion ?


    I definitely agree that the code could be much clearer, but in a hurry
    (and after some debugging experience with disappearing values), I am
    pretty sure I can tell you that this test is to make sure that different
    keys that give the same hash code can still be stored, that is what the
    linked list is for.

    H.

    - --
    Hendrik Maryns

    ==================
    www.lieverleven.be
    http://aouw.org
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2 (GNU/Linux)

    iD8DBQFD3gRZe+7xMGD3itQRAptGAJ9s2jUN+3Mcbs0bzg8hzGcd+LYSswCfRHOd
    RHJX056IXaeDjH+IKJfr3J8=
    =IAPn
    -----END PGP SIGNATURE-----
    Hendrik Maryns, Jan 30, 2006
    #2
    1. Advertising

  3. On Mon, 30 Jan 2006 20:43:16 +0900 (KST), Red Orchid wrote:
    > The 'HashMap.put' has the code "if (e.hash == hash && eq(k,
    > e.key))". Do you think that the 'e.hash == hash' is required ?


    The extra test is an optimization for a common case, since it is a
    fast operation compared to invoking equals() on each of the keys.

    Each bucket in the hastable can potentially store many different
    objects with different keys and different hash values. There is no
    point in checking the key for equality unless you know the hash value
    is correct.

    > I think that the "if (k == e.key || k.equals(e.key))" is proper.


    k == e.key implies k.equals(e.key), so both tests aren't strictly
    necessary.

    However k.equals(e.key) does not imply k == e.key, so you need to
    check with equals() regardless for those times when a different key
    (with the same value) is used.

    Your test for identity (k = e.key) might give a slight performance
    advantage when identical (not just equal) keys are being reused often,
    but likely less than the hash comparison above.

    /gordon

    --
    [ do not email me copies of your followups ]
    g o r d o n + n e w s @ b a l d e r 1 3 . s e
    Gordon Beaton, Jan 30, 2006
    #3
  4. Red Orchid

    zero Guest

    Gordon Beaton <> wrote in news:43de0ea1$:

    > On Mon, 30 Jan 2006 20:43:16 +0900 (KST), Red Orchid wrote:
    >> The 'HashMap.put' has the code "if (e.hash == hash && eq(k,
    >> e.key))". Do you think that the 'e.hash == hash' is required ?

    >
    > The extra test is an optimization for a common case, since it is a
    > fast operation compared to invoking equals() on each of the keys.
    >


    Remember that that && operator shortcuts - it doesn't evaluate the second
    operand if the first is already false. So, provided the elements have good
    hashing algorithms, this can indeed have quite some influence on
    performance.
    zero, Jan 30, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vince Darley
    Replies:
    4
    Views:
    4,383
    emilchacko
    Mar 2, 2010
  2. Composer

    HashMap.put error in Xcode

    Composer, Apr 22, 2007, in forum: Java
    Replies:
    9
    Views:
    1,149
    Daniel Pitts
    Apr 23, 2007
  3. Rakesh
    Replies:
    10
    Views:
    12,144
    Mike Schilling
    Apr 8, 2008
  4. Gabriel Rossetti
    Replies:
    3
    Views:
    532
    Jerry Hill
    Apr 25, 2008
  5. Wojtek

    HashMap get/put

    Wojtek, Oct 28, 2009, in forum: Java
    Replies:
    49
    Views:
    2,944
    Jim Janney
    Nov 3, 2009
Loading...

Share This Page