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 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.

• 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

• binarySearch() is used. Arrays.binarySearch()
• Array or Collection must be sorted before search.
• Search must be performed using the same sort order of the collection.
• 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).

e.g. List<String> list = new ArrayList<String>();
list.add("A"); list.add("B"); list.add("D"); list.add("E");
Collections.sort(list);
Collections.binarySearch(list, "E") //will return 4;
Collections.binarySearch(list, "C") //will return -3;

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:

//The no-parameter toArray() method returns an Object[]. This should be cast to the appropriate array type.

String[] strArray = (String[]) strList.toArray();