Which Collection should I use in my Java program? Hashtable vs hashmap? vectors vs hashtable? Hashmap vs hashset? Hashtable Vs Two Dimensional Array? ArrayList vs. Vector? Again hashmap vs hashtable? hashmap vs arraylist? More? I compared all the collections in my table below! Oooh...
All the these questions I asked myself at least 10 times, if not even more.
And I have not found any good Java Collections overview page on the Internet,
where I could pick one collection and compare with another in one page, without
going to multiple places.
This Comprehensive Java Collections overview page was the result of my
half-day work. I think that the info I have now in two tables below can be good
enough to make fast and right choice when you do not know which Java collection
can be used in your application.
I hope that I have not done serious mistakes, if you find them, please inform
me and I will correct the page. At the bottom of tables you can find Java code
examples for all the collections described below.
General-purpose
Implementations
| Interfaces |
Implementations |
| |
Hash table |
Resizable array |
Tree |
Linked list |
Hash table + Linked list |
Set |
HashSet |
|
TreeSet |
|
LinkedHashSet |
List |
|
ArrayListVector |
|
LinkedList |
|
Queue |
|
|
|
|
|
Map |
HashMapHashtable
|
|
TreeMap |
|
LinkedHashMap |
|
http://JavaFAQ.nu |
Set: A collection that contains no duplicate elements. More formally, sets
contain no pair of elements e1 and e2 such that
e1.equals(e2), and at most one null element. As implied by its name, this
interface models the mathematical set abstraction.
Map: cannot contain duplicate keys; each key can map to at most one value.
The Map interface provides three
collection views, which allow a map's contents to be viewed as a set of
keys, collection of values, or set of key-value mappings. The order of a
map is defined as the order in which the iterators on the map's collection views
return their elements. Some map implementations, like the TreeMap
class, make specific guarantees as to their order; others, like the HashMap
class, do not.
46 Java Free lessons course on
our site!
|
Important! Although Array is not class in Java
API, I have included it into the table below, because it is similar to
collections in terms of storage. It can be used as a simplest "collection type"
 .
That's why some functions and properties are not applicable to Array
in the table below (marked as N/A).
Java Collections Comprehensive Overview Table, Part 1
| |
HashSet |
HashMap |
ArrayList |
TreeSet |
TreeMap |
LinkedList |
LinkedHashSet |
LinkedHashMap |
Random
access |
no |
yes |
yes |
no |
yes |
yes |
no |
yes |
| Serializable |
yes |
yes |
yes |
yes |
yes |
yes |
yes |
yes |
| Synchronized |
no |
no |
no |
no |
no |
no |
no |
no |
| guarantees to the iteration order |
no |
no |
yes |
yes, |
yes |
yes |
yes |
yes |
| constant order over time |
no |
no |
yes,
see note 6 |
yes,
see note 7 |
yes,
see note 7 |
yes |
yes |
yes |
| permits null element |
yes |
yes,
null key,
null value |
yes |
no |
no |
yes |
yes |
yes |
is iteration
time proportional to size?**** |
yes note 1 |
yes |
almost,
see note 6 |
no,
log(n) |
no,
log(n) |
2n,
see note 8 |
yes,
just slightly below that of HashSet |
yes |
| Is fail-fast? note 2 |
yes |
yes |
yes |
yes |
yes |
yes |
yes |
yes |
| is resizable? |
yes |
yes |
yes |
yes |
yes |
yes |
yes |
|
Only unique elements
(no duplicates)?
|
yes |
yes |
no,
allow duplicate elements |
yes |
yes |
no |
yes |
yes |
| Notes |
|
The HashMap class is roughly equivalent to
Hashtable, except that it is unsynchronized and permits nulls. |
This class is roughly equivalent to Vector,
except that it is unsynchronized. |
|
|
Implements all optional list operations.
Implements the Queue interface, providing first-in-first-out queue
operations for add, poll, etc.
- FIFO semantics |
LinkedHashSet: Hash table and linked list implementation
of the Set interface, with predictable iteration order. This
implementation differs from HashSet in that it maintains a
doubly-linked list running through all of its entries. This linked list
defines the iteration ordering, which is the order in which elements were
inserted into the set (insertion-order). Note that insertion order is
not affected if an element is re-inserted into the set. |
LinkedHashMap: Hash table and linked list implementation
of the Map interface, with predictable iteration order. This
implementation differs from HashMap in that it maintains a
doubly-linked list running through all of its entries. This linked list
defines the iteration ordering, which is normally the order in which keys
were inserted into the map (insertion-order). Note that insertion
order is not affected if a key is re-inserted into the map. |
Since Java
version |
1.2 |
1.2 |
1.2 |
1.2 |
1.2 |
1.2 |
1.4 |
1.4 |
| Java Code Examples |
code examples for
HashSet |
code examples for
HashMap |
code examples for
ArrayList |
code examples for
TreeSet |
code examples for
TreeMap |
code examples for
LinkedList |
code examples for
LinkedHashSet |
code examples for
LinkedHashMap |
| Always visit
http://JavaFAQ.nu when you need more info about Java! |
To be continued
Part 2. Java Collections Comprehensive Overview Table (continuation).
| |
Vector |
Hashtable |
PriorityQueue |
WeakHashMap |
Array |
Random
access |
yes |
yes |
no |
no |
yes |
| Serializable |
yes |
yes |
yes |
no!!! |
note 3 |
| Synchronized |
yes |
yes |
no |
no |
N/A |
| guarantees to the iteration order |
yes |
yes |
yes, look at note 5 below |
no |
yes |
| constant order over time |
yes |
yes |
yes |
no |
yes |
| permits null element |
|
no |
no |
yes, both keys and values |
not |
is iteration
time proportional to size? note 4 |
yes |
yes |
depends on operation,
see note 5 |
yes |
yes |
| Is fail-fast? note 2 |
yes |
yes |
?? |
yes |
|
| is resizable? |
yes |
yes |
yes |
yes |
no |
Only unique elements
(no duplicates)? |
yes |
yes keys must be unique, values not |
yes |
yes |
no |
| Notes |
|
|
PriorityQueue orders its elements according
to their values. |
A hashtable-based Map implementation with
weak keys. An entry in a WeakHashMap will automatically be
removed when its key is no longer in ordinary use. More precisely, the
presence of a mapping for a given key will not prevent the key from being
discarded by the garbage collector, that is, made finalizable, finalized,
and then reclaimed. When a key has been discarded its entry is effectively
removed from the map, so this class behaves somewhat differently than other
Map implementations. This class is intended primarily for use
with key objects whose equals methods test for object identity
using the == operator. Once such a key is discarded it can never be
recreated, so it is impossible to do a lookup of that key in a
WeakHashMap at some later time and be surprised that its entry has been
removed. This class will work perfectly well with key objects whose
equals methods are not based upon object identity, such as String
instances. With such recreatable key objects, however, the automatic removal
of WeakHashMap entries whose keys have been discarded may prove to
be confusing. |
|
Since Java
version |
1.0 |
1.0 |
1.5 |
1.2 |
1.0 |
| Java Code Examples |
code examples for
Vector |
code examples for
Hashtable |
code examples for
PriorityQueue |
code examples for
WeakHashMap |
code examples forArray |
|
http://JavaFAQ.nu |
In general, it is good API design practice not to make users pay for a
feature they don't use. Furthermore, unnecessary synchronization can result in
deadlock under certain circumstances.
Note 1 - Iterating over this set requires time proportional to the sum of the
HashSet instance's size (the number of elements) plus the "capacity" of the
backing HashMap instance (the number of buckets). Thus, it's very
important not to set the initial capacity too high (or the load factor too low)
if iteration performance is important.
Note 2 - Look at the fail-fast tip
Note 3 An array is Serializable if
component type is Serializable
Note 4 If iteration performance is
important and if iterating requires time
proportional to the sum of a collection instance's size, it's very important not
to set the initial capacity too high (or the load factor too low).
Note 5 (PriorityQueue): It orders
elements according to an order specified at construction time, which is
specified either according to their natural order (see Comparable), or according
to a Comparator, depending on which constructor is used. A priority queue does
not permit null elements. A priority queue relying on natural ordering also does
not permit insertion of non-comparable objects (doing so may result in
ClassCastException).
Implementation note: this implementation provides
O(log(n)) time for the insertion methods (offer, poll,
remove() and add) methods; linear time for the remove(Object)
and contains(Object) methods; and constant time for the retrieval
methods (peek, element, and size).
Note 6: The size, isEmpty, get, set,
iterator, and listIterator operations run in constant time. The
add operation runs in amortized constant time, that is, adding n
elements requires O(n) time. All of the other operations run in linear time
(roughly speaking).
An ordered collection (also known as a sequence).
The user of this interface has precise control over where in the list each
element is inserted. The user can access elements by their integer index
(position in the list), and search for elements in the list.
Note 7: TreeSet class guarantees that the sorted set will be in
ascending element order, sorted according to the natural order of the
elements (see Comparable), or by the comparator provided at set
creation time, depending on which constructor is used.
Note 8: All of the operations perform as could be expected for a
doubly-linked list. Operations that index into the list will traverse the list
from the beginning or the end, whichever is closer to the specified index.
Copyright by JavaFAQ.nu, Alexandre Patchine, 2006
23716 bytes more | 1 comment |   | Score: 4
|
Previous
1060 Stories (530 Pages, 2 Per Page)
Next
RSS feed Java Forums
