1.
Java集合类库中最重要的两个接口Collection<E>和Map<K,V>，其中Collection接口又再次划分为
List和Set两大子接口，List中可以包含重复的元素，Set中则不可以。以下列举出一些常用的集合实现类，他们均分别继承自这两个接口：
1) ArrayList: 一种可以动态增长和缩减的索引序列(动态数组，类似于C++中的vector)；
2) LinkedList: 一种可以在任何位置进行高效的插入和删除操作的有序序列(类似于C++中list)；
3) ArrayDeque: 一种用循环数组实现的双端队列(类似于C++中的deque)；
4) HastSet：一种没有重复元素的无序集合(C++的标准库中并未提供hashset集合，但是Windows的VC和Linux平台下的gcc均各自提供了hashset容器)；
5) TreeSet: 一种有序集(类似于C++中的set)；
6) EnumSet: 一种包含枚举类型值的集；
7) LinkedHashSet: 一种可以记住元素插入次序的集，在其内部由LinkedList负责维护插入的次序，HashSet来维护Hash；
8) HashMap：一种存储键值对关联的数据结构(C++的标准库中并未提供hashmap集合，但是Windows的VC和Linux平台下的gcc均各自提供了hashmap容器)；
9) TreeMap：一种键值有序排列的映射表(类似于C++中的map)；
10) EnumMap：一种键值属于枚举类型的映射表；
11) LinkedHashMap：一种可以记住键值项插入次序的映射表；
2.
ArrayList：该集合的底层是通过动态数组来实现的，集合构造的时候可以指定一个初始容量，当插入的元素过多导致已有的容量不能容纳新元素是，其底
层数组的容量将自动增长原有容量的1.5
倍，这样会带来一定的空间浪费，但是为了避免经常扩张而带来的性能开销，只能是用空间换取时间了。如果在容器的中间添加或者删除一个元素都将会导致后面的
元素向后或向前移动一个位置，如果元素数量较多且该操作比较频繁，将会导致系统的性能降低，然而对于容器中元素的随机访问性能较好，以下为
ArrayList的常用示例代码：
1 public static void showIterator() {
2 ArrayList<String> list = new ArrayList<String>();
3 list.add("Monday");
4 list.add("Tuesdag");
5 list.add("Wednesday");
6 Iterator<String> iterator = null;
7 iterator = list.iterator();
8 //while
9 while (iterator.hasNext()) {
10 String element = iterator.next();
11 System.out.println(element);
12 }
13 //for
14 for (iterator = list.iterator(); iterator.hasNext();) {
15 String element = iterator.next();
16 System.out.println(element);
17 }
18 //for each
19 for (String element : list) {
20 System.out.println(element);
21 }
22 }
23
24 public static void showSetAndGet() {
25 ArrayList<String> nums = new ArrayList<String>();
26 nums.clear();
27 nums.add("One");
28 nums.add("Two");
29 nums.add("Three");
30 System.out.println(nums);
31 nums.set(0, "Uno");
32 nums.set(1, "Dos");
33 nums.set(2, "Tres");
34 for (int i = 0; i < nums.size(); ++i)
35 System.out.println(nums.get(i));
36 }
37
38 public static void showRemoveAndSize() {
39 ArrayList<String> al = new ArrayList<String>();
40 System.out.println("Initial size of al: " + al.size());
41 al.add("C");
42 al.add("A");
43 al.add("E");
44 al.add("B");
45 al.add(1, "A2");
46 System.out.println("Size of al after additions: " + al.size());
47 System.out.println("Contents of al: " + al);
48 al.remove("F");
49 al.remove(2);
50 System.out.println("Size of al after deletions: " + al.size());
51 System.out.println("Contents of al: " + al);
52 Iterator<String> it = al.iterator();
53 //Notes：remove() must be called after next()
54 it.next();
55 it.remove();
56 System.out.println("Size of al after deletions: " + al.size());
57 System.out.println("Contents of al: " + al);
58 }
59
60 public static void showSubListAndCopyToArray() {
61 ArrayList<String> arrayList = new ArrayList<String>();
62 arrayList.add("1");
63 arrayList.add("2");
64 arrayList.add("3");
65 arrayList.add("4");
66 arrayList.add("5");
67 List<String> lst = arrayList.subList(1, 3);
68 for (int i = 0; i < lst.size(); i++)
69 System.out.println(lst.get(i));
70 // remove one element from sub list
71 String obj = lst.remove(0);
72 System.out.println(obj + " is removed");
73 for (String str: arrayList)
74 System.out.println(str);
75 //get object array with normal method
76 Object[] objArray = arrayList.toArray();
77 for (Object obj1 : objArray)
78 System.out.println(obj1);
79 //get object array with generic method
80 String[] strArray = arrayList.toArray(new String[0]);
81 for (String str : strArray)
82 System.out.println(str);
83 }
84
85 public static void showListIterator() {
86 ArrayList<String> aList = new ArrayList<String>();
87 aList.add("1");
88 aList.add("2");
89 aList.add("3");
90 aList.add("4");
91 aList.add("5");
92
93 ListIterator<String> listIterator = aList.listIterator();
94 while (listIterator.hasNext()) {
95 System.out.println(listIterator.next());
96 System.out.println("Previous: " + listIterator.previousIndex());
97 System.out.println("Next: " + listIterator.nextIndex());
98 }
99 while (listIterator.hasPrevious()) {
100 System.out.println(listIterator.previous());
101 System.out.println("Previous: " + listIterator.previousIndex());
102 System.out.println("Next: " + listIterator.nextIndex());
103 }
104 listIterator = aList.listIterator(2);
105 listIterator.next();
106 listIterator.set("100");
107 listIterator.next();
108 listIterator.remove();
109 for (String str : aList)
110 System.out.println(str);
111
112 if (aList.contains("4"))
113 System.out.println("True");
114 else
115 System.out.println("False");
116 }
117
118 public static void showFillAndReplace() {
119 ArrayList<String> arrayList = new ArrayList<String>();
120 arrayList.add("A");
121 arrayList.add("B");
122 arrayList.add("A");
123 arrayList.add("C");
124 arrayList.add("D");
125 Collections.replaceAll(arrayList, "A", "Replace All");
126 System.out.println(arrayList);
127 Collections.fill(arrayList, "REPLACED");
128 System.out.println(arrayList);
129 }
130
131 public static void showCollectionOperation() {
132 List<String> colours = new ArrayList<String>();
133 colours.add("red");
134 colours.add("green");
135 colours.add("blue");
136
137 System.out.println(colours);
138 Collections.swap(colours, 0, 2);
139 System.out.println(colours);
140
141 Collections.reverse(colours);
142 System.out.println(colours);
143
144 Collections.sort(colours);
145 System.out.println(Arrays.toString(colours.toArray()));
146 Collections.sort(colours, Collections.reverseOrder());
147 System.out.println(Arrays.toString(colours.toArray()));
148
149 int index = Collections.binarySearch(colours, "green");
150 System.out.println("Element found at : " + index);
151 ArrayList<Integer> arrayList = new ArrayList<Integer>();
152 arrayList.add(new Integer("3"));
153 arrayList.add(new Integer("1"));
154 arrayList.add(new Integer("8"));
155 arrayList.add(new Integer("3"));
156 arrayList.add(new Integer("5"));
157 System.out.println(Collections.min(arrayList));
158 System.out.println(Collections.max(arrayList));
159 }
160
161 public static void showMinMax() {
162 ArrayList<Integer> arrayList = new ArrayList<Integer>();
163 arrayList.add(new Integer("3"));
164 arrayList.add(new Integer("1"));
165 arrayList.add(new Integer("8"));
166 arrayList.add(new Integer("3"));
167 arrayList.add(new Integer("5"));
168 System.out.println(Collections.min(arrayList));
169 System.out.println(Collections.max(arrayList));
170 }
171
172 public static void showSynchronizedList() {
173 ArrayList arrayList = new ArrayList();
174 List list = Collections.synchronizedList(arrayList);
175 //list之后的并发操作将不再需要synchronized关键字来进行同步了。
176 }
3. LinkedList:
该集合是通过双向链表来实现的，对于指定位置元素的遍历其内部做了一个小的优化，如果position大于len/2，由于内部的数据结构是双向链表，因
此可以从后向前遍历，以减少遍历过程中节点跳转的次数。ArrayList中的大部分代码示例都适用于LinkedList，以下近给出
LinkedList特有的常用示例代码：
1 public static void showNewFeatures(String[] args) {
2 LinkedList<String> lList = new LinkedList<String>();
3 lList.add("1");
4 lList.add("2");
5 lList.add("3");
6 lList.add("4");
7 lList.add("5");
8
9 System.out.println("First element of LinkedList is : " + lList.getFirst());
10 System.out.println("Last element of LinkedList is : " + lList.getLast());
11 System.out.println(lList);
12
13 String str = lList.removeFirst();
14 System.out.println(str + " has been removed");
15 System.out.println(lList);
16 str = lList.removeLast();
17 System.out.println(str + " has been removed");
18 System.out.println(lList);
19
20 lList.addFirst("1");
21 System.out.println(lList);
22 lList.addLast("5");
23 System.out.println(lList);
24 }
4. ArrayList和LinkedList的相同点：
1) 都是接口List<E>的实现类；
2) 都可以通过iterator()方法返回Iterator<E>迭代器对象，并可以通过该对象遍历容器中的元素；
3)
如果多个Iterator<E>实例同时引用同一个集合对象，那么当有一个正在遍历，而另外一个修改(add/remove)了集合对象中的
元素，对于第一个迭代器再进行迭代时将会引发ConcurrentModificationException异常的发生。
5. ArrayList和LinkedList的不同点：
1)
对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一
项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
2) 在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
3) LinkedList不支持高效的随机元素访问。
4) ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
在C++的标准库中，ArrayList和LinkedList之间的使用差异以及各自的优缺点也同样反映于vector和list。
6. HashSet:
散列表为每个对象计算出一个整数(通过Object缺省的或类重载的hashCode域方法)，称为散列码。在Java中，散列表是使用链表的数组来实现
的，每个链表被称为一个哈希桶。如果想在哈希表中查找一个对象，则需要先计算对象的hashCode，之后对表内的桶数取余数，得到的结果就是哈希桶的索
引，此时如果该桶为空桶，就可以直接将该对象插入到该桶中，如果已经有对象存在了，则需要逐个进行比较，一旦发现该与该对象相等的对象(equals()
返回true)，就会放弃本次插入操作，否则将该对象插入到该桶的末端。HashSet在构造的时候提供两个参数，一个是initialCapacity
指定了桶的数量(实际的桶数为2的initialCapacity次幂)，另一个是loadFactortian(0.0--1.0,推荐值为
0.75)，当桶的填充百分比达到该值后，哈希表内的哈希桶数将double，重新填充已有对象，该操作被称为rehash，rehash是十分影响效率
的操作，因为为了尽可能避免该事件的发生，因可能在构造HashSet的时候给出一个合理的参数。以下为HashSet的常用示例代码：
1 public static void showAddAndIterator() {
2 HashSet<String> hs = new HashSet<String>();
3 hs.add("B");
4 hs.add("A");
5 hs.add("D");
6 hs.add("E");
7 hs.add("C");
8 hs.add("F");
9 System.out.println(hs);
10 Iterator<String> it = hs.iterator();
11 while (it.hasNext())
12 System.out.println(it.next());
13 }
14 public static void showRemoveAndClearAndContains() {
15 HashSet<Integer> hSet = new HashSet<Integer>();
16 hSet.add(new Integer("1"));
17 hSet.add(new Integer("2"));
18 hSet.add(new Integer("3"));
19 System.out.println(hSet.contains(new Integer("3")));
20 System.out.println(hSet);
21 boolean blnRemoved = hSet.remove(new Integer("2"));
22 System.out.println(hSet.contains(new Integer("2")));
23 System.out.println(blnRemoved);
24 System.out.println(hSet);
25 hSet.clear();
26 System.out.println(hSet);
27 System.out.println(hSet.isEmpty());
28 }
29
30 public static void showToArrayListAndArray() {
31 HashSet<String> hs = new HashSet<String>();
32 hs.add("B");
33 hs.add("A");
34 hs.add("D");
35 System.out.println(hs);
36 List<String> list = new ArrayList<String>(hs);
37 Object[] objects = list.toArray();
38 for (Object obj : objects)
39 System.out.println("Object = " + obj);
40