Internal Working

 Internal Working of HashMap

👉 HashMap works on principle of hashing.
👉 We have put(key, value) and get(key) method for storing and retrieving element from hashmap.

💜 put() method

👉 When we pass key and value object to put() method then Hashmap implementation call hashcode method on key object and return hashcode
👉 This hashcode pass to the hashing function and return integer as bucket location.
👉 Hashing function find bucket location for storing entry object (key value pair)
👉 If two different objects have same bucket location then collision occurs, so hashmap use LinkedList to store objects
👉 While entry insert in LinkedList - use equals() and hashcode() contract- if key object and entry key object are equals and hashcode is also same then override the value, else put entry object in next node

💜 get() method

👉 When call get() then hashmap uses key objects hashcode to find out bucket location which is linked list
👉 While traversing LinkedList call keys.equals() method to identify correct node and return associate value object for that key.
👉 Improve the performance of Hashmap by reducing the collision. SO, we need to override equals and hashcode method.
👉 Once Map filled 75% then Hashmap re-size itself by creating new bucket array of size twice the previous size of hashMap and start putting old element to new one. This process is called rehashing.

Internal working of ArrayList

👉 ArrayList internally uses array object to add or store elements.
👉 ArrayList backed by Array data-structure.
👉 The array of ArrayList is resizable (or dynamic).


In ArrayList class

private transient Object[] elementData;

When we create new ArrayList() then following code executed

this.elementData = new Object[initial capacity];

1. Create empty list with initial capacity
• List   arrlstobj = new ArrayList();  - Default constructor is invoked. It will create internally an array of object with default size 10.
• List  arrlstobj  = new ArrayList(20); - Invoke the constructor with the integer argument. It will create internally an array of Object . The size of the Object[] will be equal to the argument passed in the constructor .
2. Creates the non empty list containing the elements of the specified collection. 
• List  arrlstobj  = new ArrayList(Collection c); - The above ArrayList constructor will create an non empty list containing the elements of the collection passed in the constructor.

 💜 How the size of ArrayList grows dynamically?

public boolean add(E e)

{

    ensureCapacity(size+1);

    elementData[size++] = e;

    return true;

}

1. Before adding element Checking capacity of element.
2. ensureCapacity()  determines what is the current size of occupied elements and what is the maximum size of the array.
3. If size of filled elements is greater than max size of array then increase size of array.
4. New array of new capacity is created and data from old array copied to new array.

int newCapacity = oldCapacity + (oldCapacity >> 1);

(Shallow copy is used - Instead of element reference is copied into array)