[关闭]
@lemonguge 2015-07-10T02:25:15.000000Z 字数 12084 阅读 366

容器

JAVA

集合框架

因为内部的数据结构不同，有多种具体容器。通过不断的向上抽取，就形成了集合框架。通过查看体系的最顶层来了解体系的基本功能，而这个框架的最顶层为Collection接口。

在现在的代码中不应该使用过时的Vector、Hashtable和Stack（栈），对于栈和Queue（队列）的行为，由LinkedList提供支持。

iterator()方法

Collection接口还实现一个超级接口Iterable，中文意思是“可迭代的”。字典里对迭代的解释：“迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。”

这个接口里只有一个方法，就是iterator()，返回一个迭代器Iterator。通过查看API，迭代器里面有三个方法：hasNext()、next()和remove()。其中remove()方法用于移除迭代器返回的最后一个元素，前面两个方法最常用。目的很明显，迭代器是用来取出元素的。

通过iterator()可以获取到迭代器，为什么需要迭代器呢？

因为每一个容器的数据结构都不同，该迭代器对象是在容器中进行内部实现的。该对象必须依赖于具体容器，对于使用容器者而言，具体的实现不重要，只要通过容器获取到该实现的迭代器的对象即可。迭代器就是内部类的使用体现。

  1. public class IteratorDemo {
  2.     public static void main(String[] args) {
  3.         Collection<String> coll = new ArrayList<String>();
  4.         coll.add("abc1");
  5.         coll.add("abc2");
  6.         coll.add("abc3");
  7.         coll.add("abc4");
  9.         for(Iterator<String> it = coll.iterator(); it.hasNext(); ){
  10.             System.out.println(it.next());
  11.         }
  12.     }
  13. } /* Output:
  14. abc1
  15. abc2
  16. abc3
  17. abc4
  18. *///:~

快速报错

在迭代器过程中，不要使用集合操作元素，容易出现异常。这是Java容器的一种保护机制，能够防止多个进程同时修改同一个容器的内容。

如果在迭代遍历某个容器的过程中，另一个进程介入其中，并且插入、删除或修改此容器内的某个对象，那么就会出现问题。为了防止容器的状态不一致。

  1. import java.util.*;
  3. public class FailFast {
  4.     public static void main(String[] args) {
  5.         Collection<String> c = new ArrayList<String>();
  6.         Iterator<String> it = c.iterator();
  7.         c.add("An object");
  8.         try {
  9.             String s = it.next();
  10.         } catch (ConcurrentModificationException e) {
  11.             System.out.println(e);
  12.         }
  13.     }
  14. } /* Output:
  15. java.util.ConcurrentModificationException
  16. *///:~

List的listIterator()方法

看名称就能猜到，这应该是专属于List的迭代器，其功能也更加强大。

  1. public class ListDemo2 {
  3.     /**
  4.      * @param args
  5.      */
  6.     public static void main(String[] args) {
  8.         List<String> list = new ArrayList<String>();
  9.         list.add("abc1");
  10.         list.add("abc2");
  11.         list.add("abc3");
  13.         System.out.println("list:"+list);
  14.         ListIterator<String> it = list.listIterator();//获取列表迭代器对象
  15.         // 它可以实现在迭代过程中完成对元素的增删改查。
  16.         while(it.hasNext()){
  17.             String str = it.next();
  18.             if(str.equals("abc1")){
  19.                 it.set("abc9"); // 替换当前元素
  20.             }
  21.         }
  22.         while(it.hasPrevious()){
  23.             System.out.println("previous:"+it.previous());
  24.         }
  25.         System.out.println("list:"+list);
  26.     }
  27. } /* Output:
  28. list:[abc1, abc2, abc3]
  29. previous:abc3
  30. previous:abc2
  31. previous:abc9
  32. list:[abc9, abc2, abc3]
  33. *///:~

LinkedList的peek..()和poll..()方法

在JDK1.6之后出现了一些新的方法来取代原来的。

  1. getFirst(); // 获取但不移除，如果链表为空，抛出NoSuchElementException.
  2. getLast();
  3. // jdk1.6之后
  4. peekFirst(); // 获取但不移除，如果链表为空，返回null.
  5. peekLast():
  7. removeFirst(); // 获取并移除，如果链表为空，抛出NoSuchElementException.
  8. removeLast();
  9. // jdk1.6之后
  10. pollFirst(); // 获取并移除，如果链表为空，返回null.
  11. pollLast();

Set中元素的唯一性

类名特点

前缀名就是该集合的数据结构，后缀名就是该集合所属的体系。

而且通常这些常用的集合容器都是不同步的。

动态类型安全

Java容器的插入方法并不检查类型，所以很可能会插入错误的类型：

  1. List l_raw = new ArrayList<Integer>();  
  2. l_raw.add(new Double(3)); // 运行没有任何异常抛出

上面的代码明显不符合我们所期望的，可以使用Collections工具类提供的类型检查的方法，比如checkedList返回一个在插入时检查类型的List：

  1. List<Integer> l = Collections.checkedList(new ArrayList<Integer>(), Integer.class);  
  2. List l_raw = l;
  3. // java.lang.ClassCastException： Attempt to insert class java.lang.Double
  4. // element into collection with element type class java.lang.Integer
  5. // ! l_raw.add(new Double(3)); // ERROR 运行抛出异常

容器的深入研究

Java类库里所有的具体容器类都继承自某个Abstract容器类。Abstract容器类存在的价值在于，当你需要写一个容器类，可以继承自这个Abstract容器类并覆盖你仅需要支持的方法，其它的不需要支持的方法可以继续抛出异常。这样你就不必耗费大量精力去实现容器接口的所有方法。

UnsupportedOperationException

未获支持的操作异常，在容器的使用中，有两个需要注意的方法，因为它们的某些操作会发生这些异常。

Arrays.asList(..)与Collections.unmodifiableList(..)方法

  1. public class Unsupported {
  2.     static void test(String msg, List<String> list) {
  3.         System.out.println("--- " + msg + " ---");
  4.         Collection<String> c = list;
  5.         Collection<String> subList = list.subList(1, 8);
  6.         // Copy of the sublist:
  7.         Collection<String> c2 = new ArrayList<String>(subList);
  8.         try {
  9.             c.retainAll(c2);
  10.         } catch (Exception e) {
  11.             System.out.println("retainAll(): " + e);
  12.         }
  13.         try {
  14.             c.removeAll(c2);
  15.         } catch (Exception e) {
  16.             System.out.println("removeAll(): " + e);
  17.         }
  18.         try {
  19.             c.clear();
  20.         } catch (Exception e) {
  21.             System.out.println("clear(): " + e);
  22.         }
  23.         try {
  24.             c.add("X");
  25.         } catch (Exception e) {
  26.             System.out.println("add(): " + e);
  27.         }
  28.         try {
  29.             c.addAll(c2);
  30.         } catch (Exception e) {
  31.             System.out.println("addAll(): " + e);
  32.         }
  33.         try {
  34.             c.remove("C");
  35.         } catch (Exception e) {
  36.             System.out.println("remove(): " + e);
  37.         }
  38.         // The List.set() method modifies the value but
  39.         // doesn't change the size of the data structure:
  40.         try {
  41.             list.set(0, "X");
  42.         } catch (Exception e) {
  43.             System.out.println("List.set(): " + e);
  44.         }
  45.     }
  47.     public static void main(String[] args) {
  48.         List<String> list = Arrays.asList("A B C D E F G H I J K L".split(" "));
  49.         test("Modifiable Copy", new ArrayList<String>(list));
  50.         test("Arrays.asList()", list);
  51.         test("unmodifiableList()", Collections.unmodifiableList(new ArrayList<String>(list))); // 返回容器的只读版本
  52.     }
  53. } /* Output:
  54. --- Modifiable Copy ---
  55. --- Arrays.asList() ---
  56. retainAll(): java.lang.UnsupportedOperationException
  57. removeAll(): java.lang.UnsupportedOperationException
  58. clear(): java.lang.UnsupportedOperationException
  59. add(): java.lang.UnsupportedOperationException
  60. addAll(): java.lang.UnsupportedOperationException
  61. remove(): java.lang.UnsupportedOperationException
  62. --- unmodifiableList() ---
  63. retainAll(): java.lang.UnsupportedOperationException
  64. removeAll(): java.lang.UnsupportedOperationException
  65. clear(): java.lang.UnsupportedOperationException
  66. add(): java.lang.UnsupportedOperationException
  67. addAll(): java.lang.UnsupportedOperationException
  68. remove(): java.lang.UnsupportedOperationException
  69. List.set(): java.lang.UnsupportedOperationException
  70. *///:~

Arrays.asList()返回固定尺寸的List，可以发现其中有一个set()方法，修改List中的元素是可以的，因为这并没有违法该List“尺寸固定”这一特性。

Collection或Map的同步控制

Collections类有办法能够自动同步整个容器

  1. import java.util.*;
  3. public class Synchronization {
  4.     public static void main(String[] args) {
  5.         Collection<String> c = Collections.synchronizedCollection(new ArrayList<String>());
  6.         List<String> list = Collections.synchronizedList(new ArrayList<String>());
  7.         Set<String> s = Collections.synchronizedSet(new HashSet<String>());
  8.         Set<String> ss = Collections.synchronizedSortedSet(new TreeSet<String>());
  9.         Map<String, String> m = Collections.synchronizedMap(new HashMap<String, String>());
  10.         Map<String, String> sm = Collections.synchronizedSortedMap(new TreeMap<String, String>());
  11.     }
  12. } ///:~

可以直接将新生成的容器传递给适当的“同步”方法。

SortedSet接口

SortedSet接口有一个子类TreeSet实现类，了解一下该接口的功能。里面有三个方法值得注意：

  1. public class SortedSetDemo {
  2.     public static void main(String[] args) {
  3.         SortedSet<String> sortedSet = new TreeSet<String>();
  4.         Collections.addAll(sortedSet,
  5.                 "one two three four five six seven eight".split(" "));
  6.         print(sortedSet);
  7.         String low = sortedSet.first();
  8.         String high = sortedSet.last();
  9.         print(low);
  10.         print(high);
  11.         Iterator<String> it = sortedSet.iterator();
  12.         for (int i = 0; i <= 6; i++) {
  13.             if (i == 3)
  14.                 low = it.next();
  15.             if (i == 6)
  16.                 high = it.next();
  17.             else
  18.                 it.next(); // i=3时，走了两次next()
  19.         }
  20.         print(low);
  21.         print(high);
  22.         print(sortedSet.subSet(low, high));
  23.         print(sortedSet.headSet(high));
  24.         print(sortedSet.tailSet(low));
  25.     }
  26. } /* Output:
  27. [eight, five, four, one, seven, six, three, two]
  28. eight
  29. two
  30. one
  31. two
  32. [one, seven, six, three]
  33. [eight, five, four, one, seven, six, three]
  34. [one, seven, six, three, two]
  35. *///:~

SortedMap接口，在现阶段TreeMap类是它的唯一实现，里面的方法和SortedSet接口类似。

散列和散列码

HashMap对速度进行了优化，因为HashMap使用了特殊的值，称作散列码。散列码是“相对唯一”的、用以代表对象的int值，它是通过将对象的某些信息进行转换而生成的。hashCode()是根类Object中的方法，因此所有Java对象都能用hashCode()方法产生散列码。

使用散列的目的在于：想要使用一个对象查找另一个对象。

散列使得查询得以快速进行，由于瓶颈位于键的查询速度，存储一组元素最快的数据结构就是数组。在JVM中就维护了一个巨大的内存数组，我们通过键对象的hashCode()生成一个散列码，将其作为数组的下标。

为了解决数组容量被固定的问题，不同的键可以产生相同的下标。也就是说，可能会有冲突。因此，数组多大不重要，任何键总能在数组中找到它的位置。

于是查询一个值的过程首先是计算散列码，然后将散列码作为角标查询数组。通常，冲突由外部链接处理：数组并不直接保存值，而是保存值的list，然后对list的值使用equals()方法进行线性查询。这部分的查询自然会比较慢，但是散列函数好的话，数组中发生冲突比较少，在数组的每一个位置就只有较少的值。所以对于HashMap，快速的跳到数组的某个位置，只对含有很少元素的list进行比较。

散列表中的“槽位”（slot）通常称为桶位（bucket）。

我们将表示实际散列表的数组名为bucket，在明白了散列之后，编写自己的hashCode()就更有意义。

对于链表list数组，数组的大小依赖于具体的HashMap对象的容量，而容量的改变与容器的充满程度和负载因子有关。hashCode()生成的结果，经过处理后成为了桶位的下标。

设计hashCode()时最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该产生同样的值。

如果在讲一个对象用put()添加进HashMap时产生一个hashCdoe值，而用get()取出时却产生了另一个hashCode值，那么就无法获取该对象了。所以如果你的hashCode方法依赖于对象中易变的数据，用户就要当心了，因为此数据发生变化时，hashCode()方法就会生成一个不同的散列码，相当于产生了一个不同的键。

  1. public class HashCodeTest {
  2.     int age;
  3.     String name;
  4.     char sex;
  5.     boolean flag;
  7.     public HashCodeTest(int age, String name, char sex, boolean flag) {
  8.         this.age = age;
  9.         this.name = name;
  10.         this.sex = sex;
  11.         this.flag = flag;
  12.     }
  14.     public static void main(String[] args) {
  15.         System.out.println(new HashCodeTest(10, "lemon", 'M', true).hashCode());
  16.         System.out.println(new HashCodeTest(10, "lemon", 'M', true).hashCode());
  17.     }
  18. } /* Output:
  19. 1383884648
  20. 1701381926
  21. *///:~

默认的hashCode()使用的是对象的地址，有时候不同对象拥有相同的内容，我们会希望这样的对象的散列码相同。所以应该使用对象内有意义的识别信息。

  1. // 对于String而言，散列码是基于String的内容的。
  2. public class StringHashCode {
  3.     public static void main(String[] args) {
  4.         System.out.println(new String("Hello").hashCode());
  5.         System.out.println(new String("Hello").hashCode());
  6.     }
  7. } /* Output:
  8. 69609650
  9. 69609650
  10. *///:~

要想使hashCode()实用，必须速度快，并且有意义。

也就是说，它必须基于对象的内容生成散列码，我们更应该关注生成的速度，而不是唯一性，但是通过hashCode()和equals()，必须能够完全确定对象的身份。

好的hashCode()应该产生分布均匀的散列码。如果散列码都集中在一块，那么HashMap或者HashSet在某些区域的负载会很重，这样就不如分布均匀的散列函数快。不过幸运的是，我们只需要选择有意义的内容，高级编译器会自动帮我们生成覆盖后的hashCode()和equals()方法。

  1. // 对于之前的HashCodeTest类，由编译器自动生成的hashCode()和equals()方法
  2. @Override
  3. public int hashCode() {
  4.     final int prime = 31;
  5.     int result = 1;
  6.     result = prime * result + age;
  7.     result = prime * result + (flag ? 1231 : 1237);
  8.     result = prime * result + ((name == null) ? 0 : name.hashCode());
  9.     result = prime * result + sex;
  10.     return result;
  11. }
  12. @Override
  13. public boolean equals(Object obj) {
  14.     if (this == obj)
  15.         return true;
  16.     if (obj == null)
  17.         return false;
  18.     if (getClass() != obj.getClass())
  19.         return false;
  20.     HashCodeTest other = (HashCodeTest) obj;
  21.     if (age != other.age)
  22.         return false;
  23.     if (flag != other.flag)
  24.         return false;
  25.     if (name == null) {
  26.         if (other.name != null)
  27.             return false;
  28.     } else if (!name.equals(other.name))
  29.         return false;
  30.     if (sex != other.sex)
  31.         return false;
  32.     return true;
  33. }

HashMap的性能因子

我们可以通过手工调整HashMap来提高其性能，从而满足我们特定应用的需求。为了在调整HashMap时让你理解性能问题，某些术语是必需了解的：

HashMap和HashSet都具有允许你指定初始容量和负载因子的构造器。默认的负载因子是0.75，当负载情况达到指定负载因子的水平时，容器将自动增加其容量（桶位数），实现方式是使容量大致加倍，并重新将现有对象分布到新的桶位集中（这被称为再散列）。

更高的负载因子可以降低表所需要的空间，但是会增加查找代价，因为查找使我们在大部分时间里所做的操作（包括get()和put()）。如果你知道将要在HashMap中存储多少项，那么创建一个具有恰当大小的初始容量将避免自动在散列的开销。

WeakHashMap

容器类中有中特殊的Map，即WeakHashMap，它用来保存WeakReference。这是一种节约存储空间的技术，因为WeakHashMap允许垃圾回收器自动清理键和值。

  1. import java.util.*;
  3. class Element {
  4.     private String ident;
  5.     public Element(String id) { ident = id; }
  6.     public String toString() { return ident; }
  7.     @Override
  8.     public int hashCode() {
  9.         final int prime = 31;
  10.         int result = 1;
  11.         result = prime * result + ((ident == null) ? 0 : ident.hashCode());
  12.         return result;
  13.     }
  14.     @Override
  15.     public boolean equals(Object obj) {
  16.         if (this == obj)
  17.             return true;
  18.         if (obj == null)
  19.             return false;
  20.         if (getClass() != obj.getClass())
  21.             return false;
  22.         Element other = (Element) obj;
  23.         if (ident == null) {
  24.             if (other.ident != null)
  25.                 return false;
  26.         } else if (!ident.equals(other.ident))
  27.             return false;
  28.         return true;
  29.     }
  30.     protected void finalize() {
  31.         System.out.println("Finalizing " + getClass().getSimpleName() + " " + ident);
  32.     }
  33. }
  35. class Key extends Element {
  36.     public Key(String id) { super(id); }
  37. }
  39. class Value extends Element {
  40.     public Value(String id) { super(id); }
  41. }
  43. public class CanonicalMapping {
  44.     public static void main(String[] args) throws InterruptedException {
  45.         int size = 10;
  46.         Key[] keys = new Key[size];
  47.         WeakHashMap<Key, Value> map = new WeakHashMap<Key, Value>();
  49.         Key k = null;
  50.         Value v = null;
  51.         for (int i = 0; i < size; i++) {
  52.             // 在for循环结束后，k最终指向的对象也会具有强引用，所以key=key(9)不会被回收
  53.             k = new Key(Integer.toString(i));
  54.             v = new Value(Integer.toString(i));
  55.             if (i % 4 == 0)
  56.                 keys[i] = k; // 强引用使对象不被回收
  57.             map.put(k, v);
  58.         }
  60.         System.out.println("before gc size:"+map.size());
  61.         System.gc(); // 启动垃圾回收器
  62.         Thread.sleep(200); // 使主线程睡眠
  63.         System.out.println("after gc size:"+map.size());
  64.         System.out.println(map.get(new Key("1"))+" "+map.get(new Key("9")));
  65.   }
  67. } /* 
  68. before gc size:10
  69. Finalizing Key 5
  70. Finalizing Key 2
  71. Finalizing Key 1
  72. Finalizing Key 7
  73. Finalizing Key 6
  74. Finalizing Key 3
  75. after gc size:4
  76. null 9
  77. *///:~
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注