基础知识

在 Java2 中，有一套设计优良的接口和类组成了Java集合框架 Collection，使程序员操作成批的数据或对象元素极为方便。这些接口和类有很多对抽象数据类型操作的 API，而这是我们常用的且在数据结构中熟知的。例如 Map，Set，List 等。并且Java用面向对象的设计对这些数据结构和算法进行了封装，这就极大的减化了程序员编程时的负担。程序员也可以以这个集合框架为基础，定义更高级别的数据抽象，比如栈、队列和线程安全的集合等，从而满足自己的需要。

Java2 的集合框架，抽其核心，主要有三种：List、Set 和 Map。如下图所示：

需要注意的是，这里的 Collection、List、Set 和 Map 都是接口（Interface），不是具体的类实现。 List lst = new ArrayList(); 这是我们平常经常使用的创建一个新的 List 的语句，在这里， List 是接口，ArrayList 才是具体的类。

常用集合类的继承结构如下：
Collection<–List<–Vector
Collection<–List<–ArrayList
Collection<–List<–LinkedList
Collection<–Set<–HashSet
Collection<–Set<–HashSet<–LinkedHashSet
Collection<–Set<–SortedSet<–TreeSet
Map<–SortedMap<–TreeMap
Map<–HashMap

———————————————–SB 分割线——————————————

List：
List 是有序的 Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在 List 中的位置，类似于数组下 >标）来访问 List 中的元素，这类似于Java的数组。

Vector：
基于数组（Array）的 List，其实就是封装了数组所不具备的一些功能方便我们使用，所以它难易避免数组的限制，同时性能也不可能超越数组。所以，在可能的情况下，我们要多运用数组。另外很重要的一点就是 Vector 是线程同步的(sychronized)的，这也是 Vector 和 ArrayList 的一个的重要区别。

ArrayList：
同 Vector 一样是一个基于数组上的链表，但是不同的是 ArrayList 不是同步的。所以在性能上要比 Vector 好一些，但是当运行到多线程环境中时，可需要自己在管理线程的同步问题。

LinkedList：
LinkedList 不同于前面两种 List，它不是基于数组的，所以不受数组性能的限制。
它每一个节点（Node）都包含两方面的内容：
1.节点本身的数据（data）；
2.下一个节点的信息（nextNode）。
所以当对 LinkedList 做添加，删除动作的时候就不用像基于数组的 ArrayList 一样，必须进行大量的数据移动。只要更改 nextNode 的相关信息就可以实现了，这是 LinkedList 的优势。

List 总结：

• 所有的 List 中只能容纳单个不同类型的对象组成的表，而不是 Key－Value 键值对。例如：[ tom,1,c ]

• 所有的 List 中可以有相同的元素，例如 Vector 中可以有 [ tom,koo,too,koo ]

• 所有的 List 中可以有 null 元素，例如[ tom,null,1 ]

• 基于 Array 的 List（Vector，ArrayList）适合查询，而 LinkedList 适合添加，删除操作

————————————–NB 分割线————————————

Set：
Set 是一种不包含重复的元素的无序 Collection。

HashSet：
虽然 Set 同 List 都实现了 Collection 接口，但是他们的实现方式却大不一样。List 基本上都是以 Array 为基础。但是 Set 则是在 HashMap 的基础上来实现的，这个就是 Set 和 List 的根本区别。HashSet 的存储方式是把 HashMap 中的 Key 作为 Set 的对应存储项。看看 HashSet 的 add（Object obj）方法的实现就可以一目了然了。

Java代码

public boolean add(Object obj) {   
   return map.put(obj, PRESENT) == null;   
}   

这个也是为什么在 Set 中不能像在 List 中一样有重复的项的根本原因，因为 HashMap 的 key 是不能有重复的。

LinkedHashSet：
HashSet 的一个子类，一个链表。

TreeSet：
SortedSet 的子类，它不同于 HashSet 的根本就是 TreeSet 是有序的。它是通过 SortedMap 来实现的。

Set 总结：

• Set 实现的基础是 Map（HashMap）

• Set 中的元素是不能重复的，如果使用 add(Object obj)方法添加已经存在的对象，则会覆盖前面的对象

————————————–2B 分割线————————————

Map：
Map 是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个 Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像 Set 一样，一个 Map 容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求，你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。

Map 有两种比较常用的实现：HashMap 和 TreeMap。

HashMap 也用到了哈希码的算法，以便快速查找一个键，

TreeMap 则是对键按序存放，因此它便有一些扩展的方法，比如 firstKey(),lastKey()等，你还可以从 TreeMap 中指定一个范围以取得其子 Map。
键和值的关联很简单，用 put(Object key,Object value)方法即可将一个键与一个值对象相关联。用 get(Object key)可得到与此 key 对象所对应的值对象。

————————————–JB 分割线————————————

其它：
一、几个常用类的区别
1．ArrayList: 元素单个，效率高，多用于查询
2．Vector: 元素单个，线程安全，多用于查询
3．LinkedList:元素单个，多用于插入和删除
4．HashMap: 元素成对，元素可为空
5．HashTable: 元素成对，线程安全，元素不可为空

二、Vector、ArrayList 和 LinkedList
大多数情况下，从性能上来说 ArrayList 最好，但是当集合内的元素需要频繁插入、删除时 LinkedList 会有比较好的表现，但是它们三个性能都比不上数组，另外 Vector 是线程同步的。所以：
如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替 List；
如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择 ArrayList；
如果在多线程条件下使用，可以考虑 Vector；
如果需要频繁地删除插入，LinkedList 就有了用武之地；
如果你什么都不知道，用 ArrayList 没错。

三、Collections 和 Arrays
在 Java 集合类框架里有两个类叫做 Collections（注意，不是 Collection！）和 Arrays，这是 JCF 里面功能强大的工具，但初学者往往会忽视。按 JCF 文档的说法，这两个类提供了封装器实现（Wrapper Implementations）、数据结构算法和数组相关的应用。
想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧，Collections 类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作：
binarySearch：折半查找。

sort：排序，这里是一种类似于快速排序的方法，效率仍然是 O(n * log n)，但却是一种稳定的排序方法。

reverse：将线性表进行逆序操作，这个可是从前数据结构的经典考题哦！

rotate：以某个元素为轴心将线性表“旋转”。

swap：交换一个线性表中两个元素的位置。
……
Collections 还有一个重要功能就是“封装器”（Wrapper），它提供了一些方法可以把一个集合转换成一个特殊的集合，如下：

unmodifiableXXX：转换成只读集合，这里 XXX 代表六种基本集合接口：Collection、List、Map、Set、SortedMap 和 SortedSet。如果你对只读集合进行插入删除操作，将会抛出 UnsupportedOperationException 异常。

synchronizedXXX：转换成同步集合。

singleton：创建一个仅有一个元素的集合，这里 singleton 生成的是单元素 Set，
singletonList 和 singletonMap 分别生成单元素的 List 和 Map。

空集：由 Collections 的静态属性 EMPTY_SET、EMPTY_LIST 和 EMPTY_MAP 表示。

如何在它们之间选择?

一、Array ， Arrays

Java 所有“存储及随机访问一连串对象”的做法，array 是最有效率的一种。

1、
效率高，但容量固定且无法动态改变。
array 还有一个缺点是，无法判断其中实际存有多少元素，length 只是告诉我们 array 的容量。

2、Java 中有一个 Arrays 类，专门用来操作 array。
arrays 中拥有一组 static 函数，
equals()：比较两个 array 是否相等。array 拥有相同元素个数，且所有对应元素两两相等。
fill()：将值填入 array 中。
sort()：用来对 array 进行排序。
binarySearch()：在排好序的 array 中寻找元素。
System.arraycopy()：array 的复制。

二、Collection ， Map

若撰写程序时不知道究竟需要多少对象，需要在空间不足时自动扩增容量，则需要使用容器类库，array 不适用。

1、Collection 和 Map 的区别

容器内每个为之所存储的元素个数不同。
Collection 类型者，每个位置只有一个元素。
Map 类型者，持有 key-value pair，像个小型数据库。

2、各自旗下的子类关系

Collection
–List： 将以特定次序存储元素。所以取出来的顺序可能和放入顺序不同。
–ArrayList / LinkedList / Vector
–Set ： 不能含有重复的元素
–HashSet / TreeSet
Map
–HashMap
–HashTable
–TreeMap

3、其他特征

* List，Set，Map 将持有对象一律视为 Object 型别。
* Collection、List、Set、Map 都是接口，不能实例化。
继承自它们的 ArrayList, Vector, HashTable, HashMap 是具象 class，这些才可被实例化。
* vector 容器确切知道它所持有的对象隶属什么型别。vector 不进行边界检查。

三、Collections

Collections 是针对集合类的一个帮助类。提供了一系列静态方法实现对各种集合的搜索、排序、线程完全化等操作。
相当于对 Array 进行类似操作的类——Arrays。
如，Collections.max(Collection coll); 取 coll 中最大的元素。
Collections.sort(List list); 对 list 中元素排序

四、如何选择？

1、容器类和 Array 的区别、择取
* 容器类仅能持有对象引用（指向对象的指针），而不是将对象信息 copy 一份至数列某位置。
* 一旦将对象置入容器内，便损失了该对象的型别信息。

2、
* 在各种 Lists 中，最好的做法是以 ArrayList 作为缺省选择。当插入、删除频繁时，使用 LinkedList()；
Vector 总是比 ArrayList 慢，所以要尽量避免使用。
* 在各种 Sets 中，HashSet 通常优于 HashTree（插入、查找）。只有当需要产生一个经过排序的序列，才用 TreeSet。
HashTree 存在的唯一理由：能够维护其内元素的排序状态。
* 在各种Maps中
HashMap 用于快速查找。
* 当元素个数固定，用 Array，因为 Array 效率是最高的。

结论：最常用的是 ArrayList，HashSet，HashMap，Array。

注意：

1、Collection 没有 get()方法来取得某个元素。只能通过 iterator()遍历元素。
2、Set 和 Collection 拥有一模一样的接口。
3、List，可以通过 get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)…。(add/get)
4、一般使用 ArrayList。用 LinkedList 构造堆栈 stack、队列 queue。

5、Map 用 put(k,v) / get(k)，还可以使用 containsKey()/containsValue()来检查其中是否含有某个 key/value。
HashMap 会利用对象的 hashCode 来快速找到 key。
* hashing
哈希码就是将对象的信息经过一些转变形成一个独一无二的 int 值，这个值存储在一个 array 中。
我们都知道所有存储结构中，array 查找速度是最快的。所以，可以加速查找。

发生碰撞时，让 array 指向多个 values。即，数组每个位置上又生成一个梿表。

6、Map 中元素，可以将 key 序列、value 序列单独抽取出来。
使用 keySet()抽取 key 序列，将 map 中的所有 keys 生成一个 Set。
使用 values()抽取 value 序列，将 map 中的所有 values 生成一个 Collection。

为什么一个生成 Set，一个生成 Collection？那是因为，key 总是独一无二的，value 允许重复

喜欢 (0)赏

[15211539367@163.com]

分享 (0)