Java HashMap Interview QuestionsEDIT
1) How does put() work?
You call put() with a key/value pair. The key is hashed using its hashCode() and used to find the index of the provided key in the underlying array.
If the index of this array is empty, the new key/value pair is inserted at the index.
If a value already exists at that index, it is replaced. If collision occurs and two elements have the same index, they are stored as a LinkedList or binary tree at the position of the index.
2) What is a HashMap's initial capacity?
Initial capacity is the initial size of the array used to store data. The default initial capacity is 16. Data sets with more iterations and fewer values do well with low initial capacity.
Data sets with less iteration and more values do well with high initial capacity.
3) How is HashMap implemented in Java?
HashMap is implemented as an array. This array is indexed based on the hash values of the keys. When you perform a get() for a given key, you're really retrieving a particular index of this array.
This is why HashMaps have a near constant search time O(1).
4) What does put() return with a new key?
5) What is the time complexity of get()?
Constant time or O(1). This is because get() is really like performing arr on the underlying array.
6) What is performance cost of initial capacity being too low?
The performance cost of resizing the underlying array can be costly. A low initial capacity can result in more resize operations which create new objects and populate them with old objects.
7) What is performance cost of initial capacity being too high?
Too few key/value pairs combined with too much capacity leads to excessive iteration over a data set that's too big.
8) What is the load factor?
The load factor is a measure of how full the table(array) can get before resizing occurs. The default value is 0.75. This means the capacity can be 75% filled before resizing is triggered.
9) What is capacity?
Capacity is the size of the underlying data array implemented by HashMap.
10) What is collision?
Collision occurs when two keys have the same index in the underlying data array. When this occurs, the nodes are stored as a LinkedList at the index.
11) How is collision handled in the HashMap implementation?
Keys having the same index are stored as LinkedLists at the index where they "collide". If the LinkedList grows beyond a certain capacity, then the list is converted to a binary search tree.
12) Is HashMap thread safe?
No, the thread safe version of a HashMap is the HashTable. You can easily convert the HashTable to a synchronized version as well.