Object in Java

In Java, it's the root class. All objects implement the methods of this class.

clone(), creates and returns a copy of the object

equals(Object), tests whether the two objects are equal to each other.

finalize(), garbage collector calls this method when there are no more references to this object

getClass(), returns the runtime class of the Object

hashCode(), hash code value of the Object

toString(), string representation of the Object

Thread related functions:

notify(), notify/awaken a single thread waiting on this object

notifyAll(), notify/awaken all threads waiting on this object

wait(), causes the current thread to wait until another thread invokes notify

wait(timeout), causes the current thread to wait until another thread invokes notify or the timeout is up

Queue, Deque, Stack

Stack (LIFO, Last In First Out)

In Java, the Stack class extends Vector.

Deque (aka Double-Ended Queue), objects can only be added to or removed from the front or back. Doubly linked list is a good implementation structure for this.

In Java, the Deque class extends Queue.

Queue(FIFO, First In First Out)

In Java, the Queue class extends Collection.

LinkedList is a good data structure to implement all of these.

Methods on these classes

push(Object)

pop()

clear()

isEmtpy()

size()

List in Java

LinkedList, ArrayList, Vector, and Stack all implement this interface.

Important methods on this interface:

add(Object)

add(index, Object)

addAll(Collection)

addAll(index, Collection)

clear()

contains(Object)

containsAll(Collection)

equals(Object)

get(index) //return object

indexOf(Object)

isEmpty()

size()

iterator()

subList(index, index) //return List

toArray()

iterator()

set(index, element), replace specified postion with the passed in element

retainAll(Collection)

removeAll(Collection)

remove(Object)

remove(index)

lastIndexOf(Object) //return index of the last occurrence of this object

ArrayList:

clone()

toString()

removeRange(fromIndex, toIndex)

Vector:

clone()

toString()

elementAt(index)

setElementAt(Object, index)

firstElement()

ElementAtIndex(index)

removeAllElements()

removeRange(fromIndex, toIndex)

Stack, last-in-first-out (LIFO), extends vector

empty()

peek()

pop()

push()

search(object)

LinkedList //implements Deque Interface

descendingIterator - Returns an iterator over the elements in this deque in reverse sequential order.

removeFirst()

removeLast()

removeFirstOccurance(Object)

removeLastOccurance(Object)

peekFirst/Last() //retrieve and don't remove

offerFirst/Last() //insert

pollFirst/Last() //retrieves and removes

Simple Java program to test how much time an action takes

public class TimeTest {

public static void main(String[] args) {

int count = 0;

long startTime;

startTime = System.currentTimeMillis();

while (count < Integer.MAX_VALUE) {

count++;

if (count % 1000 == 0) {

System.out.println(count);

}

}

System.out.println("Time in ms: "+ (System.currentTimeMillis() - startTime));

}

}

Red Black Tree

Self balancing binary search tree.

Searches, Inserts, and Deletes in O(log n) where n is the number of items in the tree.

Its leaf nodes don't contain data (are null).

In Java, TreeMap implements this. TreeMap guarantees the keys of the map will be in ascending order sorted according to the comparator provided in the constructor upon creation of the map.

Hashtable vs HashMap

HashTable	HashMap
Synchronized	Unsynchronized
Does not allow null keys or values	Allows one null key and any number of null values
Extends Dictionary	Extends AbstractMap
Default capacity is 11	Default capacity is 16
Both implement the Map interface
Default load factor of 0.75, then they resize

I also read that HashMap does not guarantee the order of the map to remain constant over time.

Synchronized in Java

If a method or class is synchronized, it means it is thread safe.

You can make a non-synchronized collection synchronized by adding the following line:

Map m = Collections.synchronizedMap(new HashMap(...));

You can make a block of text/access to a class synchronized by doing this:

synchronized(m) {

//do something

}

If you choose option 1, make sure you use the reference return by the synchronizedMap function.

If you choose option 2, make sure you synchronize every access to that object/collection.

Synchronized vs Unsynchronized

The first implementation of some Java classes were thread safe, synchronized against threads accessing their data at the same time. However, Java then realized many programs are single threaded and this is overkill as synchronization adds an overhead, so they introduced the same versions of those classes but unsynchronized (and thus faster).

Synchronized	Unsynchronized
StringBuffer	StringBuilder
Vector	ArrayList
HashTable	HashMap

Note on synchronization: Only concurrent access to the same class is synchronized, you may still need to do additional synchronization outside of that class. You can't add or remove from the same class at the same time, but you might want additional synchronization, see example:

Thread 1	Thread 2
if (! list.isEmpty()) { //print list }	for (i = 0; i < size; i++) { list.remove(); }

Thread 1 obtains lock on the list and checks the it isn't empty. It suspends before it prints the list. Thread 2 removes a bunch of items. Thread 1 continues and now is printing out an empty list (not what it wanted to do).

Nil, nil, null, NULL

Ahh the differences between the various nulls that all kind of typedef to 0. Mainly we have them as a convention to denote certain things.

Java
null - a reserved constant that denotes a pointer to a void object
Internally represented as zero. However, you do not compare an int to this.

Javascript
undefined - object hasn't even been assigned yet

null - it is assigned and its value is null (nothing)

if you compare the two, you'll get that they are equal to each other, but they are separate concepts and if you want to find out if a variable is undefined, don't compare it to null.

C
NULL - (void *)0, to be used with pointers
You cannot use this with ints, you might get an error.

C++
NULL - 0
Can be used with pointers and ints. Signifies pointer not pointing to anything.

Objective-C
nil - to be used with object (id) to indicate 'no value'.

Nil - to be used with class pointer to indicate or point the Objective C class to 'no value'.

NSNull - a way of representing nil/null. Where you cannot pass null or use a null value, use this non-null class to represent a null value.