interfaces for collections and maps

there are more data types then just arrays

• java.util.Collection for lists, sets, queues
• java.util.Map for associative memory
• basic operations:
  • request number of elements
  • add, delete, select, find elements
  • set operations
  • array conversion

ArrayLists

• flexible array of objects

import java.util.*;

public class ArrayListDemo {

public static void main(String args[]) {

  ArrayList<String> aL = new ArrayList<String>();
      // create an empty array list of Strings
  System.out.printf("%25s: %d\n","initial size of aL",aL.size());
// ***
// *** add objects to the array list
// ***
  aL.add("This");
  aL.add("is");
  aL.add("an");
  aL.add("arraylist");
  aL.add("of");
  aL.add("String objects");
  aL.add(1, "is really");
  System.out.printf("%25s: %d\n","size of aL after adding",aL.size());
// display the array list
  System.out.printf("%25s: %s\n\n","contents of aL: ",aL);
// Remove elements from the array list
  aL.remove("of");
  aL.remove(2);
  System.out.printf("%25s: %d\n","size of aL after deleting",aL.size());

  System.out.printf("%25s: ","contents of aL: ");
  for (int i=0;i<aL.size();i++)   // .size() and not .length as for arrays
    System.out.printf("%s ",aL.get(i));
  System.out.printf("\n\n");
  aL.clear();                        // remove all elements
  System.out.printf("%25s? %b\n","is aL empty",aL.isEmpty());
  }  // end of ArrayListDemo.main()
}    // end of ArrayListDemo

list operations

• boolean add(element): adds element to the container; returns success
• boolean remove(element): deletes element from the container; returns success
• void clear(): deletes all elements of the container
• int size(): returns the number of elements in the container
  nothing
• boolean contains(element): returns true if element ∈ container; false otherwise
• int indexOf(element): returns the index of element; -1 if not present
• boolean isEmpty(): returns true if container contains no element; false otherwise
  nothing
• toArray(): returns an array with all the elements of the container

ArrayList vs LinkedList

ArrayList

• list functionality by mapping to array
• implements interface List

LinkedList

• double linked list
• with entries to the successor and predecessor
• helpful for adding and deleting elements at specific positions

linked lists are a central structure for data representation and handling in informatics,
they are however not often employed for storaged of scientific data and in numerical computing

collection of data: sets

java.util.Set

• mathematical set
• no double entries, e1.equals(e2) always false

HashSet

• implementation of interface Set using a hash algorithm

TreeSet

• implementation of interface Set using a sorted tree

LinkedHashSet

• implementation of interface Set
• remembers the order of elements

binary / ordered / sorted trees

• 
  nothing
• objects need to be Comparable
  nothing
• fast access/search: $\ \log(size)$
• absolutely necessary for repeated manipulation
  of very large data sets
• TreeSet (only keys)
  TreeMap (map key $\to$ value)

hash table and functions

hash function

• integer: hash value
  integer: hash code
  integer: hash sum
  integer: checksum
• password encription
  widely used alogrithm: md5
• identification of identical content
  identification of identical objects
  identification of identical entries
  identification of identical data
• collision avoidance algorithm necessary

associative data storage: maps

java.util.Map

• associative memory
  map key $\to$ value
• mathematical map/function
  combines a key with a corresponding value
  via intermediate index (hash value)
• dictionary, lexicon, telephone book
• no order of elements
• no implementation of interface Collection
  because of the coherence key – data

HashMap

• association String $\rightarrow$ int[]
  only in between objects,
  not in between primitive data types like int, double
• objects need to be instantiated

import java.util.*;

public class HashMapDemo {

public static void main(String args[]) {

  HashMap<String,int[]> hM = new HashMap<String,int[]>();
     // only objects, no primitive data types like int, double
// ***
// *** put objects to the HashMap (not add)
// ***
  hM.put("Lara",new int[2]);    // create new String, int[] objects
  hM.get("Lara")[0] = 18;       // set age of Lara
  hM.get("Lara")[1] = 168;      // set height of Lara

  hM.put("John",new int[3]);
  hM.get("John")[0] = 19;       // set age of John
  hM.get("John")[1] = 178;      // set height of John
  hM.get("John")[2] = 81;       // set weigth of John

  hM.put("Greg",new int[2]);
  hM.get("Greg")[0] = 17;       // set age of Greg
  hM.get("Greg")[1] = 188;      // set height of Greg

// ***
// *** iterate over HashMap (ordering not retained)
// ***
  for (String name : hM.keySet())  // loop over all keys
    {
    System.out.printf("name: %5s, age: %3d years, height: %3d cm",
           name,hM.get(name)[0],hM.get(name)[1]);
    if (hM.get(name).length==3)   // check for number or data entries
      System.out.printf(", weight: %3d kg\n", hM.get(name)[2]);
    System.out.printf("\n");
    }
// ***
// *** various testing
// ***
  System.out.printf("      any Clara there? %b \n", hM.containsKey("Clara"));
  System.out.printf("how many folks arount? %d \n", hM.size());
  System.out.printf("trying to remove Jonas %b \n", hM.remove("Jonas"));
  System.out.printf("trying to remove Greg  %b \n", hM.remove("Greg"));
  System.out.printf("   all remaining folks %s \n", hM.keySet());

  }  // end of HashMapDemo.main()
}    // end of HashMapDemo

Map member functions

• identical for HashMap
  identical for TreeMap
  identical for ...
  just exchange definitions in program
• .put(key,value): creates a new key-value entry to HashMap
  not .add() like for collections since position is not determined
• .get(key): returns value-object for given key
• .remove(key): removes value-object for given key
  nothing
• .keySet(): set of all keys
• .values(): collection of all values
• .entrySet(): set of all key-value entries
  nothing
• .containsKey(key): checks for the presence of given key
• .containsValue(value): checks for the presence of given value

HashMap of user defined objects

• Integer/Double objects
  for primitive data types, int/double;
  note capitalization
• needed for HashMap<String,Integer>
• attention, objects need to be instantiated!

import java.util.*;

public class HashMapMapDemo {

public static void main(String args[]) {

  HashMap<String,HashMap<String,Integer>> hMM =        // a HashMap of
     new HashMap<String,HashMap<String,Integer>>();    // a HashMap
// ***
// *** put objects to the HashMapMap 
// ***
  hMM.put("Lara",new HashMap<String,Integer>());       // create key-value entry

  hMM.get("Lara").put("age",new Integer(18));          // create new key-value entry
                                                       // for the age of Lara
  hMM.get("Lara").put("height",new Integer(168));      // create new key-value entry
                                                       // for the height of Lara

  hMM.put("John",new HashMap<String,Integer>()); // now its John's turn
  hMM.get("John").put("age",new Integer(19));   
  hMM.get("John").put("height",new Integer(178));   
  hMM.get("John").put("weight",new Integer(81));   

  HashMap<String,Integer> strInt = new HashMap<String,Integer>();
  strInt.put("age",new Integer(17));                   // for Greg
  strInt.put("height",new Integer(188));               // for Greg
  hMM.put("Greg",strInt); 

  strInt.put("age",new Integer(33));                   // replaces
  strInt.put("height",new Integer(199));               // old values
  hMM.put("Anna",strInt);                              // what is happing here?

// ***
// *** looping over keySet()
// ***
  HashMap<String,Integer> tempMap = new HashMap<String,Integer>();
  for (String name : hMM.keySet())                     // loop over all keys
    {
    tempMap = hMM.get(name);                           // just for convenience
    System.out.printf("name: %5s",name);
    if (tempMap.containsKey("age"))
      System.out.printf(", age: %3d",(int)tempMap.get("age"));
    if (tempMap.containsKey("height"))
      System.out.printf(", height: %3d",(int)tempMap.get("height"));
    if (tempMap.containsKey("weight"))
      System.out.printf(", weight: %3d",(int)tempMap.get("weight"));
    System.out.printf("\n");
    }

  }  // end of HashMapMapDemo.main()
}    // end of HashMapMapDemo

exercise: maps

Write a program for manipulating user defined object with a HashMap.

• use your planet program and the class Planet
  for storing the properties of the planets
• when reading the planet data from file
  store now the data in an appropriate HashMap
• pass the HashMap with the planet data to a static member function
  of the Planet class where the printing of all Planet objects should be done.