Java Collections Framework概览

aacs4662 8年前
   <h2>概览</h2>    <p>容器,就是可以容纳其他Java对象的对象。<em>Java Collections Framework(JCF)</em>为Java开发者提供了通用的容器,其始于JDK 1.2,优点是:</p>    <ul>     <li>降低编程难度</li>     <li>提高程序性能</li>     <li>提高API间的互操作性</li>     <li>降低学习难度</li>     <li>降低设计和实现相关API的难度</li>     <li>增加程序的重用性</li>    </ul>    <p>Java容器里只能放对象,对于基本类型(int, long, float, double等),需要将其包装成对象类型后(Integer, Long, Float, Double等)才能放到容器里。很多时候拆包装和解包装能够自动完成。这虽然会导致额外的性能和空间开销,但简化了设计和编程。</p>    <h2>泛型(Generics)</h2>    <p>Java容器能够容纳任何类型的对象,这一点表面上是通过泛型机制完成,Java泛型不是什么神奇的东西,只是编译器为我们提供的一个“语法糖”,泛型本身并不需要Java虚拟机的支持,只需要在编译阶段做一下简单的字符串替换即可。实质上Java的单继承机制才是保证这一特性的根本,因为所有的对象都是Object的子类,容器里只要能够存放Object对象就行了。<br> 事实上,所有容器的内部存放的都是Object对象,泛型机制只是简化了编程,由编译器自动帮我们完成了强制类型转换而已。JDK 1.4以及之前版本不支持泛型,类型转换需要程序员显式完成。</p>    <pre>  <code class="language-java">//JDK 1.4 or before  ArrayList list = new ArrayList();  list.add(new String("Monday"));  list.add(new String("Tuesday"));  list.add(new String("Wensday"));  for(int i = 0; i < list.size(); i++){      String weekday = (String)list.get(i);//显式类型转换      System.out.println(weekday.toUpperCase());  }</code></pre>    <pre>  <code class="language-java">//JDK 1.5 or latter  ArrayList<String> list = new ArrayList<String>();//参数化类型  list.add(new String("Monday"));  list.add(new String("Tuesday"));  list.add(new String("Wensday"));  for(int i = 0; i < list.size(); i++){      String weekday = list.get(i);//隐式类型转换,编译器自动完成      System.out.println(weekday.toUpperCase());  }</code></pre>    <h2>内存管理</h2>    <p>跟C++复杂的内存管理机制不同,Java GC自动包揽了一切,Java程序并不需要处理令人头疼的内存问题,因此JCF并不像C++ STL那样需要专门的空间适配器(alloctor)。<br> 另外,由于Java里对象都在堆上,且对象只能通过引用(reference,跟C++中的引用不是同一个概念,可以理解成经过包装后的指针)访问,容器里放的其实是对象的引用而不是对象本身,也就不存在C++容器的复制拷贝问题。</p>    <h2>接口和实现(Interfaces and Implementations)</h2>    <h3>接口</h3>    <p>为了规范容器的行为,统一设计,JCF定义了14种容器接口(collection interfaces),它们的关系如下图所示:<br> <img alt="Java Collections Framework概览" src="https://simg.open-open.com/show/1aaf3cda209e3fcd003a3ab4c7522833.png" width="1520" height="574"><br> <em>Map</em>接口没有继承自<em>Collection</em>接口,因为<em>Map</em>表示的是关联式容器而不是集合。但Java为我们提供了从<em>Map</em>转换到<em>Collection</em>的方法,可以方便的将<em>Map</em>切换到集合视图。<br> 上图中提供了<em>Queue</em>接口,却没有<em>Stack</em>,这是因为<em>Stack</em>的功能已被JDK 1.6引入的<em>Deque</em>取代。</p>    <h3>实现</h3>    <p>上述接口的通用实现见下表:</p>    <p> </p>    <table align="center">     <tbody>      <tr>       <td colspan="2" rowspan="2"> </td>       <th colspan="5">Implementations</th>      </tr>      <tr>       <th>Hash Table</th>       <th>Resizable Array</th>       <th>Balanced Tree</th>       <th>Linked List</th>       <th>Hash Table + Linked List</th>      </tr>      <tr>       <th rowspan="4">Interfaces</th>       <th>Set</th>       <td>HashSet</td>       <td> </td>       <td>TreeSet</td>       <td> </td>       <td>LinkedHashSet</td>      </tr>      <tr>       <th>List</th>       <td> </td>       <td>ArrayList</td>       <td> </td>       <td>LinkedList</td>       <td> </td>      </tr>      <tr>       <th>Deque</th>       <td> </td>       <td>ArrayDeque</td>       <td> </td>       <td>LinkedList</td>       <td> </td>      </tr>      <tr>       <th>Map</th>       <td>HashMap</td>       <td> </td>       <td>TreeMap</td>       <td> </td>       <td>LinkedHashMap</td>      </tr>     </tbody>    </table>    <p>接下来的篇幅,会逐个介绍上表中容器的数据结构以及用到的算法。</p>    <p>迭代器(Iterator)</p>    <p>跟C++ STL一样,JCF的迭代器(Iterator)为我们提供了遍历容器中元素的方法。只有容器本身清楚容器里元素的组织方式,因此迭代器只能通过容器本身得到。每个容器都会通过内部类的形式实现自己的迭代器。相比STL的迭代器,JCF的迭代器更容易使用。</p>    <pre>  <code class="language-java">//visit a list with iterator  ArrayList<String> list = new ArrayList<String>();  list.add(new String("Monday"));  list.add(new String("Tuesday"));  list.add(new String("Wensday"));  Iterator<String> it = list.iterator();//得到迭代器  while(it.hasNext()){      String weekday = it.next();//访问元素      System.out.println(weekday.toUpperCase());  }</code></pre>    <pre>  <code class="language-java">JDK 1.5 引入了增强的for循环,简化了迭代容器时的写法。  </code></pre>    <pre>  <code class="language-java">//使用增强for迭代  ArrayList<String> list = new ArrayList<String>();  list.add(new String("Monday"));  list.add(new String("Tuesday"));  list.add(new String("Wensday"));  for(String weekday : list){//enhanced for statement      System.out.println(weekday.toUpperCase());  }</code></pre>    <p>源代码</p>    <p>JDK安装目录下的src.zip包含了Java core API的源代码,本文采用的是JDK 1.7u79的源码,<a href="/misc/goto?guid=4958839477163763276">下载地址</a>。<a href="/misc/goto?guid=4959672500379840383">这里复制了一份</a>。</p>    <p>参考文献</p>    <ul>     <li><a href="/misc/goto?guid=4959672500496504807">Collections Framework Overview</a></li>     <li><a href="/misc/goto?guid=4959672500598705308">The For-Each Loop</a></li>    </ul>    <p>来源:https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/1-Overview.md </p>