Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Java collections

No description
by

Georgian Parvu

on 22 March 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Java collections

Collections
Purpose

by providing the plumbing
An object that groups multiple elements into a single unit
by providing high performance
& high quality implementations
by using the same
data structures
for input and output
by their nature
Collection
Big boy's garage
Girl's wardrobe
Benefits
Reduce programing effort
Increases program
speed and quality
Allows interoperability
among unrelated APIs
Fosters software reuse
Collection
Overview
Object[] toArray();
<T> T[] toArray(T[] a);
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element);
boolean remove(Object element);
Iterator<E> iterator();
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
c.removeAll(Collections.singleton(e));
c.removeAll(Collections.singleton(null));
Object[] a = c.toArray();
String[] a = c.toArray(new String[0]);
Array operations
Basic operations
for - each (r)
for (Object o : collection)
System.out.println(o);
static void filter(Collection<?> c) {
for (Iterator<?> it = c.iterator(); it.hasNext(); )
if (!cond(it.next()))
it.remove();
}
Iterator (rw)
vs
Bulk operations
def
usage
def
usage
List
Overview
What's ?
Ordered collection that may contain duplicate elements
What's new?
E get(int index);
E set(int index, E element);
boolean add(E element);
void add(int index, E element);
E remove(int index);
boolean addAll(int index, Collection<? extends E> c);
Positional access
def
int indexOf(Object o);
int lastIndexOf(Object o);
Search
Range-view
Iteration
List<E> subList(int from, int to);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
public static <E> void swap(List<E> a, int i, int j) {
E tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
def
public static <E> void replace(List<E> list, E val, E newVal) {
for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
if (val == null ? it.next() == null : val.equals(it.next()))
it.set(newVal);
}
public static <E> void replace(List<E> list, E val, List<? extends E> newVals) {
for (ListIterator<E> it = list.listIterator(); it.hasNext(); ){
if (val == null ? it.next() == null : val.equals(it.next())) {
it.remove();
for (E e : newVals)
it.add(e);
}
}
}
Usage
List<String> ls = new ArrayList<String>(Arrays.asList("a","b","c"));
ListIterator<String> it = ls.listIterator(1);
it.add("e");
conversion
constructor
Collection Operations
remove
add & addAll
the first occurrence of the specified element
append at the end of the list
worries ?
the sublist is backed by the original list,
hence every change on the sublist
will be reflected on the list itself.
list.subList(fromIndex, toIndex).clear();
int i = list.subList(fromIndex, toIndex).indexOf(o);
power
def
def
Attention!
this methods rely on equals method.
Implementations
ArrayList
LinkedList
Characteristics
Constant time positional access O(1)
Linear time for adding/removing elements not at the end. O(n)
Tuning parameter for initial capacity
Best for everyday usage
Characteristics
Constant time for adding/removing elements O(1)
Linear time for positional access. O(n)
CopyOnWriteArrayList
Is an ArrayList that has synchronized mutative operations (add, set ...) and not synchronized traversals.
The iterator makes a snapshot, hence will not reflect changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported
what?
So?
When?
Well suited to maintaining event-handler lists, where you need sync but only on the mutative operations
Set
What's ?
A collection with no duplicates
What's new?
Nada, only stronger accent on equals() and hascode() methods of the set's elements.
Concept proof
List<String> ls = new ArrayList<String>(Arrays.asList("a","a","c"));
System.out.println(ls);

Set<String> set = new HashSet<String>(ls);
System.out.println(set);
[a, a, c]
[c, a]
Overview
Implementations
HashSet
TreeSet
LinkedHashSet
Stores elements in an hashtable
Uses an hashing function, hence stored elements must override hashCode()
Function example: 10(table size) % el.hashCode()
No ordering garantees
Constant time for mutative operations and get. O(1)
Tuning using load factor and initial capacity
Characteristics
Stores its elements in a red-black tree
Orders its elements based on their value
Log-time for most of the operations
Elements should implement Comparable in order
to benefit from SortedSet interface
A Hashset with a linked list running through it,
thus it preserves insertion order
Elements must override hashCode()
Similar performance with HashSet, but slower
EnumSet
High-performance Set implementation for enum types
All of the members of an enum set must be of the same enum type.
Rich, typesafe replacement for traditional bit flags
CopyOnWriteArraySet
Equivalent of CopyOnWriteArrayList
Map
What's ?
A collection maps keys to values.
A map cannot contain duplicate keys
Each key can map to at most one value.
Overview
HashMap
TreeMap
LinkedHashMap
Stores elements in an hashtable
Uses an hashing function, hence stored elements must override hashCode()
Function example: 10(table size) % el.hashCode()
No ordering garantees
Constant time for mutative operations and get. O(1)
Tuning using load factor and initial capacity
Characteristics
Stores its elements in a red-black tree
Orders its elements based on their value
Log-time for most of the operations
Elements should implement Comparable in order
to benefit from SortedMap interface
A Hashmap with a linked list running through it,
thus it preserves insertion order
Elements must override hashCode()
Similar performance with HashMap, but slower
EnumMap
High-performance Map implementation for mapping enum types to values
All of the keys of an enum map must be of the same enum type.
IdentityHashMap
uses == instead of equals
V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean contains Key(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
Basic operations
Bulk operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
static <K, V> Map<K, V> newAttributeMap(Map<K, V>defaults, Map<K, V> overrides) {
Map<K, V> result = new HashMap<K, V>(defaults);
result.putAll(overrides);
return result;
}
def
caution
Override equals and hashCode
Collection Views
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();
for (Map.Entry<KeyType, ValType> e : m.entrySet())
System.out.println(e.getKey() + ": " + e.getValue());
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
if (it.next().isBogus())
it.remove();
Iterating
def
Caution
You can only remove elements, no adding allowed
power
Set<Employee> simpleEmp = new HashSet<Employee>(managers.keySet());
simpleEmp.removeAll(managers.values());
m1.entrySet().removeAll(m2.entrySet());
Implementations
WeakHashMap
stores only weak references to its keys
It is useful for implementing "registry-like" data structures
reduced memory footprint in time, because they are better garbage-collected
ConcurentHashMap
highly concurrent, high-performance implementation backed up by a hash table
Queue
Overview
What's ?
Ordered collection that has support for FIFO and priority queues
What's new?
Implementations
- queue implementation backed by a list

- a priority queue based on the heap data structure. Priority decided by element's natural order or provided Comparator.

— an optionally bounded FIFO blocking queue backed by linked nodes

— a bounded FIFO blocking queue backed by an array

— an unbounded blocking priority queue backed by a heap

— a time-based scheduling queue backed by a heap

— a simple rendezvous mechanism that uses the BlockingQueue interface
LinkedList
PriorityQueue
LinkedBlockingQueue
ArrayBlockingQueue
PriorityBlockingQueue
DelayQueue
SynchronousQueue
Deque
Overview
What's ?
Ordered collection that has support for FIFO and LIFO
What's new?
Implementations
- deque implementation backed by a list

- is the resizable array implementation. It's more
efficient than the LinkedList version

—is the concurrent implementation of the Deque interface
LinkedList
ArrayDeque
LinkedBlockingDeque
Usually pronounced as deck, a deque is a double-ended-queue
public class Countdown {
public static void main(String[] args) throws InterruptedException {
int time = Integer.parseInt(args[0]);
Queue<Integer> queue = new LinkedList<Integer>();

for (int i = time; i >= 0; i--)
queue.add(i);

while (!queue.isEmpty()) {
System.out.println(queue.remove());
Thread.sleep(1000);
}
}
}
Algorithms
Sorting
is fast
is stable
as fast as a highly optimized quicksort. O(n log(n))
doesn't reorder equal elements
Collections.sort(list);
Collections.sort(winners, new Comparator<List<String>>() {
public int compare(List<String> o1, List<String> o2) {
return o2.size() - o1.size();
}});
Shuffling
does the opposite of what sort does
Collections.shuffle(list);
Collections.shuffle(list, new Random());
def
Data manipulation
— reverses the order of the elements in a List.

— rotates all the elements in a List by a specified distance.

— swaps the elements at specified positions in a List.

— replaces all occurrences of one specified value with another.

— adds all the specified elements to a Collection. The elements to be added may be specified individually or as an array.

— overwrites every element in a List with the specified value.

— copies the source List into the destination List.
rotate
swap
replaceAll
addAll
fill
copy
reverse
Searching
int pos = Collections.binarySearch(list, key);
binarySearch
indexOfSubList
lastIndexOfSubList
— returns the index of the first sublist of one List that is equal to another.

— returns the index of the last sublist of one List that is equal to another.
Composition
— counts the number of times the specified element occurs in the specified collection

— determines whether two Collections are disjoint; that is, whether they contain no elements in common
frequency
disjoint
min & max
- return the min/max value in the list. May use natural order or a provided one with Comparator
Georgian Parvu
Q&A
Final overview
Full transcript