ArrayList内部采用数组实现,随机存取效率高O(1),删除的效率就低O(N)。数组实现会保持插入的顺序,而且允许重复元素。
LinkedList内部采用引用实现(对应C,C++中的链表),查询的效率偏低O(N),但是适合插入和删除频繁的集合数据O(1)。
HashSet内部采用HashMap实现。因为使用Hash存取,所以不维护插入的顺序且不允许重复元素。
TreeSet内部采用TreeMap实现
HashMap采用数组实现,数组中的每个元素是一个链表,元素的存取都是先计算Hash值,根据Hash值得到其在那个链表之中。然后在
链表中依次进行比较。与Hashtable相比,Hashtable是线程安全且不允许null的key和value。
下面是HashMap的get方法:
public V get(Object key) {
Object k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry<K,V> e = table[i];
while (true) {
if (e == null)
return null;
if (e.hash == hash && eq(k, e.key))
return e.value;
e = e.next;
}
}
Hash方法总体的效率都很高,包括插入、删除和查询O(1)。
TreeMap采用的是red-black tree来实现。TreeMap对key值进行排序,并且维护tree的balance,所以插入和删除的效率偏低O(logN)。
下面是怎么选择集合类的一个总结:
To close this chapter, let's take a quick look at some deciding factors in how to pick which standard collection implementation to use. These are not meant to be hard and fast rules but rather general guidelines to help you along.
1.If you need to store primitive elements, you must use an array unless you want to place every item into a wrapper class like Integer or Float. Consider using a BitSet instead of an array of booleans.
2.Rarely, if ever, should you use an historical collection class like Hashtable or Vector. Sometimes you need to use a Properties object, which is a type of Hashtable. Unless explicitly called for-as when using the JavaMail API-the historical collection class should be avoided in favor of the newer framework implementations.
3.Use a List if you need ordered access. Pick an ArrayList for indexed access. Definitely use a LinkedList when you need to add and remove elements from the beginning or middle of the list. If you only need ordered access through an Iterator, believe it or not, LinkedList is actually faster. Lists are also good if your collection requires the storing of duplicates, triplicates, or more.
4.Sets are for storing unique items in a collection. If you need ordered access, use a TreeSet. Otherwise, use a HashSet. If you only need ordered access after all the elements have been added, consider creating the set with a HashSet, then copying all the elements into a TreeSet.
5.Use a Map if you need to store key?value pairs and the key isn't an integer. (Consider using an array or List for indexed access.) Like Set, you should always use the hashed version of the collection (HashMap) unless you need sorted access (TreeMap).
6.Rely on the Collections class to make collections and maps read-only and thread-safe.
7.Use the WeakHashMap if you need to maintain weak references to keys stored in the map.