Page 1 of 2 12 LastLast
Results 1 to 20 of 33
Like Tree3Likes

Thread: How is hashcode calculated?

  1. #1
    Join Date
    Aug 2013
    Posts
    108
    Rep Power
    0

    Default How is hashcode calculated?

    I know we can put a string and use the hashcode function to get the hashcode of a string. But what if somebody asks in interview how is the hashcode internally calculated?

    Sample Program:
    Java Code:
    public class HashCode {
       public static void main(String[] args) {
          System.out.println("HASHCODE="+"String1".hashCode());
          System.out.println("HASHCODE="+"String2".hashCode());
          System.out.println("HASHCODE="+"String3".hashCode());
          System.out.println("HASHCODE="+"String4".hashCode());
       }
       
    }
    Output
    HASHCODE=-217105888
    HASHCODE=-217105887
    HASHCODE=-217105886
    HASHCODE=-217105885

  2. #2
    masijade is offline Senior Member
    Join Date
    Jun 2008
    Posts
    2,571
    Rep Power
    9

    Default Re: How is hashcode calculated?

    If you have a jdk (not just a jre) the jdk directory will contain a src.zip file. Open that and take a look at the src code for String.
    DarrylBurke likes this.

  3. #3
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    4,365
    Rep Power
    6

    Default Re: How is hashcode calculated?

    Looks like it is native code, so its probably not in the src.zip. You'd have to hunt it down in the openjdk source somewhere.

    GrepCode: java.lang.Object (.java) - Class - Source Code View
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default Re: How is hashcode calculated?

    Quote Originally Posted by gimbal2 View Post
    Looks like it is native code, so its probably not in the src.zip. You'd have to hunt it down in the openjdk source somewhere.

    GrepCode: java.lang.Object (.java) - Class - Source Code View
    It isn't in Java 1.6; here it is:

    Java Code:
        public int hashCode() {
    	int h = hash;
            int len = count;
    	if (h == 0 && len > 0) {
    	    int off = offset;
    	    char val[] = value;
    
                for (int i = 0; i < len; i++) {
                    h = 31*h + val[off++];
                }
                hash = h;
            }
            return h;
        }
    b.t.w. 'hash' is a private member variable that caches the calculated hash code (it can do that because Strings are immutable).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    4,033
    Rep Power
    6

    Default Re: How is hashcode calculated?

    Well, I just checked my src.zip for 1.7.0_21 and the hashCode method for String is not native. It is slightly different in implementation than the one that Jos mentioned.
    Java Code:
    /**
         * Returns a hash code for this string. The hash code for a
         * <code>String</code> object is computed as
         * <blockquote><pre>
         * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
         * </pre></blockquote>
         * using <code>int</code> arithmetic, where <code>s[i]</code> is the
         * <i>i</i>th character of the string, <code>n</code> is the length of
         * the string, and <code>^</code> indicates exponentiation.
         * (The hash value of the empty string is zero.)
         *
         * @return  a hash code value for this object.
         */
        public int hashCode() {
            int h = hash;
            if (h == 0 && value.length > 0) {
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) {
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }
    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  6. #6
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    4,365
    Rep Power
    6

    Default Re: How is hashcode calculated?

    Note to self: OpenJDK is not the same as the Oracle JDK.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  7. #7
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,224
    Rep Power
    20

    Default Re: How is hashcode calculated?

    Well, they're pretty similar, but you linked to hashCode for Object...not String.
    :)
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default Re: How is hashcode calculated?

    Quote Originally Posted by jim829 View Post
    It is slightly different in implementation than the one that Jos mentioned.
    What and where is the difference? I can't find it but my old eyes have always been bad ;-)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,224
    Rep Power
    20

    Default Re: How is hashcode calculated?

    Java Code:
    int len = count;
    The 1.7 version seem to be taking that count value directly from the length of the string instead?
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default Re: How is hashcode calculated?

    Quote Originally Posted by Tolls View Post
    Java Code:
    int len = count;
    The 1.7 version seem to be taking that count value directly from the length of the string instead?
    Of course I saw that ;-) it seems that version 1.7 doesn't use shared char buffers anymore ... I'll have to have a look at it.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    4,365
    Rep Power
    6

    Default Re: How is hashcode calculated?

    Quote Originally Posted by Tolls View Post
    Well, they're pretty similar, but you linked to hashCode for Object...not String.
    :)
    Note to self: ... never mind, I just suck.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  12. #12
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    4,033
    Rep Power
    6

    Default Re: How is hashcode calculated?

    The 1.6 version also seems to start the hash from some offset which is not used in the 1.7 version.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  13. #13
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default Re: How is hashcode calculated?

    I haven't looked through the source for either version, but I would hazard a guess that the offset relates to a String returned by substring(...).

    That would explain Jos's comment about shared character buffers, at #10. Does the code for substring(...) also differ across the two versions?

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  14. #14
    Join Date
    Aug 2013
    Posts
    108
    Rep Power
    0

    Default Re: How is hashcode calculated?

    Ok I am having JDK 1.6. So will consider the same.
    I am not able to call the user defined hashcode. I have given the @Override annotation and also given a SOP, but it still refers to the built-in hashcode.

    My sample code
    Java Code:
    public class HashCode {
       public static void main(String[] args) {
          System.out.println("HASHCODE="+(("A").hashCode()));
       }
       @Override
       public int hashCode() {
    	   System.out.println("Inside user defined hashcode");
    	   int h = 0;
    	       int len = 1;
    	   if (h == 0 && len > 0) {
    	       int off = 0;
    	       char val[] = {'A'};
    	    
    	           for (int i = 0; i < len; i++) {
    	               h = 31*h + val[off++];
    	           }
    	       }
    	       return h;
    	   }
    }

  15. #15
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default Re: How is hashcode calculated?

    Huh? What does overriding the hashCode() of your HashCode class (inherited from Object) have to do with obtaining the hashCode() of a String literal?

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  16. #16
    Join Date
    Aug 2013
    Posts
    108
    Rep Power
    0

    Default Re: How is hashcode calculated?

    Why? What's wrong? Care to explain

  17. #17
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,457
    Rep Power
    20

    Default Re: How is hashcode calculated?

    Quote Originally Posted by suhaas.mohandos@gmail.com View Post
    Why? What's wrong? Care to explain
    No, I don't care to explain. In this and your other threads, it is clear that you haven't understood the fundamentals of Java, and a forum is no substitute for systematic learning.

    I recommend you go through The Java™ Tutorials lesson by lesson and trail by trail.

    db
    gimbal2 and masijade like this.
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  18. #18
    Join Date
    Aug 2013
    Posts
    108
    Rep Power
    0

    Default Re: How is hashcode calculated?

    No, I don't care to explain.
    If you dont care, dont bother, bro. There are others who will explain.
    Last edited by suhaas.mohandos@gmail.com; 08-09-2013 at 08:58 AM.

  19. #19
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default Re: How is hashcode calculated?

    Quote Originally Posted by DarrylBurke View Post
    I haven't looked through the source for either version, but I would hazard a guess that the offset relates to a String returned by substring(...).

    That would explain Jos's comment about shared character buffers, at #10. Does the code for substring(...) also differ across the two versions?
    Yep, that's it (I checked it); until version 1.6. sub strings shared the character buffer with their 'parent' String; memory-wise it was (a bit) cheaper but had a great drawback; e.g.

    Java Code:
    Stirng huge= ...; // a huge string
    String tiny= huge.substring(0, 1);
    huge= null;
    The character buffer for the huge String could still not be garbage collected. In the old days (when computers were made of wood) even StringBuffers used to share those character buffers. The code for the String class is greatly simplified by removing those smart tricks ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  20. #20
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    4,365
    Rep Power
    6

    Default Re: How is hashcode calculated?

    Quote Originally Posted by suhaas.mohandos@gmail.com View Post
    No, I don't care to explain.
    If you dont care, dont bother, bro. There are others who will explain.
    I think you'll find that number will go down and down as long as you don't listen to DB's excellent advice.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

Page 1 of 2 12 LastLast

Similar Threads

  1. User inputs string to get calculated output
    By freky8ss in forum New To Java
    Replies: 2
    Last Post: 05-02-2013, 07:09 AM
  2. Replies: 13
    Last Post: 02-01-2011, 02:34 AM
  3. Replies: 1
    Last Post: 12-20-2010, 10:43 PM
  4. Replies: 0
    Last Post: 12-19-2010, 02:50 PM
  5. Replies: 5
    Last Post: 10-09-2010, 06:22 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •