Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

hashCode & HashMap doubts

 
naved momin
Ranch Hand
Posts: 692
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


  • 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 ?
  •  
    Jeff Verdegan
    Bartender
    Posts: 6109
    6
    Android IntelliJ IDE Java
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Pie
    Posts: 48953
    60
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 6109
    6
    Android IntelliJ IDE Java
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 692
    Eclipse IDE Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 1557
    5
    Eclipse IDE Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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.
     
    Jeff Verdegan
    Bartender
    Posts: 6109
    6
    Android IntelliJ IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 692
    Eclipse IDE Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 6109
    6
    Android IntelliJ IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Pie
    Posts: 48953
    60
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 1557
    5
    Eclipse IDE Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 25
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 1557
    5
    Eclipse IDE Java Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 25
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 6109
    6
    Android IntelliJ IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Posts: 25
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Thank you very much, very good explanation, see you
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic