Java Container Class

Collection & Map

Collection – A collection represents a group of objects, known as its elements.Some collections allow duplicate elements and others do not. Some are ordered and others unordered.

Map – An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

3 ways to loop map:

  • Set keySet()
  • Collection values()
  • Set< Map.Entry< K, V>> entrySet()

List Set & Queue

List Set & Queue inherit Collection
Difference:

  • List: an ordered collection, the element can be duplicated
  • Set: elements can not be duplicated

List

The list provides a special iterator called ListIterator.

ListIterator<E> listIterator();

ListIterator<E> listIterator(int index);

public interface ListIterator<E> extends Iterator<E> {
    // Query Operations

    boolean hasNext();

    E next();

    boolean hasPrevious();

    E previous();

    int previousIndex();

    void remove();

    void set(E e);

    void add(E e);
}

ArrayList

  • ArrayList implements List with array.
  • It allows inserting null.
  • size, isEmpty, get, set, iterator, add are all O(1), if add N, it will be O(N)
  • ArrayList is not synchronized for threads
  • By default, the first time we insert the element the size of it is 10.
  • if exceed, the size will increase 50%

source code:

transient Object[] elementData;

private int size;

All elements are saved within the object array and size is used for length control.

source code of add:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

The add operation will check the length. If not match then it will call grow (Arrays.copyOf)

source code of remove:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

It will use System.arraycopy to move all elements behind the target index and remove the last element.

That’s why the cost of adding and removing is expensive 🙂

It alos has a function trimToSize() which can be used for compressing the size of array

public void trimToSize() { 
    modCount++; 
    if (size < elementData.length) { 
        elementData = Arrays.copyOf(elementData, size); 
    } 
}

Besides, it implements RandomAccess. RandomAccess also includes: ArrayList, AttributeList, CopyOnWriteArrayList,RoleList, RoleUnresolvedList, Stack, Vector

There is one comment within the RandomAccess:

for (int i=0, n=list.size(); i < n; i++) {     
    list.get(i);
}
runs faster than this loop:
for (Iterator i=list.iterator(); i.hasNext(); ) { 
   i.next();
}

Compared with Vector

  • almost the same. Only different is Vector is synchronized so it’s more expensive
  • Vector grows 2 times while ArrayList grows 1.5 times
  • Vector also contains Stack

LinkedList

LinkedList is also an ordered container class. LinkedList implements List with Link

ArrayList V.S LinkedList

  • Get: ArrayList can use index to get. LinkedList have to find from the beginning
  • Add & Remove: LinkedList can easily add and remove by breaking the link. ArrayList have to copy all data and move position
  • Grow: ArrayList has to apply for a larger array and move the data. LinkedList can dynamically create new link node

source code:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

A two way link

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

Each linkedList will have first and last point

Add and Delete:

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

LinkedList also implements the Deque interface which inheirts from Queue. So it also supports pop, push and peek

Set

Set doesn’t implement any function like colleciton. Set is just a concept: elements cannot be duplicated

e.g. HashSet, LinkedHashSet, TreeSet

HashSet

  • HashSet implements Set and it is based on HashMap.
  • Disorderd
  • Allow null element

source code:

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object();

So all add, reomve etc are the operaion of HashMap. The Iterator is just the keySet of HashMap

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public void clear() {
    map.clear();
}

LinkedHashSet

LinkedHashSet can use Link to keep the order of set elements.
LinkedHashSet is based on LinkedHashMap

TreeSet

The order of TreeSet is ( e1.compareTo(e2) == 0 ) TreeSet is based on TreeMap and the element must implement Comparable interface ( e1.compareTo(e2) == 0 )

Map

HashMap

It’s stored by hash table.

transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

table is used for saving element. If any conflicts, save it to the next link table.

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

LinkedHashMap

It’s similar to hashmap. The difference is it also have the following link tables:

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

TreeMap

it’s based on red-black tree.

WeakHashMAp

if only the weakHashMap has the reference of an element, it will automatically remove the element

Leave a Reply

Your email address will not be published. Required fields are marked *