Collections

Collections

Equals and Hashcode

• Mainly used for storing and retrieving objects from hashed collections.
• First object's hashcode is used to figure out which hash bucket the object is in
• Then the equals() method is used to compare objects in the same hash bucket.

This means that:

• equal objects MUST have the same hashcode
• unequal objects can have the same (or different) hashcode (e.g. same bucket but objects are different)
• objects having different hashcodes MUST be unequal

Collections

• There are four basic types of collections: Lists, Sets, Queues and Maps.
• Set, List and Queue implement the interface Collection.

There are four flavours of Collections:

• Sorted -> Means that the order in the collection is determined according to the sort order i.e. properties of the object. Most common sort oder is the natural sort order. e.g. ascending for Integer objects, alphabetical for String objects.

Sort order is defined by implementing the Comparable<T> interface and defining the compareTo method. examples of Sorted collections are TreeMap and TreeSet. If you try to insert an object which is not comparable, it will fail.

• Unsorted -> An unsorted collection can be ordered or unordered. See below.
• Ordered -> Means that we can iterate through the collection in the same specific order every time. For e.g. all lists are ordered by index position. See example below:

import java.util.*;

class Foo implements Comparable<Foo> {
	private String str;
	
	public Foo(String str) {
		this.str = str;
	}
	
	public String toString() {
		return "Foo:" + str;
	}
	
	public int compareTo(Foo f) {
		return str.compareTo(f.str);
	}
}

public class Ordering {

	public static void main(String[] args) {
		List<String> list = new ArrayList<String>();
		list.add("D");
		list.add("A");
		list.add("C");
		list.add("B");
		
		for(Iterator<String> iter = list.iterator(); iter.hasNext();) {
			System.out.println(iter.next());
		}
		//Will print D,A,C,B each time
		
		List<Foo> fooList = new ArrayList<Foo>();
		fooList.add(new Foo("D"));
		fooList.add(new Foo("A"));
		fooList.add(new Foo("C"));
		fooList.add(new Foo("B"));
		
		for(Iterator<Foo> iter = fooList.iterator(); iter.hasNext();) {
			System.out.println(iter.next());
		}
		//Will print Foo:D,Foo:A,Foo:C,Foo:B each time
	}
}

So despite Foo having defined a comparator, ordering is performed according to the element's index position. LinkedHashSet is ordered by insertion, so the last element inserted is the last element in the LinkedHashSet.

This is an example of an ordered, but unsorted collection.

• Unordered ->

e.g. HashSet, iterating over a HashSet is not guaranteed. It might produced the same order many times, but is NOT guaranteed to do so every time. This is why it is unordered.

• The Comparable interface specifies the natural sort order.
• We can also define other sort orders using the Comparator interface.

• LinkedList also implements the Queue interface. It works as a FIFO Queue.
• PriorityQueue is used to order elements according to their priority.

Difference. See the below code example, where a FIFO Queue and a PriorityQueue are populated and elements are retrieved from the head of the queue, using poll().

public class QueueTest {

	public static void main(String[] args) {
		
		Queue<Integer> fifo = new LinkedList<Integer>();
		fifo.offer(2);
		fifo.offer(3);
		fifo.offer(1);
		
		Integer h = null;
		
		while((h = fifo.poll()) != null) {
			System.out.println(h);
		}
		//prints out elements in the FIFO order i.e. 2, 3, 1
		
		Queue<Integer> pQ = new PriorityQueue<Integer>();
		
		pQ.offer(2);
		pQ.offer(3);
		pQ.offer(1);
		
		while((h = pQ.poll()) != null) {
			System.out.println(h);
		}
		//prints out elements according to priority i.e. 1, 2, 3
		//in this case since Integers are used - natural ordering is used as priority
		
	}
}

Searching and Sorting

• binarySearch() is used. Arrays.binarySearch()
• Array or Collection must be sorted before search.
• Collections.sort() takes only List. (Because, Set and Map have sorted versions) and an optional comparator.
• Arrays.sort() takes an array and an optional comparator.
  • Primitive arrays are sorted based on natural order, so no comparator is permitted for primitive sorts.

• Search must be performed using the same sort order of the collection.
  • This implies the same comparator which was used for the sort must be used for the search.
• Successful searches return the index of element that is found
• Unsuccessful searches return the possible insert position of the search element as a negative number. The insert position will be = (-(insert position) -1).

                String[] str = {"B", "D", "F", "H", "J"};
		String[] search = {"A", "C", "E", "G", "I", "K"};
		
		Arrays.sort(str);
		
		for(String s : search) {
			System.out.println(Arrays.binarySearch(str, s));
		}
                //prints: -1, -2, -3, -4, -5, -6

• Collections.binarySearch() is used to return the index position of an element. This works only for Lists ! Why ? because Lists use index based insertions.
• Otherwise use contains() to check if an object is part of a collection or not.

Converting Arrays To Lists To Arrays

• Converting Arrays To Lists - The asList() method

	        String[] sa = {"a", "b", "c"};
		
		List<String> sl = Arrays.asList(sa);
		
		System.out.println("1. sa : " + Arrays.toString(sa));
                //prints: a, b, c
		System.out.println("1. sl : " + sl);
		//prints: a, b, c

		sa[1] = "bb";
		//changes to the array write-through to the string
		System.out.println("2. sa : " + Arrays.toString(sa)); 
                //prints: a, bb, c
		System.out.println("2. sl : " + sl);
                //prints: a, bb, c
	
		sl.set(1, "b");
		//similarly, changes to the list write-through to the array
		System.out.println("3. sa : " + Arrays.toString(sa));
                //prints a, b, c
		System.out.println("3. sl : " + sl);
                //prints a, b, c

• Converting Lists to Arrays - the crazy toArray() method
• There are two versions of toArray(). The first:

public Object[] toArray(); 
//Returns an object array which must be cast into a specific array type
String[] strArray = (String[]) strList.toArray();

• The second:

public <T> T[] toArray(T[] a)
//Returns an array of the type specified in the parameter.
//Advantage is that you avoid the explicit cast as in the first method.
//The method will allocate a new array, if the argument is too small to contain the list.
//If it's too large, the left-over elements will be padded with null ! 
//There are different ways to use this:

List<String> list = new ArrayList<String>();
String[] sA = list.toArray(new String[0]);
//Here an anonymous String[] is passed, just for type identification and the returned array 
//will be newly allocated with the list's elements.

String[] sa = new String[list.size()];
//Here the array is pre-allocated with the correct size.
list.toArray(sa);
//sa will be populated with the list's elements, no need to use the returned value.

• Collections has a useful Collections.reverseOrder() method that returns a reverse Comparator for a given's collections sort order.
• e.g. sort Integers in descending order:

Map<Integer> ascMap = new TreeMap<Integer>();
//Sort in descending order.
Collections.sort(ascMap, Collections.reverseOrder());