hashCode for 4 ints?

Discussion in 'Java' started by Jeff, Jun 21, 2005.

  1. Jeff

    Jeff Guest

    Am I misusing HashMap or just need to fix the .hashCode() override for the
    key object?

    The class I use as a key for a HashMap is unique based on a combination of 4
    ints. Normally, about 5000 instances are created and persist over time.
    The maximum possible created is probably max around 40,000.

    Since .hashCode() returns an int, how do I create a unique identifier for
    the 128 bits contained in the 4 ints? Or should I swap to another data
    structure?

    Thanks!

    // Here's a simplification of my class that illustrates my problem.

    public class IntHashExample {
    int A, B, C, D;

    IntHashExample( int A , int B , int C , int D ) {
    this.A = A;
    this.B = B;
    this.C = C;
    this.D = D;
    }

    public boolean equals( Object arg0 ) {

    IntHashExample other = ( IntHashExample ) arg0;

    if ( ( A == other.A ) && ( B == other.B ) && ( C == other.C ) && ( D
    == other.D ) )
    return true;
    else
    return false;
    }

    // how do I create a hashcode to lookup the unique combination of the 4
    ints? The following obviously wouldn't work,
    // but hopefully indicates my need
    public int hashCode() {

    long highest = ( long ) A << 96;

    long high = ( long ) B << 64;

    long low = ( long ) C << 32;

    long lowest = ( long ) D;

    int code = ( int ) ( highest | high | low | lowest );

    return code;
    }
    }

    --
    Jeff
    Jeff, Jun 21, 2005
    #1
    1. Advertising

  2. Jeff

    YoungHwan Guest

    what about this??

    public int hashCode() {
    int result = 17;
    result = 37 * result + highest;
    result = 37 * result + high;
    result = 37 * result + low;
    result = 37 * result + lowest;
    return result;
    }

    >From ' Effective Java: Programming Language Guide



    Jeff 작성:
    > Am I misusing HashMap or just need to fix the .hashCode() override for the
    > key object?
    >
    > The class I use as a key for a HashMap is unique based on a combination of 4
    > ints. Normally, about 5000 instances are created and persist over time.
    > The maximum possible created is probably max around 40,000.
    >
    > Since .hashCode() returns an int, how do I create a unique identifier for
    > the 128 bits contained in the 4 ints? Or should I swap to another data
    > structure?
    >
    > Thanks!
    >
    > // Here's a simplification of my class that illustrates my problem.
    >
    > public class IntHashExample {
    > int A, B, C, D;
    >
    > IntHashExample( int A , int B , int C , int D ) {
    > this.A = A;
    > this.B = B;
    > this.C = C;
    > this.D = D;
    > }
    >
    > public boolean equals( Object arg0 ) {
    >
    > IntHashExample other = ( IntHashExample ) arg0;
    >
    > if ( ( A == other.A ) && ( B == other.B ) && ( C == other.C ) && ( D
    > == other.D ) )
    > return true;
    > else
    > return false;
    > }
    >
    > // how do I create a hashcode to lookup the unique combination of the4
    > ints? The following obviously wouldn't work,
    > // but hopefully indicates my need
    > public int hashCode() {
    >
    > long highest = ( long ) A << 96;
    >
    > long high = ( long ) B << 64;
    >
    > long low = ( long ) C << 32;
    >
    > long lowest = ( long ) D;
    >
    > int code = ( int ) ( highest | high | low | lowest );
    >
    > return code;
    > }
    > }
    >
    > --
    > Jeff
    YoungHwan, Jun 21, 2005
    #2
    1. Advertising

  3. "Jeff" <> writes:

    > The class I use as a key for a HashMap is unique based on a combination of 4
    > ints.


    Ok, that gives you (2^32)^4 different possible values (or 2^96 times
    more than the possible values of hashCode()).

    > Normally, about 5000 instances are created and persist over time.
    > The maximum possible created is probably max around 40,000.


    Is there any system to these, or are they distributed randomly in
    int^4-space?

    > Since .hashCode() returns an int, how do I create a unique identifier for
    > the 128 bits contained in the 4 ints?


    Obviously, you can't map 2^128 bits of information uniquely into 2^32
    bits, unless you know something about the four integers that you
    haven't told us yet.

    > Or should I swap to another data structure?


    No need. Hash values doesn't need to be unique. For performance
    reasons, it's best that they don't collide too often, but for 40000
    instances, that's unlikely to happen.

    > public boolean equals( Object arg0 ) {
    >
    > IntHashExample other = ( IntHashExample ) arg0;
    >
    > if ( ( A == other.A ) && ( B == other.B ) && ( C == other.C ) && ( D
    > == other.D ) )
    > return true;
    > else
    > return false;


    Just do:
    return (A==other.A) && ... && (D == other.D);

    >
    > // how do I create a hashcode to lookup the unique combination of the 4
    > ints? The following obviously wouldn't work,


    No simple method will guarantee uniqueness.

    Maybe it is possible to make a simple method that works for a typical
    choice of the 40000 instances, but as long as it's fairly good, a few
    collisions won't matter much.

    > // but hopefully indicates my need
    > public int hashCode() {


    How about just:
    return ((((((A * 31) + B) * 31) + C) * 31) + D);

    /L
    --
    Lasse Reichstein Nielsen -
    DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
    'Faith without judgement merely degrades the spirit divine.'
    Lasse Reichstein Nielsen, Jun 21, 2005
    #3
  4. Jeff

    Eric Sosman Guest

    Jeff wrote:
    > Am I misusing HashMap or just need to fix the .hashCode() override for the
    > key object?


    Others have given advice about how to hash, but I haven't
    seen anyone point out a different problem in your code:

    > public boolean equals( Object arg0 ) {
    >
    > IntHashExample other = ( IntHashExample ) arg0;


    This violates the equals() contract. If `arg0' is
    a String or a JPanel or anything except an IntHashExample,
    this method will throw a ClassCastException -- but equals()
    is not supposed to do that; it should just return false.
    Also, if `arg0' is null `other' will also be null, and
    you'll throw a NullPointerException as soon as you try to
    access the non-existent object it doesn't reference.

    Suggested fix:

    public boolean equals(Object arg0) {
    if (! (arg0 instanceof IntHashExample) )
    return false;
    // the remainder as before ...

    --
    Eric Sosman, Jun 21, 2005
    #4
  5. Jeff

    Wibble Guest

    Eric Sosman wrote:
    >
    > Jeff wrote:
    >
    >>Am I misusing HashMap or just need to fix the .hashCode() override for the
    >>key object?

    >
    >
    > Others have given advice about how to hash, but I haven't
    > seen anyone point out a different problem in your code:
    >
    >
    >> public boolean equals( Object arg0 ) {
    >>
    >> IntHashExample other = ( IntHashExample ) arg0;

    >
    >
    > This violates the equals() contract. If `arg0' is
    > a String or a JPanel or anything except an IntHashExample,
    > this method will throw a ClassCastException -- but equals()
    > is not supposed to do that; it should just return false.
    > Also, if `arg0' is null `other' will also be null, and
    > you'll throw a NullPointerException as soon as you try to
    > access the non-existent object it doesn't reference.
    >
    > Suggested fix:
    >
    > public boolean equals(Object arg0) {
    > if (! (arg0 instanceof IntHashExample) )
    > return false;
    > // the remainder as before ...
    >

    Nopers, instanceof isnt strong enough since arg0 may subclass
    IntHashExample and override hashCode or equals. use

    if (arg0==null || arg0.getClass()==this.getClass()) return(false);
    Wibble, Jun 22, 2005
    #5
  6. Wibble wrote:
    > Eric Sosman wrote:
    >> Jeff wrote:


    [...]

    >>> public boolean equals( Object arg0 ) {
    >>>
    >>> IntHashExample other = ( IntHashExample ) arg0;


    >>
    >> This violates the equals() contract.


    [...]

    >> Suggested fix:
    >>
    >> public boolean equals(Object arg0) {
    >> if (! (arg0 instanceof IntHashExample) )
    >> return false;
    >> // the remainder as before ...
    >>

    > Nopers, instanceof isnt strong enough since arg0 may subclass
    > IntHashExample and override hashCode or equals. use
    >
    > if (arg0==null || arg0.getClass()==this.getClass()) return(false);


    It depends on your point of view, I suppose. instanceof works fine for
    the equals() method described, but it does provide an extra avenue by
    which a subclass can be broken (overriding equals() or hashCode()). The
    class presented is only broken if such a subclass exists. Such breakage
    could also be prevented by making the class final (which renders your
    solution equivalent to Eric's) or by making just equals() and hashCode()
    final.

    --
    John Bollinger
    John C. Bollinger, Jun 22, 2005
    #6
    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. Roedy Green

    hashCode for byte[]

    Roedy Green, Aug 22, 2003, in forum: Java
    Replies:
    1
    Views:
    413
    Dale King
    Aug 22, 2003
  2. Marco
    Replies:
    10
    Views:
    755
  3. Jeff

    hashCode for 4 ints?

    Jeff, Jun 21, 2005, in forum: Java
    Replies:
    12
    Views:
    1,003
    Thomas Weidenfeller
    Jun 28, 2005
  4. Replies:
    3
    Views:
    554
    Mark P
    Apr 3, 2005
  5. Skybuck Flying

    ints ints ints and ints

    Skybuck Flying, Jul 8, 2004, in forum: C Programming
    Replies:
    24
    Views:
    816
    Jack Klein
    Jul 10, 2004
Loading...

Share This Page