Java集合框架详解

这篇文章详细对比以及分析了java的集合框架的原理使用以及比较。

arraylist就是传说中的动态数组，就是array的复杂版本，它提供了如下一些好处：动态的增加和减少元素、灵活的设置数组的大小……

arraylist底层是数组，并且add remove指定位置元素的时候，是通过memcpy来实现的。我们直接来看源码：

arraylist源码分析：

<a></a>

源码中存放数据的数组是用transient关键字定义的

那什么是transient呢？

java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。

ansient是java语言的关键字，用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候，transient型变量的值不包括在串行化的表示中，然而非transient型的变量是被包括进去的。

在使用arraylist的toarray方法时候，因为不支持object[]向下转型，所以我们使用 t[] toarray(t[] a) 这个方法。

下面是使用方法：

linkedlist也和arraylist一样实现了list接口，但是它执行插入和删除操作时比arraylist更加高效，因为它是基于链表的。基于链表也决定了它在随机访问方面要比arraylist逊色一点。

vector实际上实现的原理和arraylist大部分都相同，不同的地方就是它绝大部分方法都使用了synchronized同步。所以会很影响性能。

源码就不看了，如果想看的朋友可以看看这篇文章：

<a href="http://blog.csdn.net/chenssy/article/details/37520981" target="_blank">vector详解</a>

对于hashset而言，它是基于hashmap实现的，hashset底层采用hashmap来保存所有元素，因此hashset的实现比较简单，查看hashset的源代码，可以看到：

由上面源程序可以看出，hashset 的实现其实非常简单，它只是封装了一个 hashmap 对象来存储所有的集合元素，所有放入 hashset 中的集合元素实际上由 hashmap 的 key 来保存，而 hashmap 的 value 则存储了一个 present，它是一个静态的 object 对象。

hashset 的绝大部分方法都是通过调用 hashmap 的方法来实现的，因此 hashset 和 hashmap 两个集合在实现本质上是相同的。

下面是一个hashset的例子：

这段测试居然输出false。这是因为 hashset 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外，还要求两个对象的 hashcode() 返回值相等。而上面程序没有重写 name 类的 hashcode() 方法，两个 name 对象的 hashcode() 返回值并不相同，因此 hashset 会把它们当成 2 个对象处理，因此程序返回 false。

由此可见，当我们试图把某个类的对象当成 hashmap 的 key，或试图将这个类的对象放入 hashset 中保存时，重写该类的 equals(object obj) 方法和 hashcode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashcode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashcode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。

我们在刚刚的实体中加入重写的hashcode方法，再进行一个测试：

根据equals和hashcode的比较，只要first属性相同，就认为这两个对象是同一个对象。那么不难想象上面的程序只包含一个对象了。

linkedhashset概述:

linkedhashset是具有可预知迭代顺序的set接口的哈希表和链接列表实现。此实现与hashset的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。

注意，此实现不是同步的。如果多个线程同时访问链接的哈希set，而其中至少一个线程修改了该set，则它必须保持外部同步。

linkedhashset的实现:

对于linkedhashset而言，它继承与hashset、又基于linkedhashmap来实现的。

linkedhashset底层使用linkedhashmap来保存所有元素，它继承与hashset，其所有的方法操作上又与hashset相同，因此linkedhashset 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个linkedhashmap来实现，在相关操作上与父类hashset的操作相同，直接调用父类hashset的方法即可。linkedhashset的源代码如下：

在父类hashset中，专为linkedhashset提供的构造方法如下，该方法为包访问权限，并未对外公开。

由上述源代码可见，linkedhashset通过继承hashset，底层使用linkedhashmap，以很简单明了的方式来实现了其自身的所有功能。

查看treeset的源码可以发现，它是利用treemap来实现的。

treeset是无序的（关于这个是不是有序无序，在总结里面讲的很清楚）。但是它可以自定义排序规则，使它按照某种顺序排列。我们可以自定义比较器，也可以把比较器传给treeset构造一个拥有自定义比较器的set。

在treeset里面放入integer和string的时候，系统会默认帮我们排序。因为它们都已经实现了comparable接口，并且重写了compareto方法。我们自己定义一个类放入treeset的时候，务必要重写实现comparable并且重写compareto方法。

这个是treeset中存放对象的map，这个navigablemap继承于sortedmap，而sortedmap继承于map。很明显，这个map带有排序功能。

这两个构造函数说明了，默认是以treemap来实现的。所以，这里就不讲太多它的实现，我们会在treemap部分讲解。

下面是treeset的使用：

第一种，我们可以让我们的实体实现comparable接口。

还有一种，我们可以自定义一个构造器，通过构造方法传入treeset

有空再进行整理

java中有序和无序的概念

    有序指的是存储顺序与添加顺序相同，并且可以通过下标访问，list就是这样。

    无序刚好相反，指的是存储顺序与添加顺序无关，没有下标，当然也不可能通过下标访问，set就是如此。

    这里需要注意的是，有序、无序中的“序”与我们平常所说的顺序无关。

而treeset是无序，但又是排好序的。即添加顺序与存储顺序无关，但是其中的对象实现了排序。

set集合总体分析

    hashset的元素存放顺序和添加进去时候的顺序没有任何关系；而linkedhashset 则保持元素的添加顺序；treeset则是对我们的set中的元素进行排序存放。

    一般来说，当要从集合中以有序的方式抽取元素时，treeset 实现就会有用处。为了能顺利进行，添加到 treeset 的元素必须是可排序的。 而同样需要对添加到treeset中的类对象实现 comparable 接口的支持。对于comparable接口的实现。假定一棵树知道如何保持 java.lang 包装程序器类元素的有序状态。一般说来，先把元素添加到 hashset，再把集合转换为 treeset 来进行有序遍历会更快。这点和hashmap的使用非常的类似。

    其实set的实现原理是基于map上面的。set中很多实现类和map中的一些实现类的使用上非常的相似。map中的“键值对”，其中的 “键”是不能重复的。这个和set中的元素不能重复一致，其实set利用的就是map中“键”不能重复的特性来实现的。 hashset的巧妙实现：就是建立一个“键值对”，“键”就是我们要存入的对象，“值”则是一个常量。这样可以确保， 我们所需要的存储的信息之是“键”。而“键”在map中是不能重复的，这就保证了我们存入set中的所有的元素都不重复。而判断是否添加元素成功，则是通 过判断我们向map中存入的“键值对”是否已经存在，如果存在的话，那么返回值肯定是常量：present ，表示添加失败。如果不存在，返回值就为null 表示添加成功。

list集合总体分析

vector的方法都是同步的（synchronized），是线程安全的（thread-safe），而arraylist的方法不是，由于线程的同步必然要影响性能，因此，arraylist的性能要比vector好。

当vector或arraylist中的元素超过它的初始大小时，vector会将它的容量翻倍，而arraylist只增加50%大小，这样，arraylist就有利于节约内存空间。

而arraylist和linkedlist通过源码发现有很大差别。一个是基于数组实现的，一个是基于链表实现。这样，当arraylist在插入数据时，必须将所有后面的数据后移，这样必然要花费较多时间。所以，当你的操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用arraylist会提供比较好的性能。而访问链表中的某个元素时,就必须从链表的一端开始沿着连接方向一个一个元素地去查找,直到找到所需的元素为止，所以,当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用linkedlist了。