Java Collections

Hashmap:

Building Blocks:

Internal Data Structure: Array - Entry[] table=new Entry[capacity];

   static class Entry<K,V>{
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
   }

Hash Collisions: If multiple key have same hash it results in to hash collision. To handle this a linkedlist is formed using next reference. While retrieval, this linkedlist has to be iterated and check for equality of the key object to return the corresponding value.

Capacity:  

 (Default value 16)

Capacity is the length of the array or number of buckets in the hashmap. A bucket corresponds to an index of the array. 

This can be initialized with different value. 

 Map<String,String> map = new HashMap<String,String>(capacity);

Load Factor:   (Default value 0.75)

Load factor is the measure how full is the hashtable allowed to get before its capacity is automatically increased.

Threshold: This is the next size of elemnts in hashmap at which hashmap will resize.

                Threshold= capacity * loadfactor.

 Capacity will be increased by twice once element size reaches to threshold.

if( size >= threashold){  //if size after last add call >= threashold then resize table
         resize(2*table.length);
    }

API Snippet

Related Interview Questions:
1. Equals and Hashcode
2. Concurrency
3. Immutability
4. Clone (shallow copy vs Deep Copy)
5. Why capacity size is poer of two?
6. Read/Write Performance

LinkedHashMap

Linkedhashmap extends Hashmap to maintain insertion order of elements. It also maintain the access order and can be used to implement LRU based cache.

It maintains doubly linkedlist running through all of its entries.

Entry:

   static class Entry<K,V> extends HashMap.Entry<K,V>{

         Entry<K,V> before, after;  

         Entry(int hash, K key, V value, HashMap.Entry<K,V) next){

             super(hash,key,value,next);

         }

   } 

Header:

Entry<K,V> header;
       //construction or initialization
       header = new Entry<>(-1, null, null, null);
       header.before = header.after = header;

AccessOrder :

       boolean accessOrder;

        public LinkedHashMap(){
             super();
             accessOrder = false;
        } 

Add Entry:
    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed, else grow capacity if appropriate
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold)
                resize(2 * table.length);
        }

    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;

    }

        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

      void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }

        }

Concurrent Hashmap