This question have been asked by numerous interviewers to zillions of interviewees.
And we receive an answer as HashSet without basic understanding of why it is supposed to be hashSet?
Let me re-phrase the question.
List?
Well it won't be incorrect answer! I can use list.contains(searchString) and easily search my string.
But what if the String I am searching lies at last position?
In that case also list.contains(searchString). Java has provided API, why should we worry about how it fetches results.
If you think about internal implementation of contains in case of ArrayList, it just loops the list till it finds the correct one! Why? because all ArrayList knows about is index of elements.
HashSet?
So If you are aware of hashing concept of Java (see link if you are not sure of it :) http://www.app-performancetuning.com/2014/06/hashing-it-up-hashcode-and-equals-in.html )
1. Same contains function will first find hash code of the search string.
2. With the help of hash code (plus some extra internal function, in order to normalise all buckets, so that not all the strings go to same bucket and not all go to different buckets.) it will find correct bucket.
3. With the help of equals method it will find whether the string exists.
With these 3 steps and performant hash function applied it can search strings or any custom object at a pretty faster rate.
And we receive an answer as HashSet without basic understanding of why it is supposed to be hashSet?
Let me re-phrase the question.
"Suppose you had millions of strings and you want to perform search operations on those. Which data structure would you prefer in Java?"
List?
Well it won't be incorrect answer! I can use list.contains(searchString) and easily search my string.
But what if the String I am searching lies at last position?
In that case also list.contains(searchString). Java has provided API, why should we worry about how it fetches results.
If you think about internal implementation of contains in case of ArrayList, it just loops the list till it finds the correct one! Why? because all ArrayList knows about is index of elements.
HashSet?
So If you are aware of hashing concept of Java (see link if you are not sure of it :) http://www.app-performancetuning.com/2014/06/hashing-it-up-hashcode-and-equals-in.html )
1. Same contains function will first find hash code of the search string.
2. With the help of hash code (plus some extra internal function, in order to normalise all buckets, so that not all the strings go to same bucket and not all go to different buckets.) it will find correct bucket.
3. With the help of equals method it will find whether the string exists.
With these 3 steps and performant hash function applied it can search strings or any custom object at a pretty faster rate.
No comments:
Post a Comment