Java Collections Framework概览
aacs4662
9年前
<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>