Toggle Theme Editor
Slate Blueberry Blackcurrant Watermelon Strawberry Orange Banana Apple Emerald Chocolate Charcoal

Array, List, Map And Table

Discussion in 'Java Update' started by Joe, 23/3/19.

  1. Joe

    Joe Moderator

    Chao cac ban

    Most of us work with array, list and map. Most of us also know their features and how to use them. But how many of us know which one of them is better or faster if they are used for the same development goal ? Python gives us array and list. C# and JAVA have a very similar collection of APIs which range from array, ArrayList up to HashMap and Hashtable. Because of the extensive application purposes I limit myself only to the applying general and show you the comparison results with JAVA examples. Let's review the objects.

    I. Array

    Array
    is a group of elements which can be anything (primitive like an int or a double, a String or an Object), are ordered consecutively and always start with the first index 0. Array is an unchangeable object. An immutable object in OOPL parlance. And that means: an array-element cannot be "deleted" from array or inserted into the array. Only the content of an element can be modified or set to 0/null. An array-element can be accessed directly and arbitrarily (sequentially or randomly) by index (starting with 0, ending with length-1 where length the number of elements). If an array requires more elements or reduce some elements new array must be created before all elements of old array can be copied and the old array is then discarded (for garbage collection.) Example:
    PHP:
    String[] joe = { "Joe""Nartca" };
    ...
    String[] tmp = new String[3]; // temporary
    tmp[0] = joe[0];
    tmp[1] = "Timothy";
    tmp[2] = joe[1];
    joe = new String[tmp.length];
    System.arraycopy(tmp0joe0tmp.length); // now: joe = { "Joe", "Timothy", "Nartca" }
    ...
    Array is thread-unsafe. In a MultipleThreading Environment you have to synchronize the modified array explicitly with the synchronized keyword or with atomic synchronization. Example:
    PHP:
    String[] joe = { "Joe""Nartca" };
    ...
    // used in a multiple threading environment
    synchronized(joe) {
      
    joe[0] = "Joey";
    }
    ...
    II. ArrayList

    ArrayList
    is kinda "mutable" array. An array that can be expanded or reduced is an ArrayList. And that's the main difference to a "pure" array. With the provided methods (or functions) an ArrayList element can be inserted into, appended and removed (deleted) from the ArrayList. Similar to array ArrayList is thread-unsafe and must be explicitly synchronized if it is used in a multiple-threading environment.

    ArrayList which is derived from the Collections method Collections.synchronizedList(ArrayList) is thread-safe and can be used directly in a multiple-threading environment. Such a synchronized (Array)List is named as SynchronizedRandomAccessList. Elements of ArrayList (or LinkedList) can be accessed by indices which always starts with 0 and ends with "size-1" (or length-1 in array). Example:
    PHP:
    List<StringarrayList = new ArrayList<String>();
    arrayList.add("Value at index 0");
    ...
    synchronized(arrayList) {
      
    arrayList.set(0"new value at index 0");
    }
    // from Collections.synchronizedList
    List<StringsynList Collections.synchronizedList(new ArrayList<String>());
    synList.add("Value at index 0");
    ...
    synList.set(0"Value at index 0");
    Note: LinkedList is due to its internal structure (chaining or linking of elements) usually consumes more time than ArrayList. It could take an "eternity" to synchronize and to complete an update of a LinkedList element.

    III. HashMap

    HashMap is kinda form of a referencing List. An element-value of (Hash)Map elements can be only accessed by a reference or by an element-key. Element-key and element-value can be null. The element-arrangement is invisible (or unknown) to users. If you have 3 keys (0, 1, 2) the element of key 1 must not follow element of key 0 and the following element could be the one of the key 3. The sequence arbitrary.
    HashMap is thread-unsafe, hence it must be explicitly synchronized if it is used in a multiple-threading environment. Similar to ArrayList thread-safe HashMap can be derived from Collections.synchronizedMap(new HashMap()) and it is the SynchronizedMap. Example:
    PHP:
     
    // Key is an int, value is a String
    Map<IntegerStringhashmap = new HashMap<IntegerString>();
    hasmap.put(100"Value at key 100");
    ...
    synchronized(hashmap) {
      
    hashmap.put(100"new value at key 100");
    }
    // from Collections.synchronizedMap
    Map<IntegerStringsynMap Collections.synchronizedMap(new HashMap<IntegerString>());
    synMap.put(100"Value at key 100");
    ...
    synList.put(100"Value at key 100");
    IV. Hashtable

    Hashtable is similar to HashMap with the only visible difference that Hashtable is thread-safe and have neither null-key nor null-value. Example: see Collections.synchronizedMap.

    Hashtable is said thread-safe, but it just refers to the so-called "fail-fast" behavior which makes Hashtable relatively "thread-safe". However, fail-fast does not guarantees the consistency. The API description says:
    V. ConcurrentHashMap

    ConcurrentHashMap is a fine-tuned enhancement of Hashtable. More about the enhancements you could confer the API ConcurrentHashMap description or this ARTICLE

    VI. The Difference between Hashtable, HashMap and ConcurrentHashMap

    Click HERE to learn more about the Difference between Hashtable, HashMap and concurrent HashMap.

    VII. Application

    The question is which object is in which case the best to use? Array or List or Map is usually used for arbitrary accessing to a group of objects -as in a database table. The way how objects are accessed is decisive:

    - with or without key,
    - more sequentially or more randomly,
    - numeric key or non-numeric key,
    - flexible (mutable) or fixed (immutable)

    Array is always the best if the working group or table is fixed. Otherwise it depends on the application and working environment (threading). If more sequential accesses are made or no key exists List is the best tool. For the case that a group or a table must be accessed by keys Map is the best choice.

    Nevertheless, in a multithreading environment you should analyze the (application) requirements before you start to decide on what kind of List or Map you want to use. If time and consistency are crucial you should use the system-supported thread-safe List or Map.

    VIII. Own Synchronization Mechanism

    If you have to work with some extra specifications which are not (so well) supported by List or Map in your concurrency development you could design and develop your own synchronized mechanism using the basic wait & notify methods of JAVA object. In such a case the processing time might be faster (or worse) than N single-synchronizations of each object. Example:

    PHP:
     
    public class MySyn {
      public 
    MySyn() {
        
    wait false;
      }
      private 
    boolean wait;
      
    // wait for n nanoSeconds
      
    public synchronized void onWait(int n) {
        if (
    wait) {
          while (
    wait) {
            try {
              
    java.util.concurrent.TimeUnit.NANOSECONDS.sleep(n);
            } catch (
    Exception ex) { // notified...
              
    wait true;
              return;
            }
          }
        } else 
    wait true;
      }
      public 
    void setFree() {
        
    wait false;
        try {
          
    notifyAll();
        } catch (
    Exception ex) { }
      }
    }
    and an app could be as following
    PHP:
     
    import java
    .util.*;
    import java.util.concurrent.*;
    // Joe Nartca
    public class OwnSyn {
      public static 
    void main(String... athrows Exception {
        
    int time 50;
        
    int threads 5;
        
    int rwCount 10;
        if (
    a.length == 3) {
          
    threads Integer.parseInt(a[0]); // Number of Threads
          
    time Integer.parseInt(a[1]);    // Synchronizing time
          
    rwCount Integer.parseInt(a[2]); // Number of RW
        
    }
        
    OwnSyn os = new OwnSyn();
        
    os.mySyn(threadstimerwCount);
      }
      public 
    void mySyn(final int threads, final int time, final int countthrows Exception {
        
    // create own Syn.Mechanism
        
    final MySyn ms = new MySyn();
        
    Random ran = new Random(time);
        
    HashMap<IntegerStringhm = new HashMap<IntegerString>(count);
        for (
    int i 0count; ++ihm.put(i"Element_"+i);
        
    ExecutorService tPool Executors.newFixedThreadPool(threads);
        
    // do the random Read/write 5x MAX-loops
        
    double rTime System.nanoTime();
        for (
    int j 0threadsj++) {
          
    tPool.execute(() -> {
            for (
    int k 0countk++) {
              
    Integer x ran.nextInt(count);
              
    // synchronize cnt and hm
              
    ms.onWait(time);
              
    //
              // do your updates of other objects here
              //
              
    String s hm.get(x);
              
    hm.put(x"El"+ran.nextInt(count));
              
    ms.setFree();
            }
          });
        }
        
    tPool.shutdown();
        
    // wait for completion
        
    tPool.awaitTermination(Long.MAX_VALUETimeUnit.DAYS);
        
    double t = ((double)(System.nanoTime() - rTime)) / 1000000L;
        
    System.out.printf("MySyn: %d threads for %d Reads&Writes: %.3f ms. Per Access: %.3f"+                       "microSec.\n",threadscountt, (t*100));
      }
    IX. Some Comparison between Array, List and Map

    Note: bear in mind that synchronization always requires some more management and that worsens the processing time.

    The following Performance test program [see download] shows you the true behavior of array, List and Map. The Results were based on Windows 10, intelCore i5, 1.7 GHz, 8GB RAM. Survey the result or run the MapListTest.java and make your own conclusion...
    PHP:
    MultipleThreading Environment (here5 threadseach thread 500000 Reads&Writes)
    +------------------------------+----------------------+-----------------------+
    Object                       5 Rounds (milliSec.) | Per R (microSec)  |
    +------------------------------+----------------------+-----------------------+
    | array                        |        
    735.000       |      1.470            |
    +------------------------------+----------------------+-----------------------+
    ArrayList                    |       1071.200       |      2.142            |
    +------------------------------+----------------------+-----------------------+
    Collections.synchronizedList |        863.200       |      1.726            |
    +------------------------------+----------------------+-----------------------+
    HashMap                      |       2347.600       |      4.695            |
    +------------------------------+----------------------+-----------------------+
    Hashtable                    |       1705.600       |      3.411            |
    +------------------------------+----------------------+-----------------------+
    Collections$SynchronizedMap  |       1838.800       |      3.678            |
    +------------------------------+----------------------+-----------------------+
    ConcurrentHashMap            |       1385.800       |      2.772            |
    +------------------------------+----------------------+-----------------------+
     
    SingleThreading Environment (5 x 500000 Reads&Writes)
    +------------------------------+----------------------+-----------------------+
    Object                       5 Rounds (milliSec.) | Per R W  (microSec) |
    +------------------------------+----------------------+-----------------------+
    | array                        |         
    63.800       |      0.128            |
    +------------------------------+----------------------+-----------------------+
    ArrayList                    |        555.600       |      1.111            |
    +------------------------------+----------------------+-----------------------+
    Collections.synchronizedList |        603.200       |      1.206            |
    +------------------------------+----------------------+-----------------------+
    HashMap                      |        880.800       |      1.762            |
    +------------------------------+----------------------+-----------------------+
    Hashtable                    |       1293.200       |      2.586            |
    +------------------------------+----------------------+-----------------------+
    Collections$SynchronizedMap  |       1509.400       |      3.019            |
    +------------------------------+----------------------+-----------------------+
    ConcurrentHashMap            |       1575.600       |      3.151            |
    +------------------------------+----------------------+-----------------------+
    It's interesting to see that Collections.synchronizedList is processed faster than ArrayList in a MultipleThreading environment, but slower in Singlethreading process. It's clear that Collections.synchronizedList is optimized for a MultipleThreading environment. Further reason: see below.

    Hashtable, Collections$SynchronizedMap and ConcurrentHashMap are slower in single-threaded app. The main reason is the internal extra synchronization work that isn't needed in a SingleThreading environment.
     

    Attached Files:

    Last edited: 25/3/19

Chia sẻ trang này

Loading...