使用 L i s t s
List（接口） 順序是 List 最重要的特性；它可保證元素按照規定的順序排列。 List 為 Collection 添加了大量方法，以便我們在 List 中部插入和刪除元素（只推薦對 LinkedList 這樣做）。 List 也會生成一個ListIterator（列表反覆器），利用它可在一個列表裡朝兩個方向遍歷，同時插入和刪除位於列表中部的元素（同樣地，只建議對 LinkedList 這樣做）
ArrayList 由一個數組後推得到的 List。作為一個常規用途的對象容器使用，用於替換原先的 Vector。允許我們快速訪問元素，但在從列表中部插入和刪除元素時，速度卻嫌稍慢。一般只應該用ListIterator 對一個 ArrayList 進行向前和向後遍歷，不要用它刪除和插入元素；與 LinkedList 相比，它的效率要低許多LinkedList 提供優化的順序訪問性能，同時可以高效率地在列表中部進行插入和刪除操作。但在進行隨機訪問時，速度卻相當慢，此時應換用 ArrayList。
也提供了 addFirst()， addLast()， getFirst()，getLast()， removeFirst() 以及 removeLast()（未在任何接口或基礎類中定義），以便將其作為一個規格、隊列以及一個雙向隊列使用
public class List1 {
// Wrap Collection1.fill() for convenience:
public static List fill(List a) {
return (List) Collection1.fill(a);
}
// You can use an Iterator, just as with a
// Collection, but you can also use random
// access with get():
public static void print(List a) {
for (int i = 0; i < a.size(); i++)
System.out.print(a.get(i) + " ");
System.out.println();
}
static boolean b;
static Object o;
static int i;
static Iterator it;
static ListIterator lit;
public static void basicTest(List a) {
a.add(1, "x"); // Add at location 1
a.add("x"); // Add at end
// Add a collection:
a.addAll(fill(new ArrayList()));
// Add a collection starting at location 3:
a.addAll(3, fill(new ArrayList()));
b = a.contains("1"); // Is it in there?
// Is the entire collection in there?
b = a.containsAll(fill(new ArrayList()));
// Lists allow random access, which is cheap
// for ArrayList, expensive for LinkedList:
o = a.get(1); // Get object at location 1
i = a.indexOf("1"); // Tell index of object
// indexOf, starting search at location 2:
i = a.indexOf("1", 2);
b = a.isEmpty(); // Any elements inside?
it = a.iterator(); // Ordinary Iterator
lit = a.listIterator(); // ListIterator
lit = a.listIterator(3); // Start at loc 3
i = a.lastIndexOf("1"); // Last match
i = a.lastIndexOf("1", 2); // ...after loc 2
a.remove(1); // Remove location 1
a.remove("3"); // Remove this object
a.set(1, "y"); // Set location 1 to "y"
// Keep everything that's in the argument
// (the intersection of the two sets):
a.retainAll(fill(new ArrayList()));
// Remove elements in this range:
a.removeRange(0, 2);
// Remove everything that's in the argument:
a.removeAll(fill(new ArrayList()));
i = a.size(); // How big is it?
a.clear(); // Remove all elements
}
public static void iterMotion(List a) {
ListIterator it = a.listIterator();
b = it.hasNext();
b = it.hasPrevious();
o = it.next();
i = it.nextIndex();
o = it.previous();
i = it.previousIndex();
}
public static void iterManipulation(List a) {
ListIterator it = a.listIterator();
it.add("47");
// Must move to an element after add():
it.next();
// Remove the element that was just produced:
it.remove();
// Must move to an element after remove():
it.next();
// Change the element that was just produced:
it.set("47");
}
public static void testVisual(List a) {
print(a);
List b = new ArrayList();
fill(b);
System.out.print("b = ");
print(b);
a.addAll(b);
a.addAll(fill(new ArrayList()));
print(a);
// Shrink the list by removing all the
// elements beyond the first 1/2 of the list
System.out.println(a.size());
System.out.println(a.size() / 2);
a.removeRange(a.size() / 2, a.size() / 2 + 2);
print(a);
// Insert, remove, and replace elements
// using a ListIterator:
ListIterator x = a.listIterator(a.size() / 2);
x.add("one");
print(a);
System.out.println(x.next());
x.remove();
System.out.println(x.next());
x.set("47");
print(a);
// Traverse the list backwards:
x = a.listIterator(a.size());
while (x.hasPrevious())
System.out.print(x.previous() + " ");
System.out.println();
System.out.println("testVisual finished");
}
// There are some things that only
// LinkedLists can do:
public static void testLinkedList() {
LinkedList ll = new LinkedList();
Collection1.fill(ll, 5);
print(ll);
// Treat it like a stack, pushing:
ll.addFirst("one");
ll.addFirst("two");
print(ll);
// Like "peeking" at the top of a stack:
System.out.println(ll.getFirst());
// Like popping a stack:
System.out.println(ll.removeFirst());
System.out.println(ll.removeFirst());
// Treat it like a queue, pulling elements
// off the tail end:
System.out.println(ll.removeLast());
// With the above operations, it's a dequeue!
print(ll);
}
public static void main(String args[]) {
// Make and fill a new list each time:
basicTest(fill(new LinkedList()));
basicTest(fill(new ArrayList()));
iterMotion(fill(new LinkedList()));
iterMotion(fill(new ArrayList()));
iterManipulation(fill(new LinkedList()));
iterManipulation(fill(new ArrayList()));
testVisual(fill(new LinkedList()));
testLinkedList();
}
}
在 basicTest()和 iterMotiion() 中，只是簡單地發出調用，以便揭示出正確的語法。而且儘管捕獲了返回
值，但是並未使用它。在某些情況下，之所以不捕獲返回值，是由於它們沒有什麼特別的用處。在正式使用
它們前，應仔細研究一下自己的聯機文檔，掌握這些方法完整、正確的用法。
ArrayList使用實例
import java.awt.List;
import java.util.ArrayList;
import java.util.Iterator;
/**
* @author sihai
* @time 2018/4/19
* ArrayList用法示例說明
*
*/
public class Main {
public static void main(String[] args) {
//ArrayList用法示例
ArrayList m_ArrayList=new ArrayList();
m_ArrayList.add("Evankaka");
m_ArrayList.add("sihai");
m_ArrayList.add("德德");
m_ArrayList.add("Evankaka");
m_ArrayList.add("小紅");
m_ArrayList.set(2,"sihai2");// 將索引位置為2的對象修改
m_ArrayList.add(3,"好好學java");// 將對象添加到索引位置為3的位置
//ArrayList遍歷方法1
Iterator it_ArrayList = m_ArrayList.iterator();
System.out.println("ArrayList遍歷方法1");
while (it_ArrayList.hasNext()) {
System.out.println(it_ArrayList.next());
}
//ArrayList遍歷方法2
System.out.println("ArrayList遍歷方法2");
for(Object o:m_ArrayList){
System.out.println(o);
}
//ArrayList遍歷方法2
System.out.println("ArrayList遍歷方法3");
for(int i = 0; i輸出結果：
ArrayList遍歷方法1
Evankaka
sihai
sihai2
好好學java
Evankaka
小紅
ArrayList遍歷方法2
Evankaka
sihai
sihai2
好好學java
Evankaka
小紅
ArrayList遍歷方法3
Evankaka
sihai
sihai2
好好學java
Evankaka
小紅
ArrayList刪除元素後的遍歷
sihai
sihai2
Evankaka
小紅
ArrayList注意
（1）使用Iterator迭代集合過程中，不可修改集合元素，否則會引發異常。並且Iterator只能向後迭代
（2）如果你想在循環過程中去掉某個元素,只能調用it.remove方法, 不能使用list.remove方法, 否則一定出併發訪問的錯誤.
使用 S e t s
Set完全就是一個 Collection，只是具有不同的行為（這是實例和多形性最理想的應用：用於表達不同的行為）。在這裡，一個 Set 只允許每個對象存在一個實例（正如大家以後會看到的那樣，一個對象的“值”的構成是相當複雜的）
Set（接口） 添加到 Set 的每個元素都必須是獨一無二的；否則 Set 就不會添加重複的元素。添加到 Set 裡的對象必須定義 equals()，從而建立對象的唯一性。 Set 擁有與 Collection 完全相同的接口。一個 Set 不能保證自己可按任何特定的順序維持自己的元素
HashSet 用於除非常小的以外的所有 Set。對象也必須定義 hashCode()
ArraySet 由一個數組後推得到的 Set。面向非常小的 Set 設計，特別是那些需要頻繁創建和刪除的。對於小
TreeSet 由一個“紅黑樹”後推得到的順序 Set（註釋⑦）。這樣一來，我們就可以從一個 Set 裡提到一個
順序集合
public class Set1 {
public static void testVisual(Set a) {
Collection1.fill(a);
Collection1.fill(a);
Collection1.fill(a);
Collection1.print(a); // No duplicates!
// Add another set to this one:
a.addAll(a);
a.add("one");
a.add("one");
a.add("one");
Collection1.print(a);
// Look something up:
System.out.println("a.contains("one"): " + a.contains("one"));
}
public static void main(String[] args) {
testVisual(new HashSet());
testVisual(new TreeSet());
}
}
重複的值被添加到 Set，但在打印的時候，我們會發現 Set 只接受每個值的一個實例。運行這個程序時，會注意到由 HashSet 維持的順序與 ArraySet 是不同的。這是由於它們採用了不同的方法來保存元素，以便它們以後的定位。 ArraySet 保持著它們的順序狀態，而 HashSet 使用一個散列函數，這是特別為快速檢索設計的）。
class MyType implements Comparable {
private int i;
public MyType(int n) {
i = n;
}
public boolean equals(Object o) {
return (o instanceof MyType) && (i == ((MyType) o).i);
}
public int hashCode() {
return i;
}
public String toString() {
return i + " ";
}
public int compareTo(Object o) {
int i2 = ((MyType) o).i;
return (i2 < i ? -1 : (i2 == i ? 0 : 1));
}
}
public class Set2 {
public static Set fill(Set a, int size) {
for (int i = 0; i < size; i++)
a.add(new MyType(i));
return a;
}
public static Set fill(Set a) {
return fill(a, 10);
}
public static void test(Set a) {
fill(a);
fill(a); // Try to add duplicates
fill(a);
a.addAll(fill(new TreeSet()));
System.out.println(a);
}
public static void main(String[] args) {
test(new HashSet());
test(new TreeSet());
}
}
但只有要把類置入一個 HashSet 的前提下，才有必要使用 hashCode()—— 這種情況是完全有可能的，因為通常應先選擇作為一個 Set 實現。
使用 M a p s
Map（接口） 維持“鍵－值”對應關係（對），以便通過一個鍵查找相應的值
HashMap 基於一個散列表實現（用它代替 Hashtable）。針對“鍵－值”對的插入和檢索，這種形式具有最穩定的性能。可通過構建器對這一性能進行調整，以便設置散列表的“能力”和“裝載因子”
ArrayMap 由一個 ArrayList 後推得到的 Map。對反覆的順序提供了精確的控制。面向非常小的 Map 設計，特別是那些需要經常創建和刪除的。對於非常小的Map，創建和反覆所付出的代價要比
HashMap 低得多。但在Map 變大以後，性能也會相應地大幅度降低
TreeMap 在一個“紅－黑”樹的基礎上實現。查看鍵或者“鍵－值”對時，它們會按固定的順序排列（取決於 Comparable 或 Comparator，稍後即會講到）。 TreeMap 最大的好處就是我們得到的是已排好序的結果。TreeMap 是含有 subMap()方法的唯一一種 Map，利用它可以返回樹的一部分
public class Map1 {
public final static String[][] testData1 = {
{ "Happy", "Cheerful disposition" },
{ "Sleepy", "Prefers dark, quiet places" },
{ "Grumpy", "Needs to work on attitude" },
{ "Doc", "Fantasizes about advanced degree" },
{ "Dopey", "'A' for effort" },
{ "Sneezy", "Struggles with allergies" },
{ "Bashful", "Needs self-esteem workshop" }, };
public final static String[][] testData2 = {
{ "Belligerent", "Disruptive influence" },
{ "Lazy", "Motivational problems" },
{ "Comatose", "Excellent behavior" } };
public static Map fill(Map m, Object[][] o) {
for (int i = 0; i < o.length; i++)
m.put(o[i][0], o[i][1]);
return m;
}
// Producing a Set of the keys:
public static void printKeys(Map m) {
System.out.print("Size = " + m.size() + ", ");
System.out.print("Keys: ");
Collection1.print(m.keySet());
}
// Producing a Collection of the values:
public static void printValues(Map m) {
System.out.print("Values: ");
Collection1.print(m.values());
}
// Iterating through Map.Entry objects (pairs):
public static void print(Map m) {
Collection entries = m.entries();
Iterator it = entries.iterator();
while (it.hasNext()) {
Map.Entry e = (Map.Entry) it.next();
System.out.println("Key = " + e.getKey() + ", Value = "
+ e.getValue());
}
}
public static void test(Map m) {
fill(m, testData1);
// Map has 'Set' behavior for keys:
fill(m, testData1);
printKeys(m);
printValues(m);
print(m);
String key = testData1[4][0];
String value = testData1[4][1];
System.out.println("m.containsKey("" + key + ""): "
+ m.containsKey(key));
System.out.println("m.get("" + key + ""): " + m.get(key));
System.out.println("m.containsValue("" + value + ""): "
+ m.containsValue(value));
Map m2 = fill(new TreeMap(), testData2);
m.putAll(m2);
printKeys(m);
m.remove(testData2[0][0]);
printKeys(m);
m.clear();
System.out.println("m.isEmpty(): " + m.isEmpty());
fill(m, testData1);
// Operations on the Set change the Map:
m.keySet().removeAll(m.keySet());
System.out.println("m.isEmpty(): " + m.isEmpty());
}
public static void main(String args[]) {
System.out.println("Testing HashMap");
test(new HashMap());
System.out.println("Testing TreeMap");
test(new TreeMap());
}
}
遍歷map實例
package com.test;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Test {
public static void main(String[] args) {
Map map = new HashMap();
map.put("first", "linlin");
map.put("second", "好好學java");
map.put("third", "sihai");
map.put("first", "sihai2");
// 第一種：通過Map.keySet遍歷key和value
System.out.println("===================通過Map.keySet遍歷key和value:===================");
for (String key : map.keySet()) {
System.out.println("key= " + key + " and value= " + map.get(key));
}
// 第二種：通過Map.entrySet使用iterator遍歷key和value
System.out.println("===================通過Map.entrySet使用iterator遍歷key和value:===================");
Iterator> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= "
+ entry.getValue());
}
// 第三種：通過Map.entrySet遍歷key和value
System.out.println("===================通過Map.entrySet遍歷key和value:===================");
for (Map.Entry entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= "
+ entry.getValue());
}
// 第四種：通過Map.values()遍歷所有的value，但是不能遍歷鍵key
System.out.println("===================通過Map.values()遍歷所有的value:===================");
for (String v : map.values()) {
System.out.println("value= " + v);
}
}
}
輸出結果如下：
===================通過Map.keySet遍歷key和value:===================
key= third and value= sihai
key= first and value= sihai2
key= second and value= 好好學java
===================通過Map.entrySet使用iterator遍歷key和value:===================
key= third and value= sihai
key= first and value= sihai2
key= second and value= 好好學java
===================通過Map.entrySet遍歷key和value:===================
key= third and value= sihai
key= first and value= sihai2
key= second and value= 好好學java
===================通過Map.values()遍歷所有的value:===================
value= sihai
value= sihai2
value= 好好學java
決定使用哪種集合
ArrayList， LinkedList 以及 Vector（大致等價於 ArrayList）都實現了List 接口，所以無論選用哪一個，我們的程序都會得到類似的結果。然而， ArrayList（以及 Vector）是由一個數組後推得到的；而 LinkedList 是根據常規的雙重鏈接列表方式實現的，因為每個單獨的對象都包含了數據以及指向列表內前後元素的句柄。正是由於這個原因，假如想在一個列表中部進行大量插入和刪除操作，那麼 LinkedList 無疑是最恰當的選擇（ LinkedList 還有一些額外的功能，建立於AbstractSequentialList 中）。若非如此，就情願選擇 ArrayList，它的速度可能要快一些。
作為另一個例子， Set 既可作為一個 ArraySet 實現，亦可作為 HashSet 實現。 ArraySet 是由一個 ArrayList
後推得到的，設計成只支持少量元素，特別適合要求創建和刪除大量 Set 對象的場合使用。然而，一旦需要在自己的 Set 中容納大量元素， ArraySet 的性能就會大打折扣。寫一個需要 Set 的程序時，應默認選擇HashSet。而且只有在某些特殊情況下（對性能的提升有迫切的需求），才應切換到 ArraySet。
1. 決定使用何種 List
為體會各種 List 實施方案間的差異，最簡便的方法就是進行一次性能測驗。
public class ListPerformance {
private static final int REPS = 100;
private abstract static class Tester {
String name;
int size; // Test quantity
Tester(String name, int size) {
this.name = name;
this.size = size;
}
abstract void test(List a);
}
private static Tester[] tests = { new Tester("get", 300) {
void test(List a) {
for (int i = 0; i < REPS; i++) {
for (int j = 0; j < a.size(); j++)
a.get(j);
}
}
}, new Tester("iteration", 300) {
void test(List a) {
for (int i = 0; i < REPS; i++) {
Iterator it = a.iterator();
while (it.hasNext())
it.next();
}
}
}, new Tester("insert", 1000) {
void test(List a) {
int half = a.size() / 2;
String s = "test";
ListIterator it = a.listIterator(half);
for (int i = 0; i < size * 10; i++)
it.add(s);
}
}, new Tester("remove", 5000) {
void test(List a) {
ListIterator it = a.listIterator(3);
while (it.hasNext()) {
it.next();
it.remove();
}
}
}, };
public static void test(List a) {
// A trick to print out the class name:
System.out.println("Testing " + a.getClass().getName());
for (int i = 0; i < tests.length; i++) {
Collection1.fill(a, tests[i].size);
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(a);
long t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
}
}
public static void main(String[] args) {
test(new ArrayList());
test(new LinkedList());
}
}
內部類 Tester 是一個抽象類，用於為特定的測試提供一個基礎類。它包含了一個要在測試開始時打印的字串、一個用於計算測試次數或元素數量的 size 參數、用於初始化字段的一個構建器以及一個抽象方法test()。 test()做的是最實際的測試工作。各種類型的測試都集中到一個地方： tests 數組。我們用繼承於Tester 的不同匿名內部類來初始化該數組。為添加或刪除一個測試項目，只需在數組裡簡單地添加或移去一個內部類定義即可，其他所有工作都是自動進行的。
Type Get Iteration Insert Remove
A r r a y L i s t 110 490 3790 8730
LinkedList 1980 220 110 110
在 ArrayList 中進行隨機訪問（即 get()）以及循環反覆是最划得來的；但對於 LinkedList 卻是一個不小的開銷。但另一方面，在列表中部進行插入和刪除操作對於 LinkedList 來說卻比 ArrayList 划算得多。我們最好的做法也許是先選擇一個 ArrayList 作為自己的默認起點。以後若發現由於大量的插入和刪除造成了性能的降低，再考慮換成 LinkedList 不遲。
2. 決定使用何種 Set
可在 ArraySet 以及 HashSet 間作出選擇，具體取決於 Set 的大小（如果需要從一個 Set 中獲得一個順序列表，請用 TreeSet；）
public class SetPerformance {
private static final int REPS = 200;
private abstract static class Tester {
String name;
Tester(String name) {
this.name = name;
}
abstract void test(Set s, int size);
}
private static Tester[] tests = { new Tester("add") {
void test(Set s, int size) {
for (int i = 0; i < REPS; i++) {
s.clear();
Collection1.fill(s, size);
}
}
}, new Tester("contains") {
void test(Set s, int size) {
for (int i = 0; i < REPS; i++)
for (int j = 0; j < size; j++)
s.contains(Integer.toString(j));
}
}, new Tester("iteration") {
void test(Set s, int size) {
for (int i = 0; i < REPS * 10; i++) {
Iterator it = s.iterator();
while (it.hasNext())
it.next();
}
}
}, };
public static void test(Set s, int size) {
// A trick to print out the class name:
System.out.println("Testing " + s.getClass().getName() + " size "
+ size);
Collection1.fill(s, size);
for (int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(s, size);
long t2 = System.currentTimeMillis();
System.out.println(": " + ((double) (t2 - t1) / (double) size));
}
}
public static void main(String[] args) {
// Small:
test(new TreeSet(), 10);
test(new HashSet(), 10);
// Medium:
test(new TreeSet(), 100);
test(new HashSet(), 100);
// Large:
test(new HashSet(), 1000);
test(new TreeSet(), 1000);
}
}
進行 add()以及 contains()操作時， HashSet 顯然要比 ArraySet 出色得多，而且性能明顯與元素的多寡關係不大。一般編寫程序的時候，幾乎永遠用不著使用 ArraySet
3.決定使用何種 Map
選擇不同的 Map 實施方案時，注意 Map 的大小對於性能的影響是最大的，下面這個測試程序清楚地闡示了這
一點：
public class MapPerformance {
private static final int REPS = 200;
public static Map fill(Map m, int size) {
for (int i = 0; i < size; i++) {
String x = Integer.toString(i);
m.put(x, x);
}
return m;
}
private abstract static class Tester {
String name;
Tester(String name) {
this.name = name;
}
abstract void test(Map m, int size);
}
private static Tester[] tests = { new Tester("put") {
void test(Map m, int size) {
for (int i = 0; i < REPS; i++) {
m.clear();
fill(m, size);
}
}
}, new Tester("get") {
void test(Map m, int size) {
for (int i = 0; i < REPS; i++)
for (int j = 0; j < size; j++)
m.get(Integer.toString(j));
}
}, new Tester("iteration") {
void test(Map m, int size) {
for (int i = 0; i < REPS * 10; i++) {
Iterator it = m.entries().iterator();
while (it.hasNext())
it.next();
}
}
}, };
public static void test(Map m, int size) {
// A trick to print out the class name:
System.out.println("Testing " + m.getClass().getName() + " size "
+ size);
fill(m, size);
for (int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis();
tests[i].test(m, size);
long t2 = System.currentTimeMillis();
System.out.println(": " + ((double) (t2 - t1) / (double) size));
}
}
public static void main(String[] args) {
// Small:
test(new Hashtable(), 10);
test(new HashMap(), 10);
test(new TreeMap(), 10);
// Medium:
test(new Hashtable(), 100);
test(new HashMap(), 100);
test(new TreeMap(), 100);
// Large:
test(new HashMap(), 1000);
test(new Hashtable(), 1000);
test(new TreeMap(), 1000);
}
}
由於 Map 的大小是最嚴重的問題，所以程序的計時測試按Map 的大小（或容量）來分割時間，以便得到令人
信服的測試結果。下面列出一系列結果（在你的機器上可能不同）：
即使大小為 10， ArrayMap 的性能也要比 HashMap 差—— 除反覆循環時以外。而在使用 Map 時，反覆的作用通常並不重要（ get()通常是我們時間花得最多的地方）。 TreeMap 提供了出色的 put()以及反覆時間，但 get()的性能並不佳。但是，我們為什麼仍然需要使用TreeMap 呢？這樣一來，我們可以不把它作為 Map 使用，而作為創建順序列表的一種途徑。一旦填充了一個 TreeMap，就可以調用 keySet()來獲得鍵的一個 Set“景象”。然後用 toArray()產生包含了那些鍵的一個數組。隨後，可用 static 方法 Array.binarySearch()快速查找排好序的數組中的內容。當然，也許只有在 HashMap 的行為不可接受的時候，才需要採用這種做法。因為HashMap 的設計宗旨就是進行快速的檢索操作。最後，當我們使用 Map 時，首要的選擇應該是 HashMap。只有在極少數情況下才需要考慮其他方法
public class MapCreation {
public static void main(String[] args) {
final long REPS = 100000;
long t1 = System.currentTimeMillis();
System.out.print("Hashtable");
for (long i = 0; i < REPS; i++)
new Hashtable();
long t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
t1 = System.currentTimeMillis();
System.out.print("TreeMap");
for (long i = 0; i < REPS; i++)
new TreeMap();
t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
t1 = System.currentTimeMillis();
System.out.print("HashMap");
for (long i = 0; i < REPS; i++)
new HashMap();
t2 = System.currentTimeMillis();
System.out.println(": " + (t2 - t1));
}
}
TreeMap 的創建速度比其他兩種類型明顯快得多（但你應親自嘗試一下，因為據說新版本可能會改善 ArrayMap 的性能）。考慮到這方面的原因，同時由於前述 TreeMap 出色的 put()性能，所以如
果需要創建大量 Map，而且只有在以後才需要涉及大量檢索操作，那麼最佳的策略就是：創建和填充TreeMap；以後檢索量增大的時候，再將重要的 TreeMap 轉換成 HashMap—— 使用 HashMap(Map)構建器。
未支持的操作
利用 static（靜態）數組 Arrays.toList()，也許能將一個數組轉換成 List
public class Unsupported {
private static String[] s = { "one", "two", "three", "four", "five", "six",
"seven", "eight", "nine", "ten", };
static List a = Arrays.toList(s);
static List a2 = Arrays.toList(new String[] { s[3], s[4], s[5] });
public static void main(String[] args) {
Collection1.print(a); // Iteration
System.out.println("a.contains(" + s[0] + ") = " + a.contains(s[0]));
System.out.println("a.containsAll(a2) = " + a.containsAll(a2));
System.out.println("a.isEmpty() = " + a.isEmpty());
System.out.println("a.indexOf(" + s[5] + ") = " + a.indexOf(s[5]));
// Traverse backwards:
ListIterator lit = a.listIterator(a.size());
while (lit.hasPrevious())
System.out.print(lit.previous());
System.out.println();
// Set the elements to different values:
for (int i = 0; i < a.size(); i++)
a.set(i, "47");
Collection1.print(a);
// Compiles, but won't run:
lit.add("X"); // Unsupported operation
a.clear(); // Unsupported
a.add("eleven"); // Unsupported
a.addAll(a2); // Unsupported
a.retainAll(a2); // Unsupported
a.remove(s[0]); // Unsupported
a.removeAll(a2); // Unsupported
}
}
從中可以看出，實際只實現了 Collection 和 List 接口的一部分。剩餘的方法導致了不受歡迎的一種情況，名為UnsupportedOperationException。
在實現那些接口的集合類中，或者提供、或者沒有提供對那些方法的支持。若調用一個未獲支持的方法，就會導致一個 UnsupportedOperationException（操作未支持違例），這表明出現了一個編程錯誤。
Arrays.toList()產生了一個 List（列表），該列表是由一個固定長度的數組後推出來的。因此唯一能夠支持的就是那些不改變數組長度的操作。在另一方面，若請求一個新接口表達不同種類的行為（可能叫作“ FixedSizeList” —— 固定長度列表），就有遭遇更大的複雜程度的危險。這樣一來，以後試圖使用庫的時候，很快就會發現自己不知從何處下手。
對那些採用 Collection， List， Set 或者 Map 作為參數的方法，它們的文檔應當指出哪些可選的方法是必須實現的。舉個例子來說，排序要求實現 set()和 Iterator.set()方法，但不包括 add()和 remove()。
排序和搜索
數組
Arrays類為所有基本數據類型的數組提供了一個過載的 sort()和 binarySearch()，它們亦可用於 String 和Object。
public class Array1 {
static Random r = new Random();
static String ssource = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+ "abcdefghijklmnopqrstuvwxyz";
static char[] src = ssource.toCharArray();
// Create a random String
public static String randString(int length) {
char[] buf = new char[length];
int rnd;
for (int i = 0; i < length; i++) {
rnd = Math.abs(r.nextInt()) % src.length;
buf[i] = src[rnd];
}
return new String(buf);
}
// Create a random array of Strings:
public static String[] randStrings(int length, int size) {
String[] s = new String[size];
for (int i = 0; i < size; i++)
s[i] = randString(length);
return s;
}
public static void print(byte[] b) {
for (int i = 0; i < b.length; i++)
System.out.print(b[i] + " ");
System.out.println();
}
public static void print(String[] s) {
for (int i = 0; i < s.length; i++)
System.out.print(s[i] + " ");
System.out.println();
}
public static void main(String[] args) {
byte[] b = new byte[15];
r.nextBytes(b); // Fill with random bytes
print(b);
Arrays.sort(b);
print(b);
int loc = Arrays.binarySearch(b, b[10]);
System.out.println("Location of " + b[10] + " = " + loc);
// Test String sort & search:
String[] s = randStrings(4, 10);
print(s);
Arrays.sort(s);
print(s);
loc = Arrays.binarySearch(s, s[4]);
System.out.println("Location of " + s[4] + " = " + loc);
}
}
在 main()中， Random.nextBytes()
用隨機選擇的字節填充數組自變量（沒有對應的Random 方法用於創建其他基本數據類型的數組）。獲得一個數組後，便可發現為了執行 sort()或者 binarySearch()，只需發出一次方法調用即可。與 binarySearch()有關的還有一個重要的警告：若在執行一次 binarySearch()之前不調用 sort()，便會發生不可預測的行為，其中甚至包括無限循環。
對 String 的排序以及搜索是相似的，但在運行程序的時候，我們會注意到一個有趣的現象：排序遵守的是字典順序，亦即大寫字母在字符集中位於小寫字母的前面。因此，所有大寫字母都位於列表的最前面，後面再跟上小寫字母—— Z 居然位於 a 的前面。似乎連電話簿也是這樣排序的。
- 可比較與比較器
- 若想對一個 Object 數組進行排序，那麼必須解決一個問題。根據什麼來判定兩個 Object 的順序呢？不幸的是，最初的 Java 設計者並不認為這是一個重要的問題，否則就已經在根類 Object 裡定義它了。這樣造成的一個後果便是：必須從外部進行 Object 的排序，而且新的集合庫提供了實現這一操作的標準方式（最理想的是在 Object 裡定義它）。
- 針對 Object 數組（以及 String，它當然屬於 Object 的一種），可使用一個 sort()，並令其接納另一個參數：實現了 Comparator 接口（即“比較器”接口，新集合庫的一部分）的一個對象，並用它的單個compare()方法進行比較。這個方法將兩個準備比較的對象作為自己的參數使用—— 若第一個參數小於第二個，返回一個負整數；若相等，返回零；若第一個參數大於第二個，則返回正整數。基於這一規則，上述例子的 String 部分便可重新寫過，令其進行真正按字母順序的排序：
- 通過造型為 String， compare()方法會進行“暗示”性的測試，保證自己操作的只能是 String 對象—— 運期系統會捕獲任何差錯。將兩個字串都強迫換成小寫形式後， String.compareTo()方法會產生預期的結果若用自己的 Comparator 來進行一次 sort()，那麼在使用 binarySearch()時必須使用那個相同的Comparator。
- Arrays 類提供了另一個 sort()方法，它會採用單個自變量：一個 Object 數組，但沒有 Comparator。這個
- sort()方法也必須用同樣的方式來比較兩個 Object。通過實現 Comparable 接口，它採用了賦予一個類的“自然比較方法”。 這個接口含有單獨一個方法—— compareTo()，能分別根據它小於、等於或者大於自變量而返回負數、零或者正數，從而實現對象的比較。
public class CompClass implements Comparable {
private int i;
public CompClass(int ii) {
i = ii;
}
public int compareTo(Object o) {
// Implicitly tests for correct type:258
int argi = ((CompClass) o).i;
if (i == argi)
return 0;
if (i < argi)
return -1;
return 1;
}
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
public String toString() {
return i + "";
}
public static void main(String[] args) {
CompClass[] a = new CompClass[20];
for (int i = 0; i < a.length; i++)
a[i] = new CompClass((int) (Math.random() * 100));
print(a);
Arrays.sort(a);
print(a);
int loc = Arrays.binarySearch(a, a[3]);
System.out.println("Location of " + a[3] + " = " + loc);
}
}
- 列表
- 可用與數組相同的形式排序和搜索一個列表（ List）。用於排序和搜索列表的靜態方法包含在類Collections 中，但它們擁有與 Arrays 中差不多的簽名： sort(List)用於對一個實現了 Comparable 的對象列表進行排序； binarySearch(List,Object)用於查找列表中的某個對象； sort(List,Comparator)利用一個“比較器”對一個列表進行排序；而binarySearch(List,Object,Comparator)則用於查找那個列表中的一個對象
public class ListSort {
public static void main(String[] args) {
final int SZ = 20;
// Using "natural comparison method":
List a = new ArrayList();
for(int i = 0; i < SZ; i++)
a.add(new CompClass(
(int)(Math.random() *100)));
Collection1.print(a);
Collections.sort(a);
Collection1.print(a);
Object find = a.get(SZ/2);259
int loc = Collections.binarySearch(a, find);
System.out.println("Location of " + find +
" = " + loc);
// Using a Comparator:
List b = new ArrayList();
for(int i = 0; i < SZ; i++)
b.add(Array1.randString(4));
Collection1.print(b);
AlphaComp ac = new AlphaComp();
Collections.sort(b, ac);
Collection1.print(b);
find = b.get(SZ/2);
// Must use the Comparator to search, also:
loc = Collections.binarySearch(b, find, ac);
System.out.println("Location of " + find +
" = " + loc);
}
}
這些方法的用法與在 Arrays 中的用法是完全一致的，只是用一個列表代替了數組。
TreeMap 也必須根據 Comparable 或者 Comparator 對自己的對象進行排序
Collections 類中的實用工具：
enumeration(Collection) 為自變量產生原始風格的 Enumeration（枚舉）
max(Collection)， min(Collection) 在自變量中用集合內對象的自然比較方法產生最大或最小元素
max(Collection,Comparator)， min(Collection,Comparator) 在集合內用比較器產生最大或最小元素
nCopies(int n, Object o) 返回長度為 n 的一個不可變列表，它的所有句柄均指向 o
subList(List,int min,int max) 返回由指定參數列表後推得到的一個新列表。可將這個列表想象成一個
“窗口”，它自索引為 min 的地方開始，正好結束於 max 的前面
注意 min()和 max()都是隨同 Collection 對象工作的，而非隨同 List，所以不必擔心 Collection 是否需要排序（就象早先指出的那樣，在執行一次 binarySearch()—— 即二進制搜索—— 之前，必須對一個 List 或者一個數組執行 sort()）
1. 使 Collection 或 Map 不可修改
通常，創建 Collection 或 Map 的一個“只讀”版本顯得更有利一些。 Collections 類允許我們達到這個目標，方法是將原始容器傳遞進入一個方法，並令其傳回一個只讀版本。這個方法共有四種變化形式，分別用於 Collection（如果不想把集合當作一種更特殊的類型對待）、 List、 Set 以及 Map。
public class ReadOnly {
public static void main(String[] args) {
Collection c = new ArrayList();
Collection1.fill(c); // Insert useful data
c = Collections.unmodifiableCollection(c);
Collection1.print(c); // Reading is OK
// ! c.add("one"); // Can't change it
List a = new ArrayList();
Collection1.fill(a);
a = Collections.unmodifiableList(a);
ListIterator lit = a.listIterator();
System.out.println(lit.next()); // Reading OK
// ! lit.add("one"); // Can't change it
Set s = new HashSet();
Collection1.fill(s);
s = Collections.unmodifiableSet(s);
Collection1.print(s); // Reading OK
// ! s.add("one"); // Can't change it
Map m = new HashMap();
Map1.fill(m, Map1.testData1);
m = Collections.unmodifiableMap(m);
Map1.print(m); // Reading OK
// ! m.put("Ralph", "Howdy!");
}
}
對於每種情況，在將其正式變為只讀以前，都必須用有有效的數據填充容器。一旦載入成功，最佳的做法就是用“不可修改”調用產生的句柄替換現有的句柄。這樣做可有效避免將其變成不可修改後不慎改變其中的內容。
在另一方面，該工具也允許我們在一個類中將能夠修改的容器保持為private 狀態，並可從一個方法調用中返回指向那個容器的一個只讀句柄。這樣一來，雖然我們可在類裡修改它，但其他任何人都只能讀。
為特定類型調用“不可修改”的方法不會造成編譯期間的檢查，但一旦發生任何變化，對修改特定容器的方法的調用便會產生一個 UnsupportedOperationException 違例。
2.Collection 或 Map 的同步
在這兒，大家只需注意到 Collections 類提供了對整個容器進行自動同步的一種途徑。它的語法與“不可修改”的方法是類似的：
public class Synchronization {
public static void main(String[] args) {
Collection c = Collections.synchronizedCollection(new ArrayList());
List list = Collections.synchronizedList(new ArrayList());
Set s = Collections.synchronizedSet(new HashSet());
Map m = Collections.synchronizedMap(new HashMap());
}
}
總結
(1) 數組包含了對象的數字化索引。它容納的是一種已知類型的對象，所以在查找一個對象時，不必對結果進行造型處理。數組可以是多維的，而且能夠容納基本數據類型。但是，一旦把它創建好以後，大小便不能變化了。
(2) Vector（矢量）也包含了對象的數字索引—— 可將數組和 Vector 想象成隨機訪問集合。當我們加入更多的元素時， Vector 能夠自動改變自身的大小。但 Vector 只能容納對象的句柄，所以它不可包含基本數據類型；而且將一個對象句柄從集合中取出來的時候，必須對結果進行造型處理。
(3) Hashtable（散列表）屬於 Dictionary（字典）的一種類型，是一種將對象（而不是數字）同其他對象關聯到一起的方式。散列表也支持對對象的隨機訪問，事實上，它的整個設計方案都在突出訪問的“高速度”。
(4) Stack（堆棧）是一種“後入先出”（ LIFO）的隊列
對於 Hashtable，可將任何東西置入其中，並以非常快的速度檢索；對於 Enumeration（枚舉），可遍歷一個序列，並對其中的每個元素都採取一個特定的操作。那是一種功能足夠強勁的工具。
但 Hashtable 沒有“順序”的概念。 Vector 和數組為我們提供了一種線性順序，但若要把一個元素插入它們任何一個的中部，一般都要付出“慘重”的代價。除此以外，隊列、拆散隊列、優先級隊列以及樹都涉及到元素的“排序” —— 並非僅僅將它們置入，以便以後能按線性順序查找或移動它們。
三、各集合類對比總結
集(Set)：集裡的對象不按任何特定的方式排列，按索引值來操作數據，不能有重複的元素
列表(List)：序列中的對象以線性方式存儲，按索引值來操作數據，可以有重複的元素
映射(Map)：映射的每一項為“名稱—數值”對，名稱不可以重複，值可以重複，一個名稱對應一個唯一的值
迭代器Iterator
迭代器是按次序一個一個地獲取集合中所有的對象，是訪問集合中每個元素的標準機制。
迭代器的創建：Collection接口的iterator()方法返回一個Iterator
Iterator it=test.iterator(); //將test集合對象轉為迭代器
迭代器的常用方法：
hasNext() //判斷迭代器中是否有下一個元素
next() //返回迭代的下一個元素
Remove() //將迭代器新返回的元素刪除
public interface Iterator {
boolean hasNext();
Object next();
void remove(); // Optional
}
在調用remove()方法的時候, 必須調用一次next()方法.
remove()方法實際上是刪除上一個返回的元素.
List常用方法
void add(int index, Object element) ：添加對象element到位置index上
boolean addAll(int index, Collection collection) ：在index位置後添加容器collection中所有的元素
Object get(int index) ：取出下標為index的位置的元素
int indexOf(Object element) ：查找對象element 在List中第一次出現的位置
int lastIndexOf(Object element) ：查找對象element 在List中最後出現的位置
Object remove(int index) ：刪除index位置上的元素
ListIterator listIterator(int startIndex) ：返回一個ListIterator 跌代器，開始位置為startIndex
List subList(int fromIndex, int toIndex) ：返回一個子列表List ,元素存放為從 fromIndex 到toIndex之前的一個元素
ArrayList
可以將其看作是能夠自動增長容量的數組。
利用ArrayList的toArray()返回一個數組。
Arrays.asList()返回一個列表。
迭代器(Iterator) 給我們提供了一種通用的方式來訪問集合中的元素。
ArrayList可以自動擴展容量
ArrayList.ensureCapacity(int minCapacity)
首先得到當前elementData 屬性的長度oldCapacity。
然後通過判斷oldCapacity和minCapacity參數誰大來決定是否需要擴容, 如果minCapacity大於 oldCapacity，那麼我們就對當前的List對象進行擴容。
擴容的的策略為：取(oldCapacity * 3)/2 + 1和minCapacity之間更大的那個。然後使用數組拷 貝的方法，把以前存放的數據轉移到新的數組對象中如果minCapacity不大於oldCapacity那麼就不進行擴容。
LinkedList
LinkedList是採用雙向循環鏈表實現的。
利用LinkedList可以實現棧(stack)、隊列(queue)、雙向隊列(double-ended queue )。
它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()等。
ArrayList和LinkedList的比較
1.ArrayList是實現了基於動態數組的數據結構，LinkedList基於鏈表的數據結構。
2.對於隨機訪問get和set，ArrayList覺得優於LinkedList，因為LinkedList要移動指針。
3.對於新增和刪除操作add和remove，LinedList比較佔優勢，因為ArrayList要移動數據。
儘量避免同時遍歷和刪除集合。因為這會改變集合的大小；
for( Iterator iter = ComList.iterator(); iter.hasNext();){
ComType com = iter.next();
if ( !com.getName().contains("abc")){
ComList.remove(com);}
}
推薦：
for( Iterator iter = ComList.iterator(); iter.hasNext();){
ComType com = iter.next();
if ( !com.getName().contains("abc")){
iter.remove(com); }
無限制的在lst中add element，勢必會造成lst佔用內存過高
Map常用方法
常用方法：
Object put(Object key,Object value)：用來存放一個鍵-值對Map中
Object remove(Object key)：根據key(鍵)，移除鍵-值對，並將值返回
void putAll(Map mapping) ：將另外一個Map中的元素存入當前的Map中
void clear() ：清空當前Map中的元素
Object get(Object key) ：根據key(鍵)取得對應的值
boolean containsKey(Object key) ：判斷Map中是否存在某鍵（key）
boolean containsValue(Object value):判斷Map中是否存在某值(value)
public Set keySet() ：返回所有的鍵（key），並使用Set容器存放
public Collection values() ：返回所有的值（Value），並使用Collection存放
public Set entrySet() ：返回一個實現 Map.Entry 接口的元素 Set
HashMap
Map 主要用於存儲鍵(key)值(value)對，根據鍵得到值，因此鍵不允許重複,但允許值重複。
HashMap 是一個最常用的Map,它根據鍵的HashCode 值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度。
Hashmap 是一個最常用的Map,它根據鍵的HashCode 值存儲數據,根據鍵可以直接獲取它的值，具有很快的訪問速度，遍歷時，
取得數據的順序是完全隨機的。LinkedHashMap保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的.也可以在構造時用帶參數，按照應用次數排序。在遍歷的時候會比HashMap慢，不過有種情況例外，當HashMap容量很大，實際數據較少時，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數據有關，和容量無關，而HashMap的遍歷速度和他的容量有關。
TreeMap實現SortMap接口，能夠把它保存的記錄根據鍵排序,默認是按鍵值的升序排序，也可以指定排序的比較器，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的。
我們用的最多的是HashMap,HashMap裡面存入的鍵值對在取出的時候是隨機的,在Map 中插入、刪除和定位元素，HashMap 是最好的選擇。
TreeMap取出來的是排序後的鍵值對。但如果您要按自然順序或自定義順序遍歷鍵，那麼TreeMap會更好。
LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那麼用LinkedHashMap可以實現,它還可以按讀取順序來排列，像連接池中可以應用。
Set的使用
不允許重複元素
對 add()、equals() 和 hashCode() 方法添加了限制
HashSet和TreeSet是Set的實現
Set—》HashSet LinkedHashSet
SortedSet —》 TreeSet
HashSet
public boolean contains(Object o) ：如果set包含指定元素，返回true
public Iterator iterator()返回set中元素的迭代器
public Object[] toArray() ：返回包含set中所有元素的數組public Object[] toArray(Object[] a) ：返回包含set中所有元素的數組，返回數組的運行時類型是指定數組的運行時類型
public boolean add(Object o) ：如果set中不存在指定元素，則向set加入
public boolean remove(Object o) ：如果set中存在指定元素，則從set中刪除
public boolean removeAll(Collection c) ：如果set包含指定集合，則從set中刪除指定集合的所有元素
public boolean containsAll(Collection c) ：如果set包含指定集合的所有元素，返回true。如果指定集合也是一個set，只有是當前set的子集時，方法返回true
實現Set接口的HashSet，依靠HashMap來實現的。
我們應該為要存放到散列表的各個對象定義hashCode()和equals()。
HashSet如何過濾重複元素
調用元素HashCode獲得哈希碼–》判斷哈希碼是否相等，不相等則錄入—》相等則判斷equals()後是否相等，不相等在進行hashcode錄入，相等不錄入
TreeSet
TreeSet是依靠TreeMap來實現的。
TreeSet是一個有序集合，TreeSet中元素將按照升序排列，缺省是按照自然順序進行排列，意味著TreeSet中元素要實現Comparable接口，我們可以在構造TreeSet對象時，傳遞實現了Comparator接口的比較器對象。
HashSet與TreeSet與LinkedHashSet對比
HashSet不能保證元素的排列順序，順序有可能發生變化，不是同步的，集合元素可以是null,但只能放入一個null
TreeSet是SortedSet接口的唯一實現類，TreeSet可以確保集合元素處於排序狀態。TreeSet支持兩種排序方式，自然排序 和定製排序，其中自然排序為默認的排序方式。向 TreeSet中加入的應該是同一個類的對象。
TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false，或者通過CompareTo方法比較沒有返回0
自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法來比較元素之間大小關係，然後將元素按照升序排列。
定製排序
自然排序是根據集合元素的大小，以升序排列，如果要定製排序，應該使用Comparator接口，實現 int compare(To1,To2)方法
LinkedHashSet集合同樣是根據元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護元素的次序。這樣使得元素看起 來像是以插入順 序保存的，也就是說，當遍歷該集合時候，LinkedHashSet將會以元素的添加順序訪問集合的元素。
LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色於HashSet。
現在私信我可以免費獲得Java從入門到高級詳學習視頻及資料
關鍵字: 詳解 LinkedList Add
