JavaCollections

	contains/ containsKey	get	set/ put	add	remove	size	iteration
ConcurrentSkipListMap	log(n)	log(n)	log(n)		log(n)	n	n
HashMap ConcurrentHashMap Hashtable	1	1	1		1	1	n (of capacity, not size)
LinkedHashMap	1	1	1		1	1	n (of size, not capacity)
TreeMap	log(n)	log(n)	log(n)		log(n)	1	n
ArrayList	n	1	1	1 (amortized constant time)?	n	1	n
LinkedList	n	n	n	1	n (removal is 1 at either end of the list)	1	n

contains/ containsKey

get|set/ put

add

remove

size

iteration

ConcurrentSkipListMap|log(n)|log(n)|log(n)| |log(n)|n|n HashMap
ConcurrentHashMap
Hashtable|1|1|1| |1|1|n (of capacity, not size) LinkedHashMap|1|1|1| |1|1|n (of size, not capacity) TreeMap|log(n)|log(n)|log(n)| |log(n)|1|n ArrayList|n|1|1|1 (amortized
constant time)?|n|1|n LinkedList|n|n|n|1|n (removal is 1 at
either end of
the list)|1|n

TODO:

• Add more collection types.
• Add memory usage of each.
• Split into one table for lists and one for maps.