HashMap, HasTable
I was reading somewhere that in case of Hashmap and HashTable, the entries are stored in an array. But the index of the entry is calculated through a formula based on the hashKey.
The formula id to divide the HasKey with the no. of entries in the collection and use the remainder value as an index.
Now
1) What if these values are not unique.
2) What if the size increases?
3) I know the load factor for a hashmap and hashtable is 0.75 but is the size doubled or increased by a factor of 1.5
[529 byte] By [
kilyasa] at [2007-10-3 2:12:58]
> 1) What if these values are not unique.
Then they fall nto the same bucket (array) and it becomes progressively less efficient to look stuff up.
> 2) What if the size increases?
Then you have to do all the sums again. Rehashing is an expensive operation.
> 3) I know the load factor for a hashmap and hashtable
> is 0.75 but is the size doubled or increased by a
> factor of 1.5
"When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the capacity is roughly doubled by calling the rehash method."
So it's neither doubled or increased - it just changes brings forward the point at which the capacity will be increased.
