title: Time complexity for Java HashMap resizing
body: <p>I am wondering what would be the time complexity on <code>Java</code> <code>HashMap</code> resizing when the load factor exceeds the threshold ? As far as I understand for HashMap the table size is always power of 2 an even number, so whenever we resize the table we don't necessary need to rehash all the keys (correct me if i am wrong), all we need to do is to allocate additional spaces without and copy over all the entries from the old table (I am not quite sure how does JVM deal with that internally), correct ? Whereas for <code>Hashtable</code> since it uses a prime number as the table size, so we need to rehash all the entries whenever we re-size the table. So my question is does it still take O(n) linear time for resizing on <code>HashMap</code> ?</p>