File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes What does this mean? HashSet performance Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "What does this mean? HashSet performance" Watch "What does this mean? HashSet performance" New topic
Author

What does this mean? HashSet performance

Chandra Bhatt
Ranch Hand

Joined: Feb 28, 2007
Posts: 1707
The time to find the value from HashMap with a key depends
on the size of the map.


Please elaborate this!!!

Is getting an object back from the HashSet is time constant?


Regards,
cmbhatt


cmbhatt
Keith Lynn
Ranch Hand

Joined: Feb 07, 2005
Posts: 2367
Where did you find that quote?

This is from the API for HashMap.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
Srinivasan thoyyeti
Ranch Hand

Joined: Feb 15, 2007
Posts: 557
Hi Bhatt,

I don't know How HashMpa actually got implented;
But ican share the Data Structures concept i know...

Hashing can be done in two ways:
1. Closed hashing
2. Open Hashing

1. Closed Hashing:
In this Linked list concept used to group all the entries in the same bucket. like...

0 ---> Entr1 ---> Entry 3 ---> null

1 ---> Entry2 ---> null
.
.
9---> Entry 5 -->Entry9--->Entry15 ---> null

The Size of Map is 10(buckets).
Here in this case i didn't find any size constrint that will effect the retrieval time.

2. Open Hashing:
I did't remember about this.

What i understood is:
Bucket's can be array. for given the key
array[hashCode(key)] has no effect on size of Map.

But Actual implementation matter raher our assumptions.
In the mean while i will try to understand How HashMap got implemented ?


Thanks & Regards, T.Srinivasan
SCWCD 1.4(89%), SCJP 5.0(75%)
Chandra Bhatt
Ranch Hand

Joined: Feb 28, 2007
Posts: 1707
Thanks Keith & Srini!

Srini,

What you say about Closed Hashing, the traversal is done from picking the first element and going through until we find the exact match in that bucket.Right? Wont the depth of the element affect the performance???


And yeah, you people left my second question unanswered!!!

Regards,
cmbhatt
[ April 16, 2007: Message edited by: Chandra Bhatt ]
Srinivasan thoyyeti
Ranch Hand

Joined: Feb 15, 2007
Posts: 557
Hi Chandra,
But depth of one bucket has nothing to do with size of buckets.

As keith already pointed it out;

1)If your question is size of HashMap or HashSet has anything to do to retrieve a perticular entry.

Answer : No.(correct me if i am wrong)

2)if your question is beween HashSet get method and HashMap get method which one takes less time ?

Answer: HashSet's get( bec'ze only one Entry for Bucket)

HashMap has to traverse through a perticular bucket to find requested entry by using equals().

Any thing more ...?
[ April 16, 2007: Message edited by: Srinivasan thoyyeti ]
Chandra Bhatt
Ranch Hand

Joined: Feb 28, 2007
Posts: 1707
Srini,
What is this size? If the Map has 3 elements, the size is 3.
Question is, whether performance is dependent on size. (I get this size is size of the Map; number of elements in it, Isn't it?)


Yeah! I got it a bit; Nothing to consider with the size of the Map; We have to find the bucket and here size does not count! Isn't it?



Thanks,
cmbhatt
Srinivasan thoyyeti
Ranch Hand

Joined: Feb 15, 2007
Posts: 557
Hi Chandra,

You are right:
int size()
Returns the number of key-value mappings in this map.

Then size really matters depending up on the hashCode.
If you uses poor hashing like hashCode() { return 9; }

I am looking into HashMap implementation.
It will take time i suppose.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: What does this mean? HashSet performance