• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Liutauras Vilda
  • Henry Wong
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Mikalai Zaikin
  • Himai Minh

Hashing and Use in java

 
Ranch Hand
Posts: 50
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi All
I know this question would have been asked several times.
However asking again wth respect to internal working.

Contract says to have hashcode override with equals. Now questions are :
1. Why need hashing.
2. If not implemented hashing , what is pitfall. What will be size of hashmap.
3. If implemented hashcode and not equals and vice versa.
4. What is underlying implementation storing hashcode and how does it work in retrieving the object
5. How does hashing works best with immutable object
6. What is same type of objects and put. What will be size of map then.
7. What exactly is bucket. We talk of bucket but what is actual implementation of same and how does it handle the same.
8. Any other consideration.
9 Do we provide implementation of bucket or provided by java.

Please let me know or if any detailed article covering same will help.

Thanks
Avinash
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Avinash Tiwari wrote:1. Why need hashing.


Because some collection classes, such as HashMap and HashSet, need this.

Avinash Tiwari wrote:2. If not implemented hashing , what is pitfall. What will be size of hashmap.


I don't understand exactly what you mean here. HashMap needs a hashing mechanism, without it, you just couldn't have a HashMap. The size of the HashMap specifically doesn't have anything to do with it.

Avinash Tiwari wrote:3. If implemented hashcode and not equals and vice versa.


If the hashCode() and equals() method do not work together the way they should, then you can get unpredictable results when you put objects in a HashSet or use them as keys in a HashMap. For example, you put the object in a HashSet, then check if it is in the set, and you could get false, even though you just put it in.

Avinash Tiwari wrote:4. What is underlying implementation storing hashcode and how does it work in retrieving the object


You can lookup the source code of HashMap in the JDK source code, which you can find on your own computer, in the file src.zip in your JDK installation directory.

Avinash Tiwari wrote:5. How does hashing works best with immutable object


You will get into trouble when you put objects in for example a HashSet and then change the member variables in a way so that the hash code of the object would change. HashSet stores the object in a bucket that corresponds to its hash code. If you change the content of the object, then its hash code will be different, and it would be in the wrong bucket in the HashSet. This can't happen with immutable objects, because you can't change the content of an immutable object.

Avinash Tiwari wrote:6. What is same type of objects and put. What will be size of map then.


I don't understand what you mean with this. The size of the map (number of objects in the map) doesn't have anything to do with the type of objects.

Avinash Tiwari wrote:7. What exactly is bucket. We talk of bucket but what is actual implementation of same and how does it handle the same.


This has to do with how HashMap works internally. It stores elements (key-value pairs) in a collection of "buckets". In which bucket a key-value pair goes, is determined by the hash code of the key. The reason for this is that it makes it very efficient to lookup elements by key later: you supply the key, the HashMap gets the hash code, and then it knows in which bucket to look for the key-value pair. Imagine that you have a HashMap with 1000 elements, distributed evenly over 100 buckets (each bucket contains 10 elements). To lookup an element, the HashMap only needs to look in one bucket, so it has to compare the key that you provide with just 10 elements. Compare this to how it would work in a list, where the 1000 elements: there, it would need to compare it to all 1000 objects.

Avinash Tiwari wrote:9 Do we provide implementation of bucket or provided by java.


It's part of how HashMap is implemented internally. You don't provide this yourself, and you don't even have to know about this when you're just using HashMap.
 
Rancher
Posts: 1090
14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
To add to what Jesper said, you may like to read about hashing. Fortunately it is a technique which is widely in use, hence to google about it is sort of an easy thing.

8. Any other consideration.



There are quite a few and it'll be pointless to mention them unless you've read about hashing. But here are a couple of things.
You might wanna see if you're searching for an item in the hashed collection quite as frequently as you do a full iteration.
You might wanna see if you may require an explicit sort order too.
Rehashing along with its associated things ( the number of buckets, the load factor, the hashCode logic and the distribution of elements into the buckets, the kind of operations most expected, how frequently the collection may rehash etc ) is a consideration too.

Hope it helps.
Chan.
 
reply
    Bookmark Topic Watch Topic
  • New Topic