• 在实际开发中，我们经常会对一组相同类型的数据进行统一的管理操作，到目前为止，我们可以使用的数组结构，链表结构，二叉树结构来实现；
• 数组的最大问题在于数组中的元素个数是固定的，要实现动态数组，毕竟还是比较麻烦，自己实现链表或者二叉树结构来管理对象更是不方便；
• 在JDK1.2版本后，JAVA完整的提供了类集合的概念，封装了一组强大的、非常方便的集合框架API，让我们在开发中大大的提高了效率；

首先上一张图（网络上下载的，不知道具体的出处请原创者谅解），先直观的了解一下java集合类的整体架构

Collection、MAP、Iterator

集合框架的接口和类在java.util包中

API中的定义：Conllection层次结构中的根接口，Collection表示一组对象，这些对象也称为collection的元素，一些collection允许有重复的元素，而一些则不允许，一些collection是有序的，而一些则是无序的，JDK不提供此接口的任何直接实现，它提供更具体的子接口，(如set、List)实现，此接口通常用来传递collection，并在需要的最大普遍性的地方操作这些collection；

• 接口的定义

public interface Collection<E>
extends Iterable<E>

API中的定义：有序的collection（也成为序列），此接口的用户可以对列表中每个元素的插入位置进行精确的控制，用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素；

• 1、允许重复元素
• 2、必须是有序的
• 3、允许null

API中的定义：List接口的大小可变数组的实现，实现了所有可选列表操作，并允许包括mull在内的所有元素，除了实现List接口外，此类还提供一下方法来操作内部用来存储列表的数组大小；

• 线程不安全

• 默认构造的ArrayList对象数组大小是10；

• 如果数组已满，就会自动扩充数组，扩充算法：

  扩充后的数组大小 = （原数组长度*3）/2 + 1
  大约等于原数组的1.5倍
  

• 内部使用动态数组实现；

• 如果我们已知元素个数，那么可以使用指定初始容量的构造方法创建ArrayList对象，这样可以有效的避免数组扩充的次数过多，从而提高效率；

• 插入或删除，数组需要重新创建，会影响性能

• 查找效率高

API中的定义：Vector类可以实现可增长的对象数组，与数组一样，它可以使用整数索引进行访问的组件，但是，Vector的大小可以根据需要增大或者缩小，以适应创建Vector后进行添加或者移除项的操作

• 线程安全

• 使用动态对象数组；

• 默认构造方法初始容量10；

• 如果数组已满，就会自动扩充数组，扩充算法：

  有两种情况：
  1、如果有指定增量：
     扩充后的数组大小 = 原数组长度 + 增量
  2、如果没有指定增量：
     扩充后的数组大小 = 原数组长度 * 2
  

API中的定义：List接口的链接列表实现，实现所有可选的列表操作，并且所有元素（包括null），除了实现List接口外，Linklist类还为在列表的开头以及结尾get、remove和insert元素提供统一的命名方法.

• 使用双向链表实现；
• 插入和删除速度快、效率高；
• 查找效率低

API中的定义：一个不包含重复元素的collection，更确切的讲，set不包含满足e1.equals(e2)的元素，并且最多包含一个null元素。

• 不允许重复元素（通过equals方法判断是否同一元素）；

API中的定义：实现Set接口，由哈希表支持，不保证set的迭代顺序，特别是它不保证该顺序恒久不变，允许使用null元素；

• 不保证迭代顺序；

• 底层使用HashMap实现，由于HashMap的默认容量是16，所有HashSet的容量也是16；

• 自定义对象是否重复的判断条件是：

  • 1、 先判断hashCode是否相等，如果hashCode不相等，那么一定不是同一个对象；
  • 2、如果hashCode相等，不一定是同一个对象，还需要equals方法进一步判断：
    • 如果equals返回true，表示同一个对象；
    • 如果equals返回false，表示对象不相同；

API中的定义：基于TreeMap的NavigableSet实现，使用元素的自然顺序对元素进行排序，或者根据创建set时提供的Comparator进行排序，具体取决于使用的构造方法；

• 使用元素的自然顺序对元素进行排序；
• 底层使用TreeMap实现（树型结构）;
• 在TreeSet集合中存储自定义对象时，该对象必须实现Comparable/Comparator接口；
• 判断是否重复对象是通过compareTo，compareTo返回0则说明是同一个对象；

API中的定义：具有可预知迭代顺序的Set接口实现，此实现与HashSet的不同之处在于，后者维护着一个运行于所有条目的双重链接列表，此链接列表定义了迭代顺序，即按照将元素插入set中的顺序（插入顺序）进行迭代。注意，插入顺序不受在set中重新插入的元素的影响；

• 使用哈希表+双向链表实现
• 会以插入的顺序输出
• 底层使用LinkedHashMap实现
• 是HashSet的子类

Iterator是专门用来遍历集合输出的接口

• hasNext() 如果还有元素可以迭代，返回true
• next() 返回迭代的下一个元素
• remove() 从集合中删除

API中的定义：将键映射到值的对象，一个映射不能包含重复的键，每个键最多只能映射一个值；

• 1、使用键值对的方式存储数据；

API中的定义：基于哈希表的Map接口实现类，此实现提供所有可选的映射操作，并允许使用null值和null键，（除了非同步和允许使用null之外，HashMap类与HashTable大致相同），此类不保证映射的顺序，特别是它不保证该顺序恒久不变；

• 使用哈希表+链表实现
• 允许null键和null值
• 通过HashMap的key值的hashCode方法模哈希表数组长度求出散列值，根据散列值得出对象在哈希表中存储的位置，相同位置上的多个对象以链表方式存储；
• 当扩充容量时，由于哈希表需要重新散列，所以会影响性能；（扩充需要重新散列，是为了提高查找效率）
• 默认初始容量为16，每次重新散列（扩容）的方式：原数组长度*2；
• 默认的加载因子是0.75（也就是当达到总容量的75%就开始扩容）
• 线程不安全

API中的定义：此类实现一个哈希表，该哈希表将键映射到相应的值，任何非null对象都可以用作键或值；为了成功地在哈希表中存储和获取对象，用作键的对象必须实现hashCode方法和equals方法；

• HashTable不允许空的键值对；
• 默认的初始容量是11，加载因子是0.75；
• 是线程安全的

API中的定义：基于红黑树（Red-Black tree）的NavigableMap实现，该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序，具体取决于使用的构造方法；

• 线程不安全
• 使用二叉树中的红黑树实现
• 以key对象的自然顺序构造映射树
• 使用自定义对象作为key值时，该对象的类必须实现Comparable/Comparator接口实现比较规则

API中的定义：Map接口的哈希表和链接列表实现，具有预知的迭代顺序，此实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表；

• Map接口的哈希表和链接列表实现，具有可预知的迭代顺序；

• 使用map.keySet()方法把所有的key对象以转换成Set集合，然后迭代set集合取出每个key，再通过key从map中取出value；
• 使用map.values()方法把所有的value对象转换成Collection集合，然后进行遍历;
• 使用map.entrySet()方法把所有的Entry对象转换成Set集合，然后进行迭代;

• Collecton和Map具有依赖关系，具体的说：
  • HashSet底层是通过HashMap实现的；
  • TreeSet底层是通过TreeMap实现的；

• 实现List接口的类允许存在重复对象：ArrayList、Vector、ArrayList等；
• 实现Set接口的类不允许存在重复对象：HashSet、TreeSet等；

链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针；

特点:插入和删除速度快

使用递归算法实现

树是一种重要的非线性数据结构，直观的看，它是数据元素（在树种称为节点）按分支关系组织起来的结构。二叉树（Binary Tree）是每个节点最多有两个子树的有序树。通常子树被称为“左子树”和“右子树”。

二叉树算法的排序规则：

• 选择第一个元素作为根节点；
• 之后如果元素大于根节点放在右子树，如果元素小于根节点，则放在左子树，如果元素等于根节点，放左右都可以；
• 最后安装中序（根在中间，根据根的位置分为：先序、中序、后序）遍历的方式进行输出，则可以得到排序的结果（左->根->右）

• hashCode是Object的方法

public native int hashCode();

• hashCode是本地方法，它的实现是根据本地机器相关，当然我们可以自己写得类中覆盖hashCode()方法,比如String、Interger、Double。。。等等这些类都是覆盖了hashCode()方法；

• 在Java的集合中，判断两个对象是否相等的规则是：

  • 判断两个对象的hashCode是否相等
    • 如果不相等，认为两个对象不相等，结束判断；
    • 如果相等，则判断equals是否相等；
  • 判断两个对象equals是否相等
    • 如果不相等，认为两个对象不相等；
    • 如果相等，认为两个对象相等；
  • equals方法是判断两个对象是否相等的关键；

• Collection：
  • Collection是集合框架的顶层接口，具体的子接口主要是：List、Set；
  • List的实现类包括：Arraylist、Vector、Linkedlist；
  • set的实现类包括：HashSet、TreeSet、LinkerHashSet；
• Collections:
  • 此类完全由在collection上进行操作或返回collection的静态方法组成，作为操作Collection的工具类；
  • 典型的方法有：addAll、sort、synchronizedList、synchronizedMap、synchronizedSet等等；

ArrayList是基于数组实现的，查询速度快，插入删除慢，ArrayList线程不安全。

LinkedList是基于双链表实现的，查询速度慢，插入速度快；

使用场景：

（1）如果应用程序对各个索引位置的元素进行大量的存取或删除操作，ArrayList对象要远优于LinkedList对象；

( 2 ) 如果应用程序主要是对列表进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象；

数组：是将元素在内存中连续存储的；

它的优点：因为数据是连续存储的，内存地址连续，所以在查找数据的时候效率比较高；

它的缺点：在存储之前，我们需要申请一块连续的内存空间，并且在编译的时候就必须确定好它的空间的大小。在运行的时候空间的大小是无法随着你的需要进行增加和减少而改变的，当数据比较大的时候，有可能会出现越界的情况，数据比较小的时候，又有可能会浪费掉内存空间。在改变数据个数时，增加、插入、删除数据效率比较低。

链表：是动态申请内存空间，不需要像数组需要提前申请好内存的大小，链表只需在用的时候申请就可以，根据需要来动态申请或者删除内存空间，对于数据增加和删除以及插入比数组灵活。还有就是链表中数据在内存中可以在任意的位置，通过应用来关联数据（就是通过存在元素的指针来联系）

• 利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
• 存储时，如果出现hash值相同的key，此时有两种情况。
  • (1)如果key相同，则覆盖原始值；
  • (2)如果key不同（出现冲突），则将当前的key-value放入链表中
• 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
• 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

1、存储方式不同

HashMap内部有一个HashMapEntry<K, V>[]对象，每一个键值对都存储在这个对象里，当使用put方法添加键值对时，就会new一个HashMapEntry对象，

2、添加数据时扩容时的处理不一样，HashMap进行了new操作，重新创建对象，开销很大。ArrayMap用的是copy数据，所以效率相对要高。

3、ArrayMap提供了数组收缩的功能，在clear或remove后，会重新收缩数组，释放空间

4、ArrayMap采用二分法查找；

HashMap不是线程安全的，效率高一点、方法不是Synchronize的要提供外同步，有containsvalue和containsKey方法。

hashtable是，线程安全，不允许有null的键和值，效率稍低，方法是是Synchronize的。有contains方法方法。Hashtable 继承于Dictionary 类

总结：

HashMap中键值 允许为空 并且是非同步的

Hashtable中键值 不允许为空 是同步的

继承不同，但都实现了Map接口

• HashMap知识点：

  • HashMap是“链表数列”的数据结构，即数组和链表的结合体。它底层是一个数组，数组中每一项是一条链表。

  • HashMap的实例有两个参数影响其性能：“初始化容量”和“装填因子”。

  • HashMap线程不安全。

  • HashMap的key-value都是存储在entry中。

  • HashMap允许一个null键，多个null值，不保证元素的顺序，通过hashcode和equals方法保证键的唯一性。

  • HashMap采用拉链法解决哈希冲突。

• Hashtable知识点：

  • Hashtable是线程安全的。

  • Hashtable的key，value都不允许为null。

  • Hashtable遍历方式为Iterator，Enumeration，HashMap为Iterator。

  • Hashtable直接使用对象的hashcode，HashMap重新计算hash值。

  • Hashtable数组初始化大小为11，增加方式是old*2+1；HashMap数组默认大小为16，且定义为2的指数。

HashSet不能添加重复的元素，当调用add（Object）方法时候，首先会调用Object的hashCode方法判hashCode是否已经存在，如不存在则直接插入元素；如果已存在则调用Object对象的equals方法判断是否返回true，如果为true则说明元素已经存在，如为false则插入元素。