A few minor details.
Hashtable is supposed to perform slower than HashMap. Maybe because is synchronized by default. You should use HashMap because is the newest class. [...]
IMNSHO, I'd put this a bit more strongly: never, ever, use Hashtable (or Vector) if you don't absolutely have to.
The Collections classes form a logical, systematic framework of interfaces and implementations. Vector, Hashtable and Enumeration fall completely outside this framework and do nothing that the framework classes don't do. They are unnecessary baggage, so much extra stuff to remember without benefit.Retrofitting them with the Collections interfaces has made their APIs bloated and inconsistent. What shall I use today, v.iterator() or v.elements()? If you use them in a multi-developer project, inconsistencies will happen.If your code is single-threaded, the synchronization in Vector and friends does nothing for you and just decreases performance.If your code is multi-threaded... the sychronization in Vector and friends still does nothing for you and just decreases performance! You see, most of the time their synchronization is at the wrong level; most of the time, you have composite operations which need to be atomic w.r.t. other threads rather than the little Vector and Hashtable methods.Worse, the synchronization in Vector and Hashtable is likely to lure developers inexperienced in concurrent programming into a false sense of security. "I'm using a threadsafe collection, so my code is threadsafe". D'oh. That's not how it works. As a consequence, code using Vector and Hashtable is in my experience more likely to be thread-unsafe than code using the Collections framework.I know many, many developers still use them, and to me it is a complete mystery why.
A linkedList performs better than an arrayList if frequent insertions and removals are required. Otherwise use the latter because is faster.
In addition to the things you mentioned, a LinkedList is very bad at finding an arbitrary element in the middle of the list (i.e. list.get(i)). An ArrayList, on the other hand, is good at inserting or deleting elements at the end of the list but very bad at doing this anywhere else in the list.
These performance characteristics are often denoted using the big-O notation. This notation tells you how execution time grows as the number of elements (N) in the collection grows. For example, list.get(i) performs O(N) for LinkedList but O(1) for ArrayList, except when i is the start or the end of the list. In other words, for a LinkedList, if the list gets twice as large then list.get(i) will take twice as long on average; for an ArrayList, it the list size won't make any difference whatsoever.
a) a linkedList can provide a ListIterator.
So can an ArrayList; in fact, so should any implementation of the List interface, since it is part of the List API.
As per api for HashMap it says "
"Hash table based implementation of the Map interface"
Similarly for HashSet it says
"This class implements the Set interface, backed by a hash table (actually a HashMap instance). "
What is the implication of these statements ?
The implications are for performance and ordering. See below. The second statement essentially says that a HashSet will have the same characteristics as a HashMap.
I forgot to add this.. what is the difference between Set and HashSet? Both of them implement the Set interface.
HashSet is an implementation of the Set interface that uses a hash table behind the scenes. This has implications for the kinds of objects you can store and for its performance.
The objects you store must have correctly working, consistent hashCode() and equals() implementations, otherwise things go badly wrong. See the javadoc for java.lang.Object for more information about this.
The performance is O(1) for most operations, which means that the time taken to store a new object in the Set, or to check whether the Set contains a specific object, is more or less constant.
This is significantly better than say, a TreeSet, which has a performance that decreases logarithmically with the number of objects held (O(log(N)) performance). Why would you ever use a TreeSet then? Well, when you iterate over a HashSet you get the elements in an essentially random order which may change every time you modify the set. A TreeSet maintains its elements in sorted order.
Although not strictly exam material, it extremely useful to be aware of the performance characteristics of the Collection implementation classes. The resources linked to in the previous response are very good sources of information.
- Peter
[ January 11, 2003: Message edited by: Peter den Haan ]
