Java和C++在细节上的差异(四)(七)

3. LinkedList: 该集合是通过双向链表来实现的，对于指定位置元素的遍历其内部做了一个小的优化，如果position大于len/2，由于内部的数据结构是双向链表，因此可以从后向前遍历，以减少遍历过程中节点跳转的次数。ArrayList中的大部分代码示例都适用于LinkedList，以下近给出LinkedList特有的常用示例代码：

1 publicstaticvoidshowNewFeatures(String[] args) {
2 LinkedList lList = newLinkedList();
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的实现类；
2) 都可以通过iterator()方法返回Iterator迭代器对象，并可以通过该对象遍历容器中的元素；
3) 如果多个Iterator实例同时引用同一个集合对象，那么当有一个正在遍历，而另外一个修改(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 publicstaticvoidshowAddAndIterator() {
2 HashSet hs = newHashSet();
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 it = hs.iterator();
11 while(it.hasNext())
12 System.out.println(it.next());
13 }
14 publicstaticvoidshowRemoveAndClearAndContains() {
15 HashSet hSet = newHashSet();
16 hSet.add(newInteger("1"));
17 hSet.add(newInteger("2"));
18 hSet.add(newInteger("3"));
19 System.out.println(hSet.contains(newInteger("3")));
20 System.out.printl