Arrays and Collections

Here is a practical (rather than theoretical) comparison of how different programming languages use arrays and Collections. I describe the operations a programmer wants to do (adding, updating, sorting) rather than repeating SDK lists of classes, algorithms, wrappers, etc. Let me know if this helps you make more appropriate selection of collection classes/interfaces to suit the behaviors you want.

Topics this page:

Collections

Site Map  
About this site  

Comparing Arrays in Languages

Arrays in C and C++ are just pointers to an address in memory, and indexes to an array are offsets from that address. This made them error prone and thus a notorious hunting ground for "buffer overrun" security vulnerabilities which enable hackers to gain elevated access to the hacked system.

C# Fixed-Sized Array Coding

C# supports arrays as a definite, distinct reference type (objects of a class with methods and properties), so out-of-bounds errors will result in an error that error handling routines can respond to specifically.

• System.Array manages static arrays that cannot be resized once instantiated.
• ArrayList objects from the System.Collection class can have a dynamic number of elements.

Sample C# code:

public void ArrayTests(){
	string[] name = {"Aaron","Matthew","Mark","John"); // define array.
	int index = Array.IndexOf(names,"Aaron"); // returns index into array.
	ChangeName(names);
	Assert.IsTrue(names[0] == "Allen"); // note zero is the first item.
}
private void ChangeName(string[] names){ // string[] can instead be an interface.
	names[0] = "Allen";
}

JavaScript Arrays

JavScript 1.0 authors had to create their own makeArray() function. Note the need in JavaScript to explicity specify

JavaScript 1.1 has an array object.

VIDEO: 6:00 into JavaScript Arrays in WinJS within Windows 8 include functions to push, pop, slice, splice, join, concat, map, filter, some, every, forEach, reduce, sort, reverse (like Lync).

Ruby Arrays

The first and last items in a Ruby array defined with: my_array = ['venus','earth','mars'] can be accessed with my_array.first and my_array.last or my_array.each_with_index do |an_element, index|
?> puts "#{an_element} is number #{index}
end

The Java Collections Framework

A Java collection (implementation of package java.util new to Java 1.2), can store data of different types in a single structure and be sized dynamically (allowed to grow or shrink). It's a refinement of the C++ Standard Template Library (STL) and Smalltalk's collection hierarchy.

Visio class diagram:

• Interfaces to implement are in purple and use thin lines.
• Abstract classes to extend are in blue and use thick lines.
• Concrete classes to instantiate (with new constructor) are in green.
• Historical legacy classes Stack and Vector (reworked from JDK 1.1) are in white. Deprecated Dictionary and its Hashtable class are not shown.

Defensive Array Programming

Validate all parameters.

To protect Java array accesses, precede them with assert statement:

assert((index > 0) && (index < N_ELEMENTS);
i = array[index];

Java Array Constants

Unlike C, Java does not support direct manipulation of pointers into arrays.

In Java, array arguments are always passed by address, not by value.

Java arrays know how many entries they have when created.
Unlike C, the size of Java arrays is given when it is created with the new constructor.

Array constants are specified as a list of scalar constants enclosed in braces.

int b[] = new int[7]; // set to defaults of 7 elements.
int a[] = new int[] { 1, 2, 3:2, 5:* };

The variables named “a” and “b” are also called the declarator. Unlike C, the initializer “5” is not specified. The repeat operator (:) specifies repetition of a constant element array. When an asterisk (*) is specified, the constant_element “5” is repeated as many times as necessary until the array has been initialized to the intializer. Thus, the above initializer for variable “a” is the same as:

int[] a = { 1, 2, 3, 3, 5, 5, 5 };

Use line breaks to separate each dimension of a nested (multi-dimensional) array [i rows][j columns]:

int a[2][] = { { 1, 2, 3, 4},
               { 1, 2, 3, 4}};

The Arrays class is concrete.

Array Manipulations

An array is a structure that holds multiple values of the same data type (int or string). Java public static main functions declare String args[] to use an array to hold its arguments. To list them:

n=args.length;
for( int i=0; i<n; i++ ) { 
   System.out.println( "Parm "+ i +"="+ args[i] ); 
}

An index points to the value in each element within an array. Its use of a sequential index means arrays cannot contain duplicates. The first element is selected by subscript 0 (zero).

The array length property -- the number of elements within an array -- is established when the array is created (at runtime). Arrays are not growable after initialization.

Array elements are selected by enclosing an integer expression in brackets ([]).

Unlike C, if an array index refers outside the specified range, Java throws a ArrayIndexOutOfBoundsException rather than allow buffer overrun conditions that can be exploited by hackers.

Arrays can make use of collection methods for sorting and expansion when converted to a list collection

List listX=java.util.Arrays.asList( arrayY );

Loading and using arrays and collections is one of the major tricks to improve the run-time performance of busy applications because working in memory is faster than opening files and reading and writing to hard disks.

Marcus Green's notes on the SCJP exam object 1

Write code that declares, constructs and initializes arrays of any base type using any of the permitted forms, both for declaration and for initialization.

Subclassing AbstractCollection directly instantiates a bag -- an unordered collection that allows duplicate elements.

Each additional level in the subclass makes more methods available. For example, when an ArrayList is instantiated by extending AbstractList and implementing List, it inherits methods of the Collection interface because AbstractList extends the AbstractCollection interface, which provides the toString() method.

Abstract classes allow a collection to implement optional methods.

To make a collection modifiable, simply override the set( object ) method.

To make a collection grow, override the add( object ) and remove( int index) methods. New elements are added immediately prior to the implicit cursor. After adding an element, calling previous() returns the new element and calling next() returns what would have been the next element prior to the add operation.

iterator() and size() methods are not in the AbstractCollection class because they need to be relevant to each structure.

To make a twoi-dimensional array, define an array within an array, such as:

String[] [] FirstName; FirstName = new String[14] [];

or

String[] [] FirstName = new String[14] [];

Roedy Green on Java Collections

Populating Collections

To add an object (line) to vectorTZ:

vectorTZ.add(line);

To add objects in collectionC to vectorTZ:

boolean vectorTZ.addAll( collectionC );

Boolean functions return true if action was taken successfully and false if not.

To populate the vector with the intersection of elements in another Collection:

void vectorTZ.retainAll( c );

Java Collection operations do not need to be within a try-catch block because the Unsupported Operation Exception thrown when an add is attempted on a read-only collection is an extension of the RuntimeException class.

Methods for Vectors

To determine if a vector has been populated with a specific object:

vectorTZ.contains( ObjectO );

To assign an object (line) to a specific index:

vectorTZ.set( int index, object );

To obtain a row from a vector (cast to String):

String line = (String)vectorTZ.get(i);

To rid the vector of a single object “O”:

boolean vectorTZ.remove( ObjectO );

To determine if a vector has been populated with objects:

vectorTZ.isEmpty();

To determine if a vector contains all the elements in another collection:

boolean vectorTZ.containsAll( collectionC );

To get a count of elements in a vector:

int vectorTZ.size();

To rid all elements from the vector:

boolean vectorTZ.removeAllElements();

To rid all elements also found in another collection:

void vectorTZ.removeAll( Collection );
void vectorTZ.clear();

Sorting/Ordering

There are several ways to order and re-order objects.

Primitive String and Integer classes can implement the java.lang.Comparable interface to use a natural sorting order using the lexicographical compareTo() method, which places numbers before alpha letters and upper case A-Z letters before all lowercase a-z letters.

Linked list Abstract classes allow a Collection to be sorted by being instantiated as another type:

Set set = new HashSet();
...
Set sortedSet = new TreeSet(set);

To define objects (such as dates) can be inserted in reverse order:

Comparator comparator = Collections.reverseOrder();
Set reverseSet = new TreeSet(comparator);
reverseSet.add("A");

For locale-specific ordering, use Collator with CollationKey.

The Java Collections Framework provides standard methods for working on all elements in the entire collection all at once:

• sort( object or primitive ) is stable -- does not reorder equivalent elements while sorting.
• reverse(list1) order
• shuffle(list1) randomly

VB Bubble Sort

This VB function sorts a small string array in ascending order, without using any special external object.

Function SortAscending(myArray)
Dim pArray, i, j, temp
pArray = myArray  'Create another array to hold results.
For i = UBound(pArray) - 1 To 0 Step -1
    for j= 0 to i
        if uCase(pArray(j)) > uCase(pArray(j+1)) then
            temp=pArray(j+1)
            pArray(j+1)=pArray(j)
            pArray(j)=temp
        end if
    next
next
SortAscending = pArray
end Function 'SortAscending

This approach creates another array, so both the before and after array can be printed out in this sample call:

theArray = array("C","B","A")
outputArray = SortAscending (theArray)
For i=0 to ubound(outputArray)
    print i &" Before: ["& theArray(i) &"] After: ["& outputArray(i) &"]"
Next

In the real world, theArray will be created by other code.

TIP: Define a coding standard whether a space is allowed between array name and the (iterator).

The result

0 Before: [C] After: [A]
1 Before: [B] After: [B]
2 Before: [A] After: [C]

TIP: When displaying strings, it's best to encase each around [braces] so that leading and trailing spaces become visible.

TIP: Define a coding standard whether a space should precede and follow each operator such as = and >.

VB arrays are actually SAFEARRAY variables, which involes some overhead in making them syntactically simpler to program, such as UBound automatically providing the upper bound array index. So bubble sorts are appropriate only for small lists. When the array gets more then 20, instead use a b-tree algorithm.

Algorithms for Collections

The Java Collections Framework provides standard methods for working on all elements in the entire collection all at once:
• fill( list1, o ) -- list1 with a single object o
• copy( list1, list2 )
• binarySearch returns an index, which is the negative insertion point if not found. Returns undefined if array is not sorted. Arrays of objects must implement java.lang.Comparable and provide a Comparator.

• min() -- minimum value
• max() -- maximum value

Collections Interfaces & Classes

There are several implementations of the Collection concept.

Collection Interface	New Class	Usage	Arguments & Additional Methods
List is an ordered collection of objects. (has a positional index), so it can have duplicate objects. List overloads add() with add(int, Object) and addAll( collectionC ) to insert objects at the specified index.	ArrayList	extends AbstractList for a resizable Random Access array that's not synchronized. Cloneable.	constructor argument can be a collection or int Capacity, also in ensureCapacity() toArray()
	Vector	expandable array of sequenced objects. Modified to implement Collection. Synchronized.
	Stack	A form of Vector to push LIFO (Last-In, First-Out) pop
	LinkedList	extends AbstractSequentialList so each element references the next and previous element to emulate Stack, queue, and other end-oriented data structures. This doubly linked chain of objects speeds inserts/deletes but slows indexing.	Use xxxFirst() to add, get, or remove at the beginning and xxxLast() at the end.
Sets are unordered and so cannot contain duplicates of the same element. Implemented by the HashSet class. The Set interface does not define additional methods of its own.	TreeSet implements SortedSet. Its constructor argument can be a collection, Comparator, or Sorted Set.	a sorted binary tree of objects stored in ascending order. Does not allow duplicates. Cloneable.	Get the first() and last() elements Use subSet( objectStart, objectEnd ) to obtain a portion of the elements. Use headSet( objectEnd ) to get objects less than objectEnd. Use tailSet( objectStart ) to get objects greater than objectStart.
	HashSet	Unsorted, so no duplicates or null values. Cloneable.	constructor argument capacity of elements plus a fillRatio between 0.0 and 1.0.
	LinkedHashSet	New to 1.4. Extends HashSet for insertion-order iterations.
Maps store objects based on the values of unique key-value associations between objects (such as IP addresses to domain names (DNS), keys to database records, or dictionary words to their definitions). A map can store duplicate objects, but not with duplicate keys. It replaces the Dictionary class deprecated in 1.2. The Map interface does not extend the Collection interface. It is implemented by classes HashTable and HashMap. Map.Entry - An inner interface of the Map interface that defines methods for working with a single key-value pair.	TreeMap implements SortedMap	stores objects in an ascending order of their keys, so it automatically sorts objects to the default Comparator.
	HashMap	reference by key. Not synchronized like Hashtable of Dictionary. Allows nulls.	Uses .equals() to compare.
	WeakHashMap	entry vanishes when its key is no longer reachable by any thread. 1.3 adds a constructor to accept a Map.
	IdentityHashMap	New to 1.4.	Uses the == operator instead of equals() method to compare.

BitSet, an array of boolean bits, is not a set and not part of the Collections framework.

Collections Implementation

Hash Codes

Objects added to a HashSet implement a hashCode() method to calculate an index based on the plain-text string.

To distribute as evenly as possible over the capacity of the collection, space usage is optimized by tuning the initial capacity and a load factor of between 0.0 and 1.0. A load factor of 0.0 has no room.

TreeSet has no tuning options, as the tree is always balanced, ensuring log(n) performance for insertions, deletions, and queries.

The AbstractSet class overrides the equals() and hashCode() methods to ensure two equal sets return the same hash code. Two sets are equal if they are the same size and contain the same elements. By definition, the hash code for a set is the sum of the hash codes for the elements of the set. Thus, no matter what the internal ordering of the sets, two equal sets will report the same hash code.

Synchronized and Sharing

Arrays cannot be declared shared. Arrays are not thread-safe.

Collections classes are not synchronized. The synchronized keyword is used to prevent more than one thread from accessing a block of code at a time. Synchronization functionality is added by use of a wrapper class such as

Map sm = Collections.SynchronizedMap( map1 );

java.util.Collection Framework

The Java collection framework enables polymorphic processing -- manipulation of one collection type through a different collection type, regardless of the collection's internal implementation.

The different implementations of Collection can all use the same methods defined by the Collection interface because the parent Collection interface defines the names of generic methods to:

• determine whether the collection contains() a specified value.
• get the location an element;
• navigate the group with Enumerations by getting the next object in the collection;
• navigate and remove objects with interfaces Iterator or listIterator;
• process the group as a whole with Algorithms to such as clearing or removing all elements from the collection.

The Collection superclass is abstract because it is not meant to be implemented, but its subclasses are implemented. An abstract class cannot be instantiated.

Subclassing AbstractCollection directly implements a bag -- an unordered collection that allows duplicate elements.

To provide functionality for ordering elements, sorting, handling growth, and handling duplicates, AbstractCollection is subclassed by AbstractList, AbstractSet, and AbstractMap.

Collection subclasses are concrete (not abstract) so that an implementation does not have to override every method of the abstract class. To implement a List, only size() and get() methods need to override what is inherited from subclassing AbstractList. Functionality to modify a List are optionally defined by overriding set(), add(), and remove() methods. Similarly, to extend an unmodifiable AbstractMap, only the entrySet() method needs to be overridden and the Map.Entry implemented. For a modifiable Map, override add(), remove(), put(), and support remove() of the iterator returned by the entrySet().Iterator().

The Enumeration interface provides two methods for stepping through an indexed set of objects:

• hasMoreElements() contained in an Enumeration object.
• nextElement() contained by an object.

The Iterator interface enables next(object) and boolean query hasNext(). Its remove() void method delete objects when an enumerator does not. ListIterator extends the Iterator interface by providing methods for iterating through the elements of a list bi directionally: previous(), hasPrevious(), plus previousIndex() and nextIndex()

iterators for the concrete collection implementations are fail-fast. That means that if you are using an Iterator to traverse a collection while underlying collection is being modified by another thread, then the Iterator fails immediately by throwing a ConcurrentModificationException (another RuntimeException). That means the next time an Iterator method is called, and the underlying collection has been modified, the ConcurrentModificationException exception gets thrown.

The Comparator interface provides the compare() method for comparing the elements of a collection. Method equals() returns true if two sets are the same size and contain the same elements in the same order.

Introduction to the Collections Framework by John Zukowski of the MageLang Institute

The hierarchy of classes of the java.lang.Object package are: Dictionary-Stores key-value pairs.

Hashtable-Generates indexes for storing objects in the dictionary. Does not allow null values.
Properties class.

Instances

In Java, arrays exist as objects. To determine if an object is an array (without regard to the base type) use the isArray() method of the Class class.

To determine if a value is contained in an array Parent (an instance of the array), use the instanceof operator:

if (p instanceof Parent) {
...
}

Java Set Operations

The Java System class static method arraycopy copies the first dimension of an array. Multi-dimensional arrays use the elements of this first dimension to refer back to the source array elements, which are, in turn, arrays.

To create a stand-alone array, allocate new sub-arrays, then arraycopy the source array.

Public methods of a collection provide a view.