Map implementations

• HashTable
• HashMap
• IdentityMap
• EnumMap
• ConcurrentHashMap
• LinkedHashMap
• TreeMap
• WeakHashMap
• Collections.SynchronizedMap

Youtube : link

How does HashMap works in Java

• Array created with default capacity of 16
• Then getting hash code of the key
• It rehashes the hash code to prevent against a bad hashing function from the key that would put all data in the same index (bucket) of the inner array
• It takes the rehashed hash hashcode and bit-masks it with the length (minus 1) of the array. This operation assures that the index can’t be greater than the size of the array. You can see it as a very computationally optimized modulo function.

• Finding appreciate array index according to hash code and saving in bucket associated with this index
• In Java 8 , if bucket size more than 8 automatically converting that bucket from linked list to read black tree
• Can auto size the map according to load factor. Initial arrays size is 16 and load factor is 0.75
• HashMap is not thread safe but HashTable is thread safe but locks whole data structure during concurrent access.  On the other hand , ConcurrentHashMap is locking only bucket
• Mostly Integer and String used as map key because they immutable and provide string hash code function
• If you have too many data to put on Map , it is advisable to create map with approximate high initial capacity. Because there is additional overhead of shrinking the map

Source : http://coding-geek.com/how-does-a-hashmap-work-in-java/

Youtube : link

Java Collections

Iterable Interface

The Iterable interface is the root interface for all the collection classes because the Collection interface extends the Iterable interface, therefore, all the subclasses of Collection interface also implement the Iterable interface.

The iterable interface contains only one abstract method.

• Iterator iterator(): It returns the iterator over the elements of type T.

Iterator Interface

The iterator interface provides the facility of iterating the elements in a forward direction only.

public interface Iterator<E>{
        E next();     

        boolean hasNext();

        void  remove();

        default void forEachRemaining(Consumer<? super E> action);

}

Collection Interface

The Collection interface builds the foundation for the Collection framework. The collection interface is one of the interfaces which is implemented by all the Collection framework classes. It provides common methods to implement by all the subclasses of collection interfaces.

public interface Collection<E>{

        boolean add(E element)
        Iterator<E>  iterator()  
       int size()boolean isEmpty()
       boolean contains(Object obj)
       boolean containsAll(Collection<?> c)
       boolean equals(Object other)
boolean addAll(Collection<? extends E> from)
       boolean remove(Object obj)
       boolean removeAll(Collection<?> c)
       void clear()
boolean retainAll(Collection<?> c)
       Object[] toArray()
       <T> T[] toArray(T[] arrayToFill)   
        ...............
}

Concrete Collections

List Interface

ArrayList and LinkedList implements this interface.  get and set methods can be works  different  in 

terms of performance due to nature of array and list data structure. Java language designer added

RandomAccess tagging interface in order to distinguish between these two

public interface List<E>{

        void add(int index, E element)

void remove(int index)

E get(int index)

E set(int index, E element)

}

Set Interface

* Usually implemented by HashSet and TreeSet classes

* TreeSet visits elements in sorted order

* In HashSet if someone providing poor hashing algorithm then it can be slower. On the other hand TreeSet performance guaranteed. But you have to provide Compactor or implement compareTo method  

Queue  Interface

* Queue let you efficiently add at the tail and remove from head

* Deque can add/remove on both ends

* Priority Queue  isn't queue 

    -  doesn't remember in which order elements were added

    -  when removed , highest priority elements were removed

    -  useful for work scheduling 

Concurrent Modification

Suppose one iterator traverses a collection and  another modifies the collection by add/removing the

element. in the case of linked list , that won't work - the links will not be consistent. Linked list

detects the concurrent modification and throws ConcurrentModificationException

In order to understand to which collection have modification count you need to check the java API

documentation.  This is also sometimes called fail-fast

Fail Fast vs Fail Safe 

Reference - 1

Reference - 2 

---

Maps

* HashMap hashes the keys, TreeMap organizes them in sorted order

* map.get(id) can return null if not exists. Then you need to check the value. In order to avoid you can use map.getOrElse(id, $value) if key absent returns $value

* Easiest way to iterate over map : map.forEach ( (k,v)-> doSomething ) 

* Updating map entries

• map.put(word, map.get(word) +1 )
• If key is not present then you can use map.put(word, map.getOrDefault(word,0 ) + 1 )
• map.putIfAbsent(word, 0) then map.put(word, map.get(word) +1)
• map.merge(word, 1 , Integer::sum)  If word wasn't present, put 1 . Otherwise , put them sum of 1 and previous value
• Efficient map.forEach( (k,v) -> do something with k,v )

* LinkedHashMap traverses the entries in the other which they were added

Views

* A view implements a collection interface without storing the elements. Examples :

  Collection<String> greetings = Collections.nCopies(100,"Hello");  // create illusion of 100 hellos

  Collection<String> greetings = Collections.singletion("Helllo");

  Collection<String> greetings = Collections.emptySet();

  List<Employee> list = staff.subList(10,20);

Restricted Views

Collections.unmodifiableCollection

Collections.unmodifiableList

Collections.unmodifiableSet

Collections.unmodifiableSortedSet

Collections.unmodifiableNaviagableSet

Collections.unmodifiableMap

* look but don't touch

* Synchronized views for safe concurrent access. But you should use  a thread safe collection instead.

  

---

Practical

List<String> names = Arrays.asList("A", "B", "C");

In Java - 7

List<Integer> digits = [1,2,3,4,5,6];   

Set<Integer> digits = {1,2,3,4,5,6};

In Java -9

List<Integer> digits = List.of(1,2,3,4,5,6);   

Set<Integer> digits =  Set.of(1,2,3,4,5,6);

Map<Integer, String> map  = {4 : "ab", 5 : "bc", 6 : "ce"};

In Java -9

Version 1  : 

Map<Integer, String> map  = Map.of(4 , "ab", 5 , "bc", 6 , "ce");

OR

Version -2 : 

import static java.util.Map.*

map = ofEnteries( entry(4,"a") ,   entry(5,"b") , entry(6,"d") )

* Version 1 works only if you have less than 10 elements

Collection to Arrays
String[] names = collection.toArray( new String[collection.size()]);

References 

Image : https://facingissuesonit.com/2019/10/15/java-collection-framework-hierarchy/

Book :  Core Java 11 Fundamentals, Second Edition by Cay S. Horstmann