java 常用的数据结构
Java 集合是 java 提供的工具包，包含了常用的数据结构：集合、链表、队列、栈、数组、映射等。Java 集合工具包位置是 java.util.*
Java 集合主要可以划分为 4 个部分：List 列表、Set 集合、Map 映射、工具类 (Iterator 迭代器、Enumeration 枚举类、Arrays 和 Collections)。
Java 集合工具包框架图 (如下)：
常用的集合
Java 中有几种常用的数据结构，主要分为 Collection 和 map 两个主要接口（接口只提供方法，并不提供实现），而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系（继承关系）有：
Collection---->Collections
Collection---->List----->(Vector \ ArryList \ LinkedList)
Collection---->Set------>(HashSet \ LinkedHashSet \ SortedSet)
Map----->SortedMap------>TreeMap
Map------>HashMap
** Collections **
是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于 Java 的 Collection 框架。（如排序、同步）
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 适合添加，删除操作
Set
Set 是一种不包含重复的元素的无序 Collection。
HashSet
虽然 Set 同 List 都实现了 Collection 接口，但是他们的实现方式却大不一样。List 基本上都是以 Array 为基础。但是 Set 则是在
HashMap 的基础上来实现的，这个就是 Set 和 List 的根本区别。HashSet 的存储方式是把 HashMap 中的 Key 作为 Set 的对应存储项。看看
HashSet 的 add（Object obj）方法的实现就可以一目了然了。
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) 方法添加已经存在的对象，则会覆盖前面的对象
Map
Map
是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个 Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像 Set 一样，一个
Map 容器中的键对象不允许重复，这是为了保持查找结果的一致性; 如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求，你可以将任意多个键都映射到一个值对象上，这不会发生任何问题。
HashMap
用到了哈希码的算法，以便快速查找一个键。
TreeMap
是对键按序存放，因此它便有一些扩展的方法，比如 firstKey(),lastKey() 等，你还可以从 TreeMap 中指定一个范围以取得其子 Map。
HashTable
线程安全的 HashMap，但是不能为空。
Iterator
它是遍历集合的工具，即我们通常通过 Iterator 迭代器来遍历集合。我们说 Collection 依赖于 Iterator，是因为 Collection 的实现类都要实现 iterator() 函数，返回一个 Iterator 对象。
ListIterator 是专门为遍历 List 而存在的。
Enumeration
它是 JDK 1.0 引入的抽象类。作用和 Iterator 一样，也是遍历集合；但是 Enumeration 的功能要比 Iterator 少。Enumeration 只能在 Hashtable, Vector, Stack 中使用。
** 几个常用类的区别 **
- ArrayList: 元素单个，效率高，多用于查询
- Vector: 元素单个，线程安全，多用于查询
- LinkedList: 元素单个，多用于插入和删除
- HashMap: 元素成对，元素可为空
- HashTable: 元素成对，线程安全，元素不可为空
Vector、ArrayList 和 LinkedList 和数组
- 如果能用数组的时候 (元素类型固定，数组长度固定)，请尽量使用数组来代替 List；
- 如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择 ArrayList；
- 如果在多线程条件下使用，可以考虑 Vector；
- 如果需要频繁地删除插入，LinkedList 就有了用武之地；
- 如果你什么都不知道，用 ArrayList 没错。
Collection 和 Collections 的区别
Collection
在 Java.util 下的一个接口，它是各种集合结构的父接口。继承与他的接口主要有 Set 和 List.
Collections
java.util 下的一个专用静态类，它包含有各种有关集合操作的静态方法。
提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。
Array 与 Arrays 的区别
数组类 Array
Java 中最基本的一个存储结构。
提供了动态创建和访问 Java 数组的方法。其中的元素的类型必须相同。
效率高，但容量固定且无法动态改变。
它无法判断其中实际存有多少元素，length 只是告诉我们 array 的容量。
静态类 Arrays
此静态类专门用来操作 array ，提供搜索、排序、复制等静态方法。
equals()：比较两个 array 是否相等。array 拥有相同元素个数，且所有对应元素两两相等。
sort()：用来对 array 进行排序。
binarySearch()：在排好序的 array 中寻找元素。