[Logo]
Forums Register Login
What does this mean? HashSet performance
 
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
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.
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 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 ]
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 ]
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
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.
Wink, wink, nudge, nudge, say no more ... https://richsoil.com/cards



All times above are in ranch (not your local) time.
The current ranch time is
Nov 22, 2017 22:52:40.