使用 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
