Comparing the HashMap
and Hashtable
source code in JDK 1.6, I saw the below code inside HashMap:
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 16; int capacity = 1; while (capacity < initialCapacity) capacity <<= 1;
However, in Hashtable, I saw this:
table = new Entry[initialCapacity]; public Hashtable() { this(11, 0.75f); }
So my question is: Why does HashMap require a power of 2 as the initial capacity, while Hashtable chooses 11 as the default initial capacity? I assume this has nothing to do with the thing that Hashtable is thread-safe and does not allow null key or values.
The default load factor of HashMap is 0.75f (75% of the map size). The problem is, keeping the bucket size fixed (i.e., 16), we keep on increasing the total number of items in the map that disturbs time complexity. When we increase the total number of buckets, total items in each bucket starts increasing.
So, basically the point is, if the size is a power of two, the keys will be more evenly distributed across the array with minimal collision leading to better retrieval performance (and also less synchronizations in case of ConcurrentHashMap ) when compared with any other size which is not a power of 2.
Constructor Summary Constructs a new, empty hashtable with a default initial capacity (11) and load factor (0.75).
Hashmap vs Hashtable HashMap allows one null key and multiple null values whereas Hashtable doesn't allow any null key or value. HashMap is generally preferred over HashTable if thread synchronization is not needed.
The following article addresses this question in some detail: HashMap requires a better hashCode() - JDK 1.4 Part II.
According to that article, the main reason to move to power-of-two sizes was that bit masking is faster than integer division. This is not without adverse consequences, which are explained by one of the original authors:
Joshua Bloch: The downside of using a power-of-two is that the resulting hash table is very sensitive to the quality of the hash function (hashCode). It is imperative that any change in the input must affect the low order bits of the hash value. (Ideally, it should affect all bits of the hash value with equal likelihood.) Because we have no assurance that this is true, we put in a secondary (or "defensive") hash function when we switched to the power-of-two hash table. This hash function is applied to the results of hashCode before masking off the low order bits. Its job is to scatter the information over all the bits, and in particular, into the low order bits. Of course it has to run very fast, or you lose the benefit of switching to the power-of-two-sized table. The original secondary hash function in 1.4 turned out to be insufficient. We knew that this was a theoretical possibility, but we thought that it didn't affect any practical data sets. We were wrong. The replacement secondary hash function (which I developed with the aid of a computer) has strong statistical properties that pretty much guarantee good bucket distribution.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With