Please enable JavaScript.

Coggle requires JavaScript to display documents.

Collections - Coggle Diagram

- - - - It is not synchronized and is not thread-safe.
      - is the unordered collection and does not give a guarantee for any specific order of elements
      - HashMap is hash table based implementation of Map interface.
      - default initial capacity is 16
      - Iterator in hashMap is fail fast
      - [diagram]https://4.bp.blogspot.com/-adRczhctozE/VD_eimhTQbI/AAAAAAAACCg/lfA1G5GZXyM/s1600/How%2BHashMap%2Bworks%2Bin%2BJava%2B(1).jpg
    - - One null key and multiple null values are allowed
      - The null key is handled specially in HashMap, there are two separate methods for that putForNullKey(V value) and getForNullKey(). Null keys always map to index 0. This null case is split out into separate methods for the sake of performance in the two most commonly used operations (get and put), but incorporated with conditionals in others. In short, equals() and hashcode() method are not used in case of null keys in HashMap.
    - - removing
        
        remove(Object key); remove(Object key,Object value)
      - java 8
        
        compute()
        
        teamGoalMap.put("team1",teamGoalMap.get("team1")+1); teamGoalMap.compute("team1",(team,goal) ->goal+1);
        
        computeIfAbsent()
        
        if(!teamGoalMap.containsKey("team3")) { teamGoalMap.put("team3",0); } ... teamGoalMap.computeIfAbsent("team3",value -> 0);
        
        computeIfPresent()
        
        if(teamGoalMap.containsKey("team1")) { teamGoalMap.put("team1",teamGoalMap.get("team1")+1); } ... teamGoalMap.computeIfPresent("team1",(team,goal) ->goal+1);
        
        putIfAbsent
        
        replace()
        
        replace(K key, V value)
        
        replace(K key, V oldValue, V newValue)
    - - If the size of the Map exceeds a given threshold defined by load-factor e.g. if the load factor is .75 it will act to re-size the map once it filled 75%. Similar to other collection classes like ArrayList, Java HashMap re-sizes itself by creating a new bucket array of size twice of the previous size of HashMap and then start putting every old element into that new bucket array. This process is called rehashing because it also applies the hash function to find new bucket location.
      - problem with resizing of HashMap in Java
        
        there is potential race condition while resizing HashMap in Java, if two threads at the same time found that now HashMap needs resizing and they both try resizing. On the process of resizing of HashMap in Java, the element in the bucket which is stored in linked list get reversed in order during their migration to new bucket because Java HashMap doesn't append the new element at tail instead it append new element at the head to avoid tail traversing. If race condition happens then you will end up with an infinite loop.
    - - When we call put method, hashcode() method of the key object is called so that hash function of the map can find a bucket location to store value object, which is actually an index of the internal array. HashMap internally stores mapping in the form of Map.Entry object which contains both key and value object
      - When you want to retrieve the object, you call the get() method and again pass the key object. This time again key object generates same hash code (it's mandatory for it to do so to retrieve the object and that's why HashMap keys are immutable e.g. String) and we end up at same bucket location. If there is only one object then it is returned and that's your value object which you have stored earlier.
      - Since the internal array of HashMap is of fixed size, and if you keep storing objects, at some point of time hash function will return same bucket location for two different keys, this is called collision in HashMap. In this case, a linked list is formed at that bucket location and a new entry is stored as next node.
      - If we try to retrieve an object from this linked list, we need an extra check to search correct value, this is done by equals() method. Since each node contains an entry, HashMap keeps comparing entry's key object with the passed key using equals() and when it return true, Map returns the corresponding value.
  - - - ConcurrentHashMap does not allow null keys or null values while synchronized HashMap allows one null key.
      - Once the size of Hashtable becomes considerably large performance degrades because for iteration it has to be locked for a longer duration. Since ConcurrentHashMap introduced the concept of segmentation, no matter how large it becomes, only certain part of it gets locked to provide thread safety so many other readers can still access map without waiting for iteration to complete.
      - ConcurrentHashMap is introduced as an alternative of Hashtable and provided all functions supported by Hashtable with an additional feature called "concurrency level", which allows ConcurrentHashMap to partition Map. ConcurrentHashMap allows multiple readers to read concurrently without any blocking. This is achieved by partitioning Map into different parts based on concurrency level and locking only a portion of Map during updates. Default concurrency level is 16, and accordingly Map is divided into 16 parts and each part is governed with a different lock. This means, 16 threads can operate on Map simultaneously until they are operating on different part of Map
    - - synchronized(map){ if (map.get(key) == null){ return map.put(key, value); } else{ return map.get(key); } }
        
        Though this code will work fine in HashMap and Hashtable, This won't work in ConcurrentHashMap; because, during put operation whole map is not locked, and while one thread is putting value, other thread's get() call can still return null which result in one thread overriding value inserted by other thread. Of course, you can wrap whole code in synchronized block and make it thread-safe but that will only make your code single threaded. ConcurrentHashMap provides putIfAbsent(key, value) which does same thing but atomically and thus eliminates above race condition. You can use ConcurrentHashMap in place of Hashtable but with caution as CHM doesn't lock whole Map.
      - Since update operations like put(), remove(), putAll() or clear() is not synchronized, concurrent retrieval may not reflect most recent change on Map. In case of putAll() or clear(), which operates on whole Map, concurrent read may reflect insertion and removal of only some entries. Another important point to remember is iteration over CHM, Iterator returned by keySet of ConcurrentHashMap are weekly consistent and they only reflect state of ConcurrentHashMap and certain point and may not reflect any recent change.
  - - - headMap() method returns a NavigableMap whose keys are less than specified
      - tailMap() returns a NavigableMap whose keys are greater than the specified
      - subMap() gives a NavigableMap between a range, specified by toKey to fromKey.
- - - - Fail-fast iterator means if one thread is iterating over hashmap and other thread trying to modify hashmap structurally (meaning inserting or deleting elements) it will throw ConcurrentModificationException and fail immediately.
      - As name suggests fail-fast Iterators fail as soon as they realize that structure of Collection has been changed since iteration has begun. Structural changes means adding, removing or updating any element from collection while one thread is Iterating over that collection. fail-fast behavior is implemented by keeping a modification count and if iteration thread realizes the change in modification count it throws ConcurrentModificationException.
      - Java doc says this is not a guaranteed behavior instead its done of "best effort basis"
      - Also since multiple threads are involved while updating and checking modification count and this check is done without synchronization, there is a chance that Iteration thread still sees a stale value and might not be able to detect any change done by parallel threads. Iterators returned by most of JDK1.4 collection are fail-fast including Vector, ArrayList, HashSet etc
    - - fail-safe Iterators works on copy of collection instead of original collection
      - Contrary to fail-fast Iterator, fail-safe iterator doesn't throw any Exception if Collection is modified structurally while one thread is Iterating over it because they work on clone of Collection instead of original collection and that’s why they are called as fail-safe iterator. Iterator of CopyOnWriteArrayList is an example of fail-safe Iterator also iterator written by ConcurrentHashMap keySet is also fail-safe iterator and never throw ConcurrentModificationException in Java.
- - - - Since HashSet implements Set interface it needs to guarantee uniqueness and this is achieved by storing elements as keys with same value always.
      - private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; }
- - - - Sorting logic must be in same class whose objects are being sorted. Hence this is called natural ordering of objects
      - If any class implements comparable inteface then collection of that object can be sorted automatically using Collection.sort() or Arrays.sort().Objects will be sorted on the basis of compareTo method in that class.
    - - One of advantage of Comparator over comparable is you can create anonymous comparator i.e you don’t need to implement Comparable interface to class whose objects need to be sorted.
      - When you want to sort the list of objects of a class,you can use Comparator interface. You don’t need to implement Comparator (like with Comparable) on the class whose objects need to be sorted. You can create a separate class and implement a Comparator
      - can be created as a lambda expression
- - - - java.util.LinkedList
      - java.util.ArrayDeque