aspose file tools*
The moose likes Java in General and the fly likes hashCode & HashMap doubts Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "hashCode & HashMap doubts" Watch "hashCode & HashMap doubts" New topic
Author

hashCode & HashMap doubts

naved momin
Ranch Hand

Joined: Jul 03, 2011
Posts: 692



  • one thing is noticable here is whenever we add or demand something from hashmap it internally (implicity)calls to hashCode() why ?
  • 2nd thing is that when it calls to that hashCode() it gets a hash value which is 7 , my question is what does the hashmap do with that value ?


  • The Only way to learn is ...........do!
    Visit my blog http://inaved-momin.blogspot.com/
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    naved momin wrote:
  • one thing is noticable here is whenever we add or demand something from hashmap it internally (implicity)calls to hashCode() why ?

  • 2nd thing is that when it calls to that hashCode() it gets a hash value which is 7 , my question is what does the hashmap do with that value ?


  • That's the whole point of hashCode() and HashMap. The hashCode() is fast to calculate, and if you have a good hashing function, then the probability that two objects have the same hashcode is small. HashMap uses hashCode() first to narrow down the list of potentially equal objects that it has to do a linear search on.

    In your case, you have a bad hashing function, so a HashMap lookup of your object will be O(N) just like an unsorted List lookup--it's a linear search of all entries. With a good hash function, it would be O(1).

    http://en.wikipedia.org/wiki/Hash_table
    http://java.sun.com/developer/Books/effectivejava/Chapter3.pdf
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39435
        
      28
    A worthwhile quote . Use ctrl-F “working” on that pdf and see what comes up. The bit I am thinking of is on page 38.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Campbell Ritchie wrote:
    A worthwhile quote . Use ctrl-F “working” on that pdf and see what comes up. The bit I am thinking of is on page 38.


    Yup. Waiting two days for something I need in the next few seconds does not count as "working" in my book.
    naved momin
    Ranch Hand

    Joined: Jul 03, 2011
    Posts: 692

    HashMap uses hashCode() first to narrow down the list of potentially equal objects that it has to do a linear search on.

    so you mean in my case whenever i add something to hashmap it has hashcode = 7 , regardless whether two objects are same or different
    so while checking two objects are equal through hashCode i will have o(n) time complexity , but if i have unique hashCode for each entry in hashmap the search will narrow down
    to o(1) , is it so ?
    Anayonkar Shivalkar
    Bartender

    Joined: Dec 08, 2010
    Posts: 1509
        
        5

    naved momin wrote:but if i have unique hashCode for each entry in hashmap the search will narrow down to o(1) , is it so ?

    Yes. Exactly.

    If you go through Java specification, you'll find something called as HashCode contract.

    The contract says :
    1) If you call HashCode method over an object again and again, the result must be same. i.e. HashCode method must be independent of time and number of times it is called.
    2) If two objects are equal as per equals method, then their HashCode must be same.
    3) If two objects are not equal as per equals method, then their HashCode may be same or different (in your case, the HashCode is same, no matter what. So, it is valid, though not optimized, design).

    Hope this helps.


    Regards,
    Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    naved momin wrote:
    HashMap uses hashCode() first to narrow down the list of potentially equal objects that it has to do a linear search on.

    so you mean in my case whenever i add something to hashmap it has hashcode = 7 , regardless whether two objects are same or different
    so while checking two objects are equal through hashCode i will have o(n) time complexity , but if i have unique hashCode for each entry in hashmap the search will narrow down
    to o(1) , is it so ?


    naved momin wrote:
    HashMap uses hashCode() first to narrow down the list of potentially equal objects that it has to do a linear search on.

    so you mean in my case whenever i add something to hashmap it has hashcode = 7 , regardless whether two objects are same or different
    so while checking two objects are equal through hashCode i will have o(n) time complexity , but if i have unique hashCode for each entry in hashmap the search will narrow down
    to o(1) , is it so ?


    You're close.

    We don't check whether two objects are equal with hashCode. We only check if they're in the same bucket (or rather, the hash-based data structure does). Equality is still tested with equals(), and finding the element within the bucket is O(N), where N is the size of that bucket, but with a good hashing function, that will be very small, ideally 1.

    So yes, a perfectly unique hashing function (which is impossible to achieve in general) will give perfect O(1) performance, and a perfectly non-unique hashing function (a constant) will give O(N) performance. A good hashing function (such as the one in Josh Bloch's book that I linked to) will provide close to O(1) performance.
    naved momin
    Ranch Hand

    Joined: Jul 03, 2011
    Posts: 692

    Jeff Verdegan wrote:
    naved momin wrote:
    HashMap uses hashCode() first to narrow down the list of potentially equal objects that it has to do a linear search on.

    so you mean in my case whenever i add something to hashmap it has hashcode = 7 , regardless whether two objects are same or different
    so while checking two objects are equal through hashCode i will have o(n) time complexity , but if i have unique hashCode for each entry in hashmap the search will narrow down
    to o(1) , is it so ?


    naved momin wrote:
    HashMap uses hashCode() first to narrow down the list of potentially equal objects that it has to do a linear search on.

    so you mean in my case whenever i add something to hashmap it has hashcode = 7 , regardless whether two objects are same or different
    so while checking two objects are equal through hashCode i will have o(n) time complexity , but if i have unique hashCode for each entry in hashmap the search will narrow down
    to o(1) , is it so ?


    You're close.

    We don't check whether two objects are equal with hashCode. We only check if they're in the same bucket (or rather, the hash-based data structure does). Equality is still tested with equals(), and finding the element within the bucket is O(N), where N is the size of that bucket, but with a good hashing function, that will be very small, ideally 1.


    So yes, a perfectly unique hashing function (which is impossible to achieve in general) will give perfect O(1) performance, and a perfectly non-unique hashing function (a constant) will give O(N) performance. A good hashing function (such as the one in Josh Bloch's book that I linked to) will provide close to O(1) performance.


    thanks jef josh bouch is a great software enggineer .....from where this guyz know so much .....
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    naved momin wrote:
    thanks jef josh bouch is a great software enggineer .....from where this guyz know so much .....


    I don't know. You'd have to ask him. I imagine a lot of it comes from experience. For instance, I think he's one of the main authors of the Collections framework that's been part of Java since 1998.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 39435
        
      28
    naved momin wrote: . . . thanks jef josh bouch is a great software enggineer .....from where this guyz know so much .....
    You would do well to use a spell-check on your web browser; there are 5 words misspelt in that line, which would confuse anybody using automatic translation software. Some browsers (eg FireFox) have an option to mark misspellings in posts.
    Anayonkar Shivalkar
    Bartender

    Joined: Dec 08, 2010
    Posts: 1509
        
        5

    Jeff Verdegan wrote:You're close.


    Oops I missed that part

    Jeff is absolutely correct. HashCode decides that in which 'bucket' the object would go. In worst case, all objects will be in same bucket (e.g. HashCode method returns a hard-coded value) and in best case, all objects will be in different bucket. Practically, we can take measure to be sure that code complexity is approaching to O(1).
    Cheo Gomez
    Greenhorn

    Joined: Jan 24, 2012
    Posts: 25
    When I invoke the "get" method of the hashmap, the hashcode is called first, then is called the equal method of the key class, why the hashcode method is called first? who calls the equal method? the reference you are passing to the equal method is the key we use with the get method?
    thank you all
    Anayonkar Shivalkar
    Bartender

    Joined: Dec 08, 2010
    Posts: 1509
        
        5

    Hi Cheo,

    Welcome to coderanch!

    Cheo Gomez wrote: why the hashCode method is called first?

    Well, hashCode decides in which 'bucket' to look for.
    e.g. consider below scenario:
    you have different objects - triangular, rectangular, spherical etc. Further, those objects are also coloured with red, yellow, green etc.
    Consider that your hashCode returns shape and equality is based on colour.
    Now, when you say - get red sphere, you'll first decide in which bucket to look. Hence, you'll consult hashCode first - which will tell you the bucket containing all kinds of spheres.
    Further, with equals method, you'll match colour - red with all available spheres and get the required sphere. Please note that this is just a general example of hashCode and equals (and not for HashMap)

    Cheo Gomez wrote: who calls the equal method?

    The equals (not equal) method is internally called during invocation of 'get' method. We don't have to explicitly call it (but of course, we'll have to define it).

    I hope this helps.
    Cheo Gomez
    Greenhorn

    Joined: Jan 24, 2012
    Posts: 25
    It really helps a lot my friend, didnt see this explanation in another place, thanks very much
    About the hashmap, it can contain more than one kind of objects, I mean, having a Hashmap with cars, students and dogs, ?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Cheo Gomez wrote:
    About the hashmap, it can contain more than one kind of objects, I mean, having a Hashmap with cars, students and dogs, ?


    It can do that, but putting unrelated types in the same Map or Collection is generally a bad idea. It's okay to put in different classes if the implement a common interface or extend a common base class. For instance, you might have a Map<Student, ClassSchedule>, where Student is an interface and Undergrad and GradStudent are implementing classes. Or a Map<Food, NutritionalData> where Food is an interface implemented by BigMac, Apple, Broccoli, ChocolateChipCookie, and Beer.

    As long as you can treat all the elements as the base type--Student or Food--and not worry about knowing which class it is (because polymorphism will take care of that for you), it's fine. Putting Donuts, Airplanes, and Politicians in the same Map or Collection, however, though legal in syntax and in the library, makes no sense.
    Cheo Gomez
    Greenhorn

    Joined: Jan 24, 2012
    Posts: 25
    Thank you very much, very good explanation, see you
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
     
    subject: hashCode & HashMap doubts