JAVA:Collections-Some Good Basic Questions

What is HashMap and Map?

Map is Interface and Hashmap is class that implements this interface.

What is the significance of ListIterator?

Or

What is the difference b/w Iterator and ListIterator?

Iterator : Enables you to cycle through a collection in the forward direction only, for obtaining or removing elements

ListIterator : It extends Iterator, allow bidirectional traversal of list and the modification of elements

Difference between HashMap and HashTable? Can we make hashmap synchronized?

1. The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls. (HashMap allows null values as key and value whereas Hashtable doesn’t allow nulls).
2. HashMap does not guarantee that the order of the map will remain constant over time.
3. HashMap is non synchronized whereas Hashtable is synchronized.
4. Iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't.

Note on Some Important Terms
1)Synchronized means only one thread can modify a hash table at one point of time. Basically, it means that any thread before performing an update on a hashtable will have to acquire a lock on the object while others will wait for lock to be released.

2)Fail-safe is relevant from the context of iterators. If an iterator has been created on a collection object and some other thread tries to modify the collection object "structurally”, a concurrent modification exception will be thrown. It is possible for other threads though to invoke "set" method since it doesn’t modify the collection "structurally”. However, if prior to calling "set", the collection has been modified structurally, "IllegalArgumentException" will be thrown.

HashMap can be synchronized by

Map m = Collections.synchronizeMap(hashMap);

What is the difference between set and list?

A Set stores elements in an unordered way and does not contain duplicate elements, whereas a list stores elements in an ordered way but may contain duplicate elements.

Difference between Vector and ArrayList? What is the Vector class?

Vector is synchronized whereas ArrayList is not. The Vector class provides the capability to implement a growable array of objects. ArrayList and Vector class both implement the List interface. Both classes are implemented using dynamically resizable arrays, providing fast random access and fast traversal. In vector the data is retrieved using the elementAt() method while in ArrayList, it is done using the get() method. ArrayList has no default size while vector has a default size of 10. when you want programs to run in multithreading environment then use concept of vector because it is synchronized. But ArrayList is not synchronized so, avoid use of it in a multithreading environment.

What is an Iterator interface? Is Iterator a Class or Interface? What is its use?

The Iterator is an interface, used to traverse through the elements of a Collection. It is not advisable to modify the collection itself while traversing an Iterator.

What is the Collections API?

The Collections API is a set of classes and interfaces that support operations on collections of objects.
Example of classes: HashSet, HashMap, ArrayList, LinkedList, TreeSet and TreeMap.
Example of interfaces: Collection, Set, List and Map.

What is the List interface?

The List interface provides support for ordered collections of objects.

How can we access elements of a collection?

We can access the elements of a collection using the following ways:
1.Every collection object has get(index) method to get the element of the object. This method will return Object.
2.Collection provide Enumeration or Iterator object so that we can get the objects of a collection one by one.

What is the Set interface?

The Set interface provides methods for accessing the elements of a finite mathematical set. Sets do not allow duplicate elements.

What’s the difference between a queue and a stack?

Stack is a data structure that is based on last-in-first-out rule (LIFO), while queues are based on First-in-first-out (FIFO) rule.

What is the Map interface?

The Map interface is used associate keys with values.

What is the Properties class?

The properties class is a subclass of Hashtable that can be read from or written to a stream. It also provides the capability to specify a set of default values to be used.

Which implementation of the List interface provides for the fastest insertion of a new element into the middle of the list?

a. Vector
b. ArrayList
c. LinkedList
d. None of the above

ArrayList and Vector both use an array to store the elements of the list. When an element is inserted into the middle of the list the elements that follow the insertion point must be shifted to make room for the new element. The LinkedList is implemented using a doubly linked list; an insertion requires only the updating of the links at the point of insertion. Therefore, the LinkedList allows for fast insertions and deletions.

How can we use hashset in collection interface?

This class implements the set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the Null element.

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

What are differences between Enumeration, ArrayList, Hashtable and Collections and Collection?

Enumeration: It is series of elements. It can be use to enumerate through the elements of a vector, keys or values of a hashtable. You can not remove elements from Enumeration.

ArrayList: It is re-sizable array implementation. Belongs to 'List' group in collection. It permits all elements, including null. It is not thread -safe.

Hashtable: It maps key to value. You can use non-null value for key or value. It is part of group Map in collection.

Collections: It implements Polymorphic algorithms which operate on collections.

Collection: It is the root interface in the collection hierarchy.

What is difference between array & arraylist?

An ArrayList is resizable, where as, an array is not. ArrayList is a part of the Collection Framework. We can store any type of objects, and we can deal with only objects. It is growable. Array is collection of similar data items. We can have array of primitives or objects. It is of fixed size. We can have multi dimensional arrays.

Array: can store primitive ArrayList: Stores object only

Array: fix size ArrayList: resizable

Array: can have multi dimensional

Array: lang ArrayList: Collection framework

Can you limit the initial capacity of vector in java?

Yes you can limit the initial capacity. We can construct an empty vector with specified initial capacity

public vector(int initialcapacity)

What method should the key class of Hashmap override?

The methods to override are equals() and hashCode().

What is the difference between Enumeration and Iterator?

The functionality of Enumeration interface is duplicated by the Iterator interface. Iterator has a remove() method while Enumeration doesn't. Enumeration acts as Read-only interface, because it has the methods only to traverse and fetch the objects, where as using Iterator we can manipulate the objects also like adding and removing the objects.

So Enumeration is used when ever we want to make Collection objects as Read-only.

JAVA:Fail fast and Fail safe Iteratotrs

A Fail Fast Iterator is an iterator that attempts to raise an error if the sequence of elements processed by the iterator is changed during iteration.

Fail-safe means, The ability of a system to fail but not produce a catastrophic result.

  

An iterator is considered fail-fast if it throws a ConcurrentModificationException under either of the following two conditions:

1. In multithreaded processing: if one thread is trying to modify a Collection while another thread is iterating over it.

2. In single-threaded or in multithreaded processing: if after the creation of the Iterator, the container is modified at any time by any method other than the Iterator's own remove or add methods.

Note in particular what is implied by the second condition: After we create a container's iterator, during a loop that iterates over the container we must only use the remove (and when applicable add) methods defined for the iterator and that we must NOT use the same methods defined for the container itself. To illustrate this point, suppose we declare and initialize a List in the following manner

List list = new ArrayList();

list.add("Peter");

list.add("Paul");

list.add("Mary");

Let's say we wish to iterate over this list. We'd need to declare a ListIterator as follows:

ListIterator iter = list.listIterator();

Having created this iterator, we could now set up a loop like:

while(iter1.hasNext()){

String str = iter1.next();

// do something with str

}

Because iter is fail-fast, we are not allowed to invoke List's add or remove methods inside the loop. Inside the loop, we are only allowed to use ListIterator's add and remove methods. This makes sense because it is the Iterator object that knows where it is in a List as the List is being scanned. The List object itself would have no idea of that.

The Iterators supported by all the work-horse container classes, such as ArrayList, LinkedList, TreeSet, and HashSet, are fail-fast. The Iterator type retrofitted to the older container class Vector is also fail-fast. For associative containers, such as HashMap and the older HashTable, the Iterator type for the Collections corresponding to either the keys or the values or the pairs are fail-fast with respect to the container itself. That means that even if you are iterating over, say, just the keys of the container, any illegal concurrent modifications to the underlying container would be detected.

One final note regarding iterators versus enumerations: It is also possible to use an Enumeration object returned by the elements() method for iterating over the older container types such as Vector. However, Enumerations do not provide a fail-fast method. On the other hand, the more modern Iterator returned by a Vector's iterator() and listIterator() methods are fail-fast. Hence, iterators are recommended over enumerations for iterating over the elements of the older container types.

A PRACTICAL APPROACH----------->Iterators can be designed so that they are fail fast or fail safe. Depending on the underlying implementation of the Iterator, a ConcurrentModificationException is thrown if the Collection is modified while Iterating over the data structure. It pays to understand how an Iterator will behave under both conditions. Lets try to implement fail fast Vs fail safe iterators of our own.

Our data structure for this example is pretty simple. It defines an interface that abstracts set and get operations on a structure. How the underlying classes handle invalid set operations or the size of the structure is implementation dependent

A data structure interface:

1 2 3 4 5 6

public interface Data<T> extends Iterable<T> { int size(); T getElement(int position); void setElement(int position, T t); }

An underlying implementation of such an Interface, could be say an array of Integers whose size is fixed. Invalid indexes on bounds are not allowed and the internal structure will not grow or shrink. An implementation is given below

An array of integers implementing the interface:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

public class ArrayOfIntegers implements Data<Integer> { private static int DEFAULT_SIZE = 1024; private int mods = 0; private Integer[] integers = new Integer[DEFAULT_SIZE]; @Override public Integer getElement(int position) { checkRange(position); return integers[position]; } @Override public void setElement(int position, Integer integer) { checkRange(position); mods++; integers[position] = integer; } @Override public int size() { return integers.length; } @Override public Iterator<Integer> iterator() { // return new FailFastIter(); // return new NoFailIter(); return null; } private void checkRange(int position) { if (position > DEFAULT_SIZE || position < 0) { throw new ArrayIndexOutOfBoundsException(position); } } // Iterator implementations go here as a private class }

If we wanted to Iterate over the ArrayOfIntegers structure, there are 2 ways to do it. Either ensure that the underlying data structure Integer[] integers is not modified while we iterate over ArrayOfIntegers, or make a copy of Integer[] integers so that any changes made to the internal structure will not affect the caller in any way. Let us look at 2 private Iterator classes that we can place into the ArrayOfIntegers class that will help us achieve both flavors of Iteration

Fail fast:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

private class FailFastIter implements Iterator<Integer> { int currentIndex = 0; int check = -1; int size = integers.length; public FailFastIter() { check = mods; } @Override public boolean hasNext() { checkForModification(); if (currentIndex < size) { return true; } return false; } @Override public Integer next() { checkForModification(); Integer result = integers[currentIndex]; currentIndex++; return result; } @Override public void remove() { throw new UnsupportedOperationException(); } private void checkForModification() { if (check != mods) { throw new ConcurrentModificationException(); } } }

The fail fast Iterator in this example, refers to the internal data structure directly. Every modification to the internal structure is tracked using the ‘mods‘ variable. Our iterator stores this value when it was initially created using the ‘check‘ variable. Both variables are compared every time the hasNext() or next() methods are called. If they are unequal then it means that the underlying structure was changed. This is when the code throws a ConcurrentModificationException

Fail safe:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

private class NoFailIter implements Iterator<Integer> { int currentIndex = 0; Integer[] internal = Arrays.copyOf(integers, size()); int internalSize = -1; public NoFailIter() { internalSize = internal.length; } @Override public boolean hasNext() { if (currentIndex < internalSize) { return true; } return false; } @Override public Integer next() { if (hasNext()) { Integer result = internal[currentIndex]; currentIndex++; return result; } else { throw new NoSuchElementException(); } } @Override public void remove() { throw new UnsupportedOperationException(); } }

The fail safe iterator makes a copy of the internal array data structure and uses it to iterate over the elements. This prevents any concurrent modification exceptions from being thrown if the underlying data structure changes. Of course, the overhead of copying the entire array is introduced. Both implementation can be tested using a program

Iterator test for both iterators:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class IterTest { public static void main(String... args) { new IterTest().go(); } public void go() { Data<Integer> dataArray = new ArrayOfIntegers(); for (int iCounter = 0; iCounter < 100; iCounter++) { dataArray.setElement(iCounter, iCounter); } Iterator<Integer> iterator = dataArray.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); dataArray.setElement(1, 12); } } }

By changing the Iterator implementation that the iterator() method returns, this test program will either throw a ConcurrentModificationException or iterate over all the elements without knowing what changed under the hood.

It makes sense to throw ConcurrentModificationException from an Iterator in certain cases. Under other scenarios you just don’t care if the Iterator will fail or survive an internal structure change. Taking a leaf out of the java Collection API, take a look at the Iterator behavior of an ArrayList Vs that of a CopyOnWriteArrayList.

Iterator test for 2 iterators within the JDK API:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

public class IterTest2 { public static void main(String... args) { new IterTest2().go(); } public void go() { List<String> arList = new ArrayList<String>(); List<String> copyList = new CopyOnWriteArrayList<String>(); populate(arList); populate(copyList); iterate(arList); iterate(copyList); } private void populate(List<String> list) { for (int iCounter = 0; iCounter < 100; iCounter++) { list.add(new Integer(iCounter).toString()); } } private void iterate(List<String> list) { try { for (String x : list) { System.out.println(x); list.add(x); } } catch (RuntimeException e) { e.printStackTrace(); } } }

The CopyOnWriteArrayList does not fail when the internal structure changes, but ArrayList does. This example better highlights the problem of fail fast Vs fail safe iterators. The next time your write a custom iterator for your classes, consider this decision.

JAVA:Static class declarations (Can a class -- inner or outer -- be declared static?)

Q: Can a class (whether an inner or outer class) be declared static?

static means "one per class".

In order to understand the use of the static keyword in class declaration, we need to understand the class declaration itself. You can declare two kinds of classes: top-level classes and inner classes.

Top-level classes

You declare a top-level class at the top level as a member of a package. Each top-level class corresponds to its own java file sporting the same name as the class name.

A top-level class is by definition already top-level, so there is no point in declaring it static; it is an error to do so. The compiler will detect and report this error.

Inner classes

You define an inner class within a top-level class. Depending on how it is defined, an inner class can be one of the following four types:

1. Anonymous. Anonymous classes are declared and instantiated within the same statement. They do not have names, and they can be instantiated only once.

The following is an example of an anonymous class:

okButton.addActionListener( new ActionListener(){
  public void actionPerformed(ActionEvent e){
 dispose();
 } }); 

Because an anonymous class doesn't have a normal class declaration where it's possible to use static, it cannot be declared static.

2. Local. Local classes are the same as local variables, in the sense that they're created and used inside a block. Once you declare a class within a block, it can be instantiated as many times as you wish within that block. Like local variables, local classes aren't allowed to be declared public, protected, private, or static.

Here's a code example:

//some code block .......{    class ListListener implements ItemListener {
     List list;     
      public ListListener(List l) {
              list = l;       }     
        public void itemStateChanged(ItemEvent e) { 
       String s = l.getItemSelected();    
    doSomething(s);      
}   
}   
List list1 = new List(); 
 list list2 = new List();
 list1.addItemListener(new ListListener(list1));
 list2.addItemListener(new ListListener(list2));
} 

3. Member. Member classes are defined within the body of a class. You can use member classes anywhere within the body of the containing class. You declare member classes when you want to use variables and methods of the containing class without explicit delegation.

The member class is the only class that you can declare static. When you declare a member class, you can instantiate that member class only within the context of an object of the outer class in which this member class is declared. If you want to remove this restriction, you declare the member class a static class.

When you declare a member class with a static modifier, it becomes a nested top-level class and can be used as a normal top-level class as explained above.

4. Nested top-level. A nested top-level class is a member classes with a static modifier. A nested top-level class is just like any other top-level class except that it is declared within another class or interface. Nested top-level classes are typically used as a convenient way to group related classes without creating a new package.

If your main class has a few smaller helper classes that can be used outside the class and make sense only with your main class, it's a good idea to make them nested top-level classes. To use the nested top-level class, write: TopLevelClass.NestedClass.

See the following example:

public class Filter {  
Vector criteria = new Vector();  
public addCriterion(Criterion c) {     
criteria.addElement(c);    } 
 public boolean isTrue(Record rec) {     
for(Enumeration e=criteria.elements();     
e.hasMoreElements();) {      
  if(! ((Criterion)e.nextElement()).isTrue(rec))
            return false;       }  
   return true;    }  
public static class Criterion {
     String colName, colValue; 
    public Criterion(Stirng name, String val) {
        colName = name; colValue = val;       }
     public boolean isTrue(Record rec) {       
 String data = rec.getData(colName);        
if(data.equals(colValue)) return true;      
  return false;    
 }    } } 

And when you want to use it:

Filter f = new Filter();
f.addCriterion(new Filter.Criterion("SYMBOL", "SUNW"));
f.addCriterion(new Filter.Criterion("SIDE", "BUY"));
..... if(f.isTrue(someRec)) //do some thing ..... 

One important note: The static keyword does not do to a class declaration what it does to a variable or a method declaration.