在看集合类之前, 我们要先明白一下概念:

1.数据结构

　　(1):线性表

　　　　[1]:顺序存储结构(也叫顺序表)

　　　　　　一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

　　　　[2]:链表

　　　　　　链表里面节点的地址不是连续的，是通过指针连起来的。

　　(2):哈希表

解释一:

哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

解释二:

数组的特点是：寻址容易，插入和删除困难；

而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

Hash 表的查询速度非常的快，几乎是O(1)的时间复杂度。

hash就是找到一种数据内容和数据存放地址之间的映射关系。

散列法：元素特征转变为数组下标的方法。

我想大家都在想一个很严重的问题：“如果两个字符串在哈希表中对应的位置相同怎么办？”,毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用“链表”。我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。

散列表的查找步骤

当存储记录时，通过散列函数计算出记录的散列地址

当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

优缺点

优点：不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

哈希表的原理：

　　 1，对对象元素中的关键字(对象中的特有数据)，进行哈希算法的运算，并得出一个具体的算法值，这个值 称为哈希值。

　　2，哈希值就是这个元素的位置。

　　3，如果哈希值出现冲突，再次判断这个关键字对应的对象是否相同。如果对象相同，就不存储，因为元素重复。如果对象不同，就存储，在原来对象的哈希值基础 +1顺延。

　　4，存储哈希值的结构，我们称为哈希表。

　　5，既然哈希表是根据哈希值存储的，为了提高效率，最好保证对象的关键字是唯一的。

　　这样可以尽量少的判断关键字对应的对象是否相同，提高了哈希表的操作效率。

扩展:

相同的字符串如果存进去，哈希值相同并且equals方法为true，不会存入相同的

只要哈希值相同或者equals方法为true都成立才不会存入，只要其中一条不满足，都会储存

哈希表存储过程：

1.调用对象的哈希值(通过一个函数f()得到哈希值):存储位置 = f(关键字)

2.集合在容器内搜索有没有重复的哈希值，如果没有，存入新元素，记录哈希值

3.再次存储，重复上边的过程

4.如果有重复的哈希值，调用后来者的equals方法，参数为前来者，结果得到true，集合判断为重复元素，不存入

哈希冲突

然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？

哈希冲突的解决方案有多种:

开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）

再散列函数法

链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式

关于hashcode和equals的一些问题，在面试中会问道：

1.两个对象哈希值相同，那么equals方法一定返回true吗？

不一定:取决于如何重写equals，如果重写固定了它返回false，结果就一定是false

2.equals方法返回true，那么哈希值一定相同吗？

一定:如果类中定义一个静态变量（static int a = 1），然后重写hashcode返回a+1，那么每一个对象的哈希值都不一样,不过java中规定：对象相等，必须具有相同的哈希码值，所以这里是一定的

　　(3)数组

采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

　　(4)区别

1.数组

优点：(1)随机访问效率高(根据下标查询)，(2)搜索效率较高(可使用折半方法)。

缺点：(1)内存连续且固定，存储效率低。(2)插入和删除效率低(可能会进行数组拷贝或扩容)。

2.链表

优点：(1)不要求连续内存，内存利用率高，(2)插入和删除效率高(只需要改变指针指向)。

缺点：(1)不支持随机访问，(2)搜索效率低(需要遍历)。

3.Hash表

优点：(1)搜索效率高，(2)插入和删除效率较高，

缺点：(1)内存利用率低(基于数组)，(2)存在散列冲突。

2.集合类种重要概念词解释

不弄清楚这些词的概念, 总感觉集合类学的很模糊!!!

　　(1).泛型

java中很重要的概念, 集合里面应用很多.

集合的元素，可以是任意类型对象的引用，如果把某个对象放入集合，则会忽略它的类型，就会把它当做Object类型处理.

泛型则是规定了某个集合只可以存放特定类型的对象的引用，会在编译期间进行类型检查,可以直接指定类型来获取集合元素

在泛型集合中有能够存入泛型类型的对象实例还可以存入泛型的子类型的对象实例

注意：

1 泛型集合中的限定类型，不能使用基本数据类型

2 可以通过使用包装类限定允许存放基本数据类型

泛型的好处

1 提高了安全性（将运行期的错误转换到编译期）

2 省去强转的麻烦

　　(2).哈希值

　　1 就是一个十进制的整数，有操作系统随机给出

　　2 可以使用Object类中的方法hashCode获取哈希值

　　3 Object中源码: int hashCode()返回该对象的哈希码值；

　　源码：

　　　　public native int hashCode();

　　　　native:指调用了本地操作系统的方法实现

　　(3).平衡二叉树(称AVL树)

其特点是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个子节点，其左右子树的高度都相近。

注意:

关键点是左子树和右子树的深度的绝对值不超过1

那什么是左子树深度和右子树深度呢?

如上图中:

如果插入6元素, 则8的左子树深度就为2, 右子树深度就为0,绝对值就为2, 就不是一个平很二叉树

[1].二叉排序树

1若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3左、右子树也分别为二叉排序树

解释一:

现在有a[10] = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8}需要构建二叉排序树。在没有学习平衡二叉树之前，根据二叉排序树的特性，通常会将它构建成如下左图。虽然完全符合二叉排序树的定义，但是对这样高度达到8的二叉树来说，查找是非常不利的。因此，更加期望构建出如下右图的样子，高度为4的二叉排序树，这样才可以提供高效的查找效率。

平衡二叉树是一种二叉排序树，是一种高度平衡的二叉树，其中每个结点的左子树和右子树的高度至多等于1.意味着：要么是一棵空树，要么左右都是平衡二叉树，且左子树和右子树深度之绝对值不超过1. 将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

平衡二叉树的前提是它是一棵二叉排序树。

[2].旋转

假设一颗 AVL 树的某个节点为 r，有四种操作会使 r 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。使用旋转达到平衡性

1.对 r 的左儿子的左子树进行一次插入（左旋转 LL）

 2.对 r 的左儿子的右子树进行一次插入（LR）

3.对 r 的右儿子的左子树进行一次插入（RL）

4.对 r 的右儿子的右子树进行一次插入（RR）

　　(4).红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树

(1) 检索效率O(log n)

(2) 红黑树的五点规定：

1.每个结点要么是红的要么是黑的

2.根结点是黑的

3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的

4.如果一个结点是红的，那么它的两个儿子都是黑的（反之不一定）

5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点

它的每个结点都额外有一个颜色的属性，颜色只有两种：红色和黑色。

示例:(这块难度比较大, 建议自行百度,查阅相关文档)

红黑树插入操作

如果是第一次插入,由于原树为空,所以只会违反红黑树的规则2,所以只要把根节点涂黑即可；

如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；

但是遇到如下三种情况时，我们就要开始变色和旋转了：

1. 插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的；

2. 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点；

3. 插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。

下面我们先挨个分析这三种情况都需要如何操作:

对于情况1：插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的。此时，肯定存在祖父节点，但是不知道父节点是其左子节点还是右子节点，但是由于对称性，我们只要讨论出一边的情况，另一种情况自然也与之对应。

这里考虑父节点是祖父节点的左子节点的情况(即插入一个4节点,插入的节点一般为红色,不然可能违反规则5.),如下左图所示：

对于这种情况，我们要做的操作有：将当前节点(4)的父节点(5)和叔叔节点(8)涂黑，将祖父节点(7)涂红，变成上右图所示的情况。再将当前节点指向其祖父节点，再次从新的当前节点开始算法。这样上右图就变成了情况2了。

对于情况2：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点。我们要做的操作有：将当前节点(7)的父节点(2)作为新的节点，以新的当前节点为支点做左旋操作。完成后如左下图所示，这样左下图就变成情况3了。

对于情况3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。我们要做的操作有：将当前节点的父节点(7)涂黑，将祖父节点(11)涂红，在祖父节点为支点做右旋操作。最后把根节点涂黑，整个红-黑树重新恢复了平衡，如右上图所示。至此，插入操作完成！

我们可以看出，如果是从情况1开始发生的，必然会走完情况2和3，也就是说这是一整个流程，当然咯，实际中可能不一定会从情况1发生，如果从情况2开始发生，那再走个情况3即可完成调整，如果直接只要调整情况3，那么前两种情况均不需要调整了。故变色和旋转之间的先后关系可以表示为：变色->左旋->右旋。

红黑树删除操作

我们现在约定：后继节点的子节点称为“当前节点”.

删除节点有三种情况分析：

a. 叶子节点；(直接删除即可)

　　　　　　b. 仅有左或右子树的节点；（上移子树即可）

　　　　　　c. 左右子树都有的节点。( 用删除节点的直接前驱或者直接后继来替换当前节点，调整直接前驱或者直接后继的位置)

删除操作后，如果当前节点是黑色的根节点，那么不用任何操作，因为并没有破坏树的平衡性，即没有违背红-黑树的规则，这很好理解。如果当前节点是红色的，说明刚刚移走的后继节点是黑色的，那么不管后继节点的父节点是啥颜色，我们只要将当前节点涂黑就可以了，红-黑树的平衡性就可以恢复。但是如果遇到以下四种情况，我们就需要通过变色或旋转来恢复红-黑树的平衡了。

1. 当前节点是黑色的，且兄弟节点是红色的（那么父节点和兄弟节点的子节点肯定是黑色的）；

2. 当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的两个子节点均为黑色的；

3. 当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色，右子节点时黑色的；

4. 当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色，左子节点任意颜色。

以上四种情况中，我们可以看出2,3,4其实是“当前节点是黑色的，且兄弟节点是黑色的”的三种子集，等会在程序中可以体现出来。现在我们假设当前节点是左子节点（当然也可能是右子节点，跟左子节点相反即可，我们讨论一边就可以了），分别解决上面四种情况：

对于情况1：当前节点是黑色的，且兄弟节点是红色的（那么父节点和兄弟节点的子节点肯定是黑色的）。如左下图所示：A节点表示当前节点。针对这种情况，我们要做的操作有：将父节点（B）涂红，将兄弟节点（D）涂黑，然后将当前节点（A）的父节点（B）作为支点左旋，然后当前节点的兄弟节点就变成黑色的情况了（自然就转换成情况2，3,4的公有特征了），如右下图所示：  

对于情况2：当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的两个子节点均为黑色的。如左下图所示，A表示当前节点。针对这种情况，我们要做的操作有：将兄弟节点（D）涂红，将当前节点指向其父节点（B），将其父节点指向当前节点的祖父节点，继续新的算法（具体见下面的程序），不需要旋转。这样变成了右下图所示的情况：

对于情况3：当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色，右子节点时黑色的。如左下图所示，A是当前节点。针对这种情况，我们要做的操作有：把当前节点的兄弟节点（D）涂红，把兄弟节点的左子节点（C）涂黑，然后以兄弟节点作为支点做右旋操作。然后兄弟节点就变成黑色的，且兄弟节点的右子节点变成红色的情况（情况4）了。如右下图：

对于情况4：当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色，左子节点任意颜色。如左下图所示：A为当前节点，针对这种情况，我们要做的操作有：把兄弟节点（D）涂成父节点的颜色，再把父节点（B）涂黑，把兄弟节点的右子节点（E）涂黑，然后以当前节点的父节点为支点做左旋操作。至此，删除修复算法就结束了，最后将根节点涂黑即可。

我们可以看出，如果是从情况1开始发生的，可能情况2，3，4中的一种：如果是情况2，就不可能再出现3和4；如果是情况3，必然会导致情况4的出现；如果2和3都不是，那必然是4。当然咯，实际中可能不一定会从情况1发生，这要看具体情况了。不懂的欢迎加群讨论: QQ群：123300273 (相亲相爱的一家人)

　　(5).迭代器

　　[1].迭代器模式

把访问逻辑从不同类型的集合类中抽取出来，从而避免向外部暴露集合的内部结构。在java中它是一个对象，其目的是遍历并选中其中的每个元素，而使用者（客户端）无需知道里面的具体细节。

[2].Iterator

Collection集合元素的通用获取方式：在取出元素之前先判断集合中有没有元素。如果有，就把这个元素取出来，继续再判断，如果还有就再取出来，一直把集合中的所有元素全部取出来，这种取出元素的方式专业术语称为迭代。

java.util.Iterator:在Java中Iterator为一个接口，它只提供了迭代的基本规则。在JDK中它是这样定义的：对Collection进行迭代的迭代器。迭代器取代了Java Collection Framework中的Enumeration。

Collection中有一个抽象方法iterator方法，所有的Collection子类都实现了这个方法；返回一个Iterator对象

定义:

package java.util;

public interface Iterator<E> {

boolean hasNext();//判断是否存在下一个对象元素

E next();//获取下一个元素

void remove();//移除元素

}

在使用Iterator的时候禁止对所遍历的容器进行改变其大小结构的操作。例如: 在使用Iterator进行迭代时，如果对集合进行了add、remove操作就会出现ConcurrentModificationException异常。

在进行集合元素取出的时候，如果集合中没有元素了，还继续使用next()方法的话，将发生NoSuchElementException没有集合元素的错误

修改并发异常：在迭代集合中元素的过程中，集合的长度发生改变（进行了元素增加或者元素删除的操作), 增强for的底层原理也是迭代器，所以也需要避免这种操作；

解决以上异常的方法:使用ListIterator

任何集合都有迭代器。

任何集合类，都必须能以某种方式存取元素，否则这个集合容器就没有任何意义。

迭代器，也是一种模式（也叫迭代器模式）。迭代器要足够的“轻量”——创建迭代器的代价小。

[3].Iterable(1.5)

Java中还提供了一个Iterable接口，Iterable接口实现后的功能是‘返回’一个迭代器，我们常用的实现了该接口的子接口有:Collection<E>、List<E>、Set<E>等。该接口的iterator()方法返回一个标准的Iterator实现。实现Iterable接口允许对象成为Foreach语句的目标。就可以通过foreach语句来遍历你的底层序列。

Iterable接口包含一个能产生Iterator对象的方法，并且Iterable被foreach用来在序列中移动。因此如果创建了实现Iterable接口的类，都可以将它用于foreach中。

定义:

　　Package java.lang; import java.util.Iterator; public interface Iterable<T> {    Iterator<T> iterator(); }

Iterable是Java 1.5的新特性, 主要是为了支持forEach语法, 使用容器的时候, 如果不关心容器的类型, 那么就需要使用迭代器来编写代码. 使代码能够重用.

使用方法很简单:

　　List<String> strs = Arrays.asList("a", "b", "c"); for (String str: strs) {    out.println(str); }

好处：代码减少，方便遍历

　　     弊端：没有索引，不能操作容器里的元素

增强for循环底层也是使用了迭代器获取的，只不过获取迭代器由jvm完成，不需要我们获取迭代器而已，所以在使用增强for循环变量元素的过程中不准使用集合对象对集合的元素个数进行修改；

[4].forEach()(1.8)

使用接收lambda表达式的forEach方法进行快速遍历.

　　List<String> strs = Arrays.asList("a", "b", "c"); // 使用Java 1.8的lambda表达式 strs.forEach(out::println);

[5].Spliterator迭代器

　   Spliterator是1.8新增的迭代器,属于并行迭代器,可以将迭代任务分割交由多个线程来进行。

Spliterator可以理解为Iterator的Split版本（但用途要丰富很多）。使用Iterator的时候，我们可以顺序地遍历容器中的元素，使用Spliterator的时候，我们可以将元素分割成多份，分别交于不于的线程去遍历，以提高效率。使用 Spliterator 每次可以处理某个元素集合中的一个元素 — 不是从 Spliterator 中获取元素，而是使用 tryAdvance() 或 forEachRemaining() 方法对元素应用操作。但Spliterator 还可以用于估计其中保存的元素数量，而且还可以像细胞分裂一样变为一分为二。这些新增加的能力让流并行处理代码可以很方便地将工作分布到多个可用线程上完成

[6].ListIterator

ListIterator是一个更强大的Iterator子类型，能用于各种List类访问，前面说过Iterator支持单向取数据，ListIterator可以双向移动，所以能指出迭代器当前位置的前一个和后一个索引，可以用set方法替换它访问过的最后一个元素。我们可以通过调用listIterator方法产生一个指向List开始处的ListIterator，并且还可以用过重载方法listIterator(n)来创建一个指定列表索引为n的元素的ListIterator。

ListIterator可以往前遍历，添加元素，设置元素

Iterator和ListIterator的区别：

两者都有next()和hasNext()，可以实现向后遍历，但是ListIterator有previous()和hasPrevious()方法，即可以实现向前遍历

ListIterator可以定位当前位置，nextIndex()和previous()可以实现

ListIterator有add()方法，可以向list集合中添加数据

都可以实现删除操作，但是ListIterator可以实现对对象的修改，set()可以实现，Iterator仅能遍历，不能修改

[7]Fail-Fast

类中的iterator()方法和listIterator()方法返回的iterators迭代器是fail-fast的：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

迭代器与枚举有两点不同:

　　1. 迭代器在迭代期间可以从集合中移除元素。

　　2. 方法名得到了改进，Enumeration的方法名称都比较长。

迭代器的好处：屏蔽了集合之间的不同，可以使用相同的方式取出

3.集合类概念

(1).集合类的作用

集合类也叫做容器类，和数组一样，用于存储数据，但数组类型单一，并且长度固定，限制性很大，而集合类可以动态增加长度。

集合存储的元素都是对象(引用地址)，所以集合可以存储不同的数据类型，但如果是需要比较元素来排序的集合，则需要类型一致。

集合中提供了统一的增删改查方法，使用方便。

支持泛型，避免数据不一致和转换异常，还对常用的数据结构进行了封装。

所有的集合类的都在java.util包下。

(2)集合框架体系的组成

集合框架体系是由Collection、Map(映射关系)和Iterator(迭代器)组成，各部分的作用如下所示。

[1]Collection体系中有三种集合：Set、List、Queue

Set(集)： 元素是无序的且不可重复。

List(列表)：元素是有序的且可重复。

Queue(队列)：封装了数据结构中的队列。

[2]Map体系

Map用于保存具有映射关系的数据，即key-value(键值对)。Map集合的key是唯一的，不可重复，而value可以重复。所以一个value可以对应多个key。

Map体系除了常用类之外，还有Properties（属性类）也属于Map体系。

[3]Iterator(迭代器)

请查看上面!

(3)Collection的由来

由于数组中存放对象，对对象操作起来不方便。java中有一类容器，专门用来存储对象。

集合可以存储多个元素,但我们对多个元素也有不同的需求

多个元素,不能有相同的

多个元素,能够按照某个规则排序

针对不同的需求：java就提供了很多集合类，多个集合类的数据结构不同。但是，结构不重要，重要  的是能够存储东西,能够判断,获取.

把集合共性的内容不断往上提取,最终形成集合的继承体系---->Collection

并且所有的Collection实现类都重写了toString()方法.

(4)集合和数组

集合与数组的区别：

　　　　1.数组的长度固定的，而集合长度时可变的

2.数组只能储存同一类型的元素，而且能存基本数据类型和引用数据类型。集合可以存储不同类型的元素，只能存储引用数据类型

集合类和数组不一样,数组元素既可以是基本类型的值,也可以是对象(实际上保存的是对象的引用变量);而集合只能保存对象。

数组和集合的主要区别包括以下几个方面：

一：数组声明了它容纳的元素的类型，而集合不声明。这是由于集合以object形式来存储它们的元素。

二：一个数组实例具有固定的大小，不能伸缩。集合则可根据需要动态改变大小。

三：数组是一种可读/可写数据结构没有办法创建一个只读数组。然而可以使用集合提供的ReadOnly方   只读方式来使用集合。该方法将返回一个集合的只读版本。

集合的作用：

如果一个类的内部有很多相同类型的属性，并且他们的作用与意义是一样的，比如说学生能选课学生类就有很多课程类型的属性，或者工厂类有很多机器类型的属性，我们用一个类似于容器的集合去盛装他们，这样在类的内部就变的井然有序---------这就是：

• • • 在类的内部，对数据进行组织的作用。
    • 简单而快速的搜索查找其中的某一条元素
    • 有的集合接口，提供了一系列排列有序的元素，并且可以在序列中间快速的插入或者删除有关元素。
    • 有的集合接口在其内部提供了映射关系的结构，可以通过关键字(key)去快速查找对应的唯一对象，而这个关键可以是任意类型的。

(5)泛型与集合的区别

泛型听起来很高深的一个词，但实际上它的作用很简单，就是提高java程序的性能。

比如在计算机中经常用到一些数据结构，如队列，链表等，而其中的元素以前一般这么定义：object a=new object();

这样就带来一个严重的问题，用object来表示元素没有逻辑问题，但每次拆箱、封箱就占用了大量的计算机资源，导致程序性能低下，而这部分内容恰恰一般都是程序的核心部分，如果使用object，那么程序的表现就比较糟糕。

而使用泛型则很好的解决这个问题，本质就是在编译阶段就告诉编译器，数据结构中元素的种类，既然编译器知道了元素的种类，自然就避免了拆箱、封箱的操作，从而显著提高java程序的性能。

比如List<string>就直接使用string对象作为List的元素，而避免使用object对象带来的封箱、拆箱操作，从而提高程序性能。

4.集合接口与类

(1)数组和集合一般就用到下面接口和集合

Array  数组

Arrays  数组工具

Collection 最基本的集合接口

Collections  集合工具类

List  接口

ArrayList 一种可以动态增长和缩减的索引序列

LinkedList 一种可以在任何位置进行高效地插入和删除操作的有序序列

Vector

Set

HashSet 一种没有重复元素的无序集合

TreeSet 一种有序集

LinkHashSet 一种可以记住元素插入次序的集合

map

HashMap 一种存储key：value关联的映射

HashTable

TreeMap 一种key有序的映射

LinkedHashMap 一种可以记住插入次序的映射

Deque

Stack

ArrayDeque  一种用循环数组实现的双端队列

Queue

PriorityQueue 一种可以高效删除最小元素的集合

(2)Array

数组：是以一段连续内存保存数据的；随机访问是最快的,但不支持插入,删除,迭代等操作。

Array可以包含基本类型和对象类型

Array大小是固定的

指定数组引用为 null，则此类中的方法都会抛出 NullPointerException。

所创建的对象都放在堆中。

够对自身进行枚举(因为都实现了IEnumerable接口)。

具有索引(index),即可以通过index来直接获取和修改任意项。

Array类型的变量在声明的同时必须进行实例化(至少得初始化数组的大小)，而ArrayList可以只是先声明。

Array只能存储同构的对象，而ArrayList可以存储异构的对象。

在CLR托管对中的存放方式

Array是始终是连续存放的，而ArrayList的存放不一定连续。

Array不能够随意添加和删除其中的项，而ArrayList可以在任意位置插入和删除项。

采用数组存在的一些缺陷：

1.数组长度固定不变，不能很好地适应元素数量动态变化的情况。

2.可通过数组名.length获取数组的长度，却无法直接获取数组中真实存储的个数。

3.在进行频繁插入、删除操作时同样效率低下。

(3)Arrays

数组的工具类,里面都是操作数组的工具.

常用方法:

1、数组的排序:Arrays.sort(a);//实现了对数组从小到大的排序//注：此类中只有升序排序，而无降序排序。

2、数组元素的定位查找:Arrays.binarySearch(a,8);//二分查找法

3、数组的打印:Arrays.toString(a);//String 前的a和括号中的a均表示数组名称

4、 查看数组中是否有特定的值:Arrays.asList(a).contains(1);

(4)Collection

Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类， Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个Collection参数的构造函数用于创建一个新的 Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。

如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：

　　　　Iterator it = collection.iterator(); // 获得一个迭代子

　　　　while(it.hasNext()) {

　　　　　　Object obj = it.next(); // 得到下一个元素

由Collection接口派生的两个接口是List和Set。

Collection返回的是Iterator迭代器接口，而List中又有它自己对应的实现-->ListIterator接口 Collection。标识所含元素的序列，这里面又包含多种集合类，比如List，Set，Queue；它们都有各自的特点，比如List是按顺序插入元素，Set是不重复元素集合，Queue则是典型的FIFO结构

Collection接口描述：

　　Collection接口常用的子接口有List 接口和Set接口

　　List接口中常用的子类有：ArrayList类（数组列表）和LinkedList（链表）

　　Set接口中常用的子类有：HashSet （哈希表）和LinkedHashSet（基于链表的哈希表）

Collection 层次结构 中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。（面向接口的编程思想）

(5)Collections

[1]排序操作

Collections提供以下方法对List进行排序操作

void reverse(List list)：反转

void shuffle(List list),随机排序

void sort(List list),按自然排序的升序排序

void sort(List list, Comparator c);定制排序，由Comparator控制排序逻辑

void swap(List list, int i , int j),交换两个索引位置的元素

void rotate(List list, int distance),旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面。

[2]查找，替换操作

int binarySearch(List list, Object key), 对List进行二分查找，返回索引，注意List必须是有序的

int max(Collection coll),根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)

int max(Collection coll, Comparator c)，根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)

void fill(List list, Object obj),用元素obj填充list中所有元素

int frequency(Collection c, Object o)，统计元素出现次数

int indexOfSubList(List list, List target), 统计targe在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target).

boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替换旧元素。

[3]同步控制

Collections中几乎对每个集合都定义了同步控制方法, 这些方法，来将集合包装成线程安全的集合

SynchronizedList(List);

SynchronizedSet(Set;

SynchronizedMap(Map);

SynchronizedMap和ConcurrentHashMap 区别

Collections.synchronizedMap()和Hashtable一样，实现上在调用map所有方法时，都对整个map进行同步，而ConcurrentHashMap的实现却更加精细，它对map中的所有桶加了锁。所以，只要要有一个线程访问map，其他线程就无法进入map，而如果一个线程在访问ConcurrentHashMap某个桶时，其他线程，仍然可以对map执行某些操作。这样，ConcurrentHashMap在性能以及安全性方面，明显比Collections.synchronizedMap()更加有优势。同时，同步操作精确控制到桶，所以，即使在遍历map时，其他线程试图对map进行数据修改，也不会抛出ConcurrentModificationException。

ConcurrentHashMap从类的命名就能看出，它必然是个HashMap。而Collections.synchronizedMap()可以接收任意Map实例，实现Map的同步

线程安全，并且锁分离。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的hashtable，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。

(6)List

List：有序(元素存入集合的顺序和取出的顺序一致)，元素都有索引。元素可以重复。

List本身是Collection接口的子接口，具备了Collection的所有方法。

List的特有方法都有索引，这是该集合最大的特点。

List集合支持对元素的增、删、改、查。

List中存储的元素实现类排序，而且可以重复的存储相关元素。

次序是List最重要的特点：它保证维护元素特定的顺序。

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

和下面要提到的Set不同，List允许有相同的元素。

除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个 ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。

优点：操作读取操作效率高，基于数组实现的，可以为null值，可以允许重复元素，有序，异步。

缺点：由于它是由动态数组实现的，不适合频繁的对元素的插入和删除操作，因为每次插入和删除都需要移动数组中的元素。

(7)ArrayList

ArrayList 是基于数组实现，内存中分配连续的空间，需要维护容量大小。随机访问.

ArrayList就是动态数组，也是一个对象。

ArrayList不自定义位置添加元素和LinkedList性能没啥区别，ArrayList默认元素追加到数组后面，而LinkedList只需要移动指针，所以两者性能相差无几。

如果ArrayList自定义位置插入元素，越靠前，需要重写排序的元素越多，性能消耗越大，LinkedList无论插入任何位置都一样，只需要创建一个新的表项节点和移动一下指针，性能消耗很低。

ArrayList是基于数组，所以查看任意位置元素只需要获取当前位置的下标的数组就可以，效率很高，然而LinkedList获取元素需要从最前面或者最后面遍历到当前位置元素获取，如果集合中元素很多，就会效率很低，性能消耗大。

频繁遍历查看元素,使用 ArrayList 集合,ArrayList 查询快，增删慢

ArrayList线程不安全的

1、ArrayList是用数组实现的，该对象存放在堆内存中，这个数组的内存是连续的，不存在相邻元素之间还隔着其他内存。底层是一个可动态扩容的数组

2、索引ArrayList时，速度比原生数组慢是因为你要用get方法，这是一个函数调用，而数组直接用[ ]访问，相当于直接操作内存地址，速度当然比函数调用快。

3、新建ArrayList的时候，JVM为其分配一个默认或指定大小的连续内存区域（封装为数组）。

4、每次增加元素会检查容量，不足则创建新的连续内存区域（大小等于初始大小+步长），也用数组形式封装，并将原来的内存区域数据复制到新的内存区域，然后再用ArrayList中引用原来封装的数组对象的引用变量引用到新的数组对象：

　　　　elementData = Arrays.copyOf(elementData, newCapacity);

　　ArrayList里面的removeIf方法就接受一个Predicate参数，采用如下Lambda表达式就能把，所有null元素删除:

　　　　list.removeIf(e -> e == null)；

ArrayList：每次添加元素之前会检查是否需要扩容,是按照原数组的1.5倍延长。构造一个初始容量为 10 的空列表。

使用for适合循环ArrayLIst以及数组，当大批量的循环LinkedList时程序将会卡死，for适合循环数组结构，通过下标去遍历。

get访问List内部任意元素时，ArrayList的性能要比LinkedList性能好。LinkedList中的get方法是要按照顺序从列表的一端开始检查，直到另一端。

在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；

ArrayList的空 间浪费主要体现在在list列表的结尾预留一定的容量空间

ArrayList只能包含对象类型。

ArrayList的大小是动态变化的。

对于基本类型数据，集合使用自动装箱来减少编码工作量

够对自身进行枚举(因为实现了IEnumerable接口)。

具有索引(index),即可以通过index来直接获取和修改任意项。

ArrayList允许存放（不止一个）null元素

允许存放重复数据，存储时按照元素的添加顺序存储

ArrayList可以存放任何不同类型的数据（因为它里面存放的都是被装箱了的Object型对象，实际上ArrayList内部就是使用"object[] _items;"这样一个私有字段来封装对象的）

ArrayList不是一个线程安全的集合，如果集合的增删操作需要保证线程的安全性，可以考虑使用CopyOWriteArrayList或者使用collections.synchronizedList(Lise l)函数返回一个线程安全的ArrayList类。

实现了RandomAccess接口，底层又是数组，get读取元素性能很好

顺序添加很方便

删除和插入需要复制数组 性能很差（可以使用LinkindList）

为什么ArrayList的elementData是用transient修饰的？

transient修饰的属性意味着不会被序列化，也就是说在序列化ArrayList的时候，不序列化elementData。

为什么要这么做呢？

elementData不总是满的，每次都序列化，会浪费时间和空间

重写了writeObject 保证序列化的时候虽然不序列化全部 但是有的元素都序列化

所以说不是不序列化 而是不全部序列化。

elementData属性采用了transient来修饰，不使用Java默认的序列化机制来实例化，自己实现了序列化writeObject()和反序列化readObject()的方法。

每次对下标的操作都会进行安全性检查，如果出现数组越界就立即抛出异常。

如果提前知道数组元素较多，可以在添加元素前通过调用ensureCapacity()方法提前增加容量以减小后期容量自动增长的开销。

当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

ArrayList基于数组方式实现，容量限制不大于Integer.MAX_VALUE的小大，每次扩容1.5倍。有序，可以为null,允许重复，非线程安全。

增加和删除会修改modCount,在迭代的时候需要保持单线程的唯一操作，如果期间进行了插入或者删除操作，就会被迭代器检查获知，从而出现运行时异常。

一般建议在单线程中使用ArrayList。

当在index处放置一个元素的时候，会将数组index处右边的元素全部右移

当在index处删除一个元素的时候，会将数组index处右边的元素全部左移

ArrayList底层是数组结构，因为数组有维护索引，所以查询效率高；而做插入、删除操作时，因为要判断扩容（复制一份新数组）且数组中的元素可能要大规模的后移或前移一个索引位置，所以效率差。

Arrays.asList()方法返回的List集合是一个固定长度的List集合，不是ArrayList实例，也不是Vector的实例

ArrayList也采用了快速失败(Fail-Fast机制)的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。具体介绍请参考HashMap的实现原理中的Fail-Fast机制。

(8)linkedList

LinkedList 是基于循环双向链表数据结构，不需要维护容量大小。顺序访问。

频繁插入删除元素 使用 LinkedList 集合

LinkedList 线程不安全的

LinkedList在随机访问方面相对比较慢，但是它的特性集较ArrayList 更大。

LinkedList提供了大量的首尾操作

LinkedList：底层的数据结构是链表，线程不同步，增删元素的速度非常快。

LinkedList：底层基于链表实现，链表内存是散乱的，每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快，查找慢

LinkedList由双链表实现，增删由于不需要移动底层数组数据，其底层是链表实现的，只需要修改链表节点指针，对元素的插入和删除效率较高。

LinkedList缺点是遍历效率较低。HashMap和双链表也有关系。

LinkedList是一个继承于AbstractSequentialList的双向链表，它可以被当做堆栈、队列或双端队列进行操作

LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

使用foreach适合循环LinkedList，使用双链表结构实现的应当使用foreach循环。

LinkedList实现了List接口，允许null元素。

LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

       List list = Collections.synchronizedList(new LinkedList(…));

在LinkedList的中间插入或删除一个元素的开销是固定的。

LinkedList不支持高效的随机元素访问。

LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

LinkedList是List和Deque接口的双向链表的实现。实现了所有可选列表操作，并允许包括null值。

 Fail-Fast机制:LinkedList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

LinkedList因为底层为链表结构，查询时需要从头节点（或尾节点）开始遍历所以查询效率差；但同时也因为是链表结构，做插入、删除操作时只要断开当前删除节点前驱、后驱引用，并将原来的前、后节点的引用链接起来，所以效率高。

千万不要使用普通for循环遍历LinkedList，这么做会让你崩溃！可以选择使用foreach或迭代器来进行遍历操作

LinedList适合用迭代遍历；

基于链表结构的集合 LinkedList。LinkedList 属于 java.util 包下面，也实现Iterable接口，说明可以使用迭代器遍历；LinkedList 还实现 Deque<E>，Queue<E> 操作。Deque 和 Queue 是 LinkedList 的父接口，那么 LinkedList 也可以看成一种 Deque 或者 Queue；Queue表示一种队列，也是一种数据结构，它的特点是先进先出，因此在队列这个接口里面提供了一些操作队列的方法，同时LinkedList也具有这些方法；Deque(Double ended queues双端队列)，支持在两端插入或者移除元素; 那也应该具有操作双端队列的一些方法；LinkedList 是他们的子类，说明都具有他们两者的方法；LinkedList也可以充当队列，双端队列，堆栈多个角色。

(9)vector

Vector：底层的数据结构就是数组，线程同步的，Vector无论查询和增删都巨慢。

Vector：是按照原数组的2倍延长。

Vector是基于线程安全的，效率低 元素有放入顺序，元素可重复

Vector可以由我们自己来设置增长的大小，ArrayList没有提供相关的方法。

Vector相对ArrayList查询慢(线程安全的)

Vector相对LinkedList增删慢(数组结构)

以前还能见到Vector和Stack，但Vector太过古老，被ArrayList取代，所以这里不讲；而Stack已经被ArrayDeque取代。

对于想在迭代器迭代过程中针对集合进行增删改的，可以通过返回ListIterator来操作。

Vector：底层结构是数组，线程是安全的，添加删除慢，查找快，（同ArrayList）

ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以索引数据快，插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快。

Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。

Vector 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在Vector中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。

Vector 实现了Cloneable接口，即实现clone()函数。它能被克隆。

由Vector创建的Iterator，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

(10)Set

无序(存入和取出顺序有可能不一致)，不可以存储重复元素。必须保证元素唯一性。

元素无放入顺序，元素不可重复（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的）

Set具有与Collection完全一样的接口，因此没有任何额外的功能,只是行为不同。这是继承与多态思想的典型应用：表现不同的行为。

Set不保存重复的元素(至于如何判断元素相同则较为负责)

存入Set的每个元素都必须是唯一的，因为Set不保存重复元素,加入Set的元素必须定义equals()方法以确保对象的唯一性。

Set 是基于对象的值来确定归属性的。

Set本身有去重功能是因为String内部重写了hashCode()和equals()方法，在add里实现了去重, Set集合是不允许重复元素的，但是集合是不知道我们对象的重复的判断依据的，默认情况下判断依据是判断两者是否为同一元素（euqals方法，依据是元素==元素），如果要依据我们自己的判断来判断元素是否重复，需要重写元素的equals方法（元素比较相等时调用）hashCode()的返回值是元素的哈希码，如果两个元素的哈希码相同，那么需要进行equals判断。【所以可以自定义返回值作为哈希码】 equals()返回true代表两元素相同，返回false代表不同。

set集合没有索引，只能用迭代器或增强for循环遍历

set的底层是map集合

Set最多有一个null元素

必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

Set具有与Collection完全一样的接口，没有额外的任何功能。所以把Set就是Collection，只是行为不同（这就是多态）；Set是基于对象的值来判断归属的，由于查询速度非常快速，HashSet使用了散列，HashSet维护的顺序与TreeSet或LinkedHashSet都不同，因为它们的数据结构都不同，元素存储方式自然也不同。TreeSet的数据结构是“红-黑树”，HashSet是散列函数，LinkedHashSet也用了散列函数；如果想要对结果进行排序，那么选择TreeSet代替HashSet是个不错的选择

(11)Hashset

HashSet : 为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。

Hashset实现set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set的迭代顺序,别是它不保证该顺序恒久不变。此类允许使用Null元素

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都说调用HashMap的相关方法来实现的

对于HashSet中保存的对象，请注意正确重写其equals和hashCode方法，以保证放入的对象的唯一性。

HashSet: 哈希表结构的集合 利用哈希表结果构成的集合查找速度会很快。

HashSet ： 底层数据结构是哈希表，线程 是不同步的 。 无序，高效；HashSet 集合保证元素唯一性 ：通过元素的 hashCode 方法，和 equals 方法完成的。当元素的 hashCode 值相同时，才继续判断元素的 equals 是否为 true。如果为 true，那么视为相同元素，不存。如果为 false，那么存储。如果 hashCode 值不同，那么不判断 equals，从而提高对象比较的速度。

HashSet类直接实现了Set接口， 其底层其实是包装了一个HashMap去实现的。HashSet采用HashCode算法来存取集合中的元素，因此具有比较好的读取和查找性能。

元素值可以为NULL,但只能放入一个null

　         HashSet集合保证元素唯一性：通过元素的hashCode方法，和equals方法完成的。

当元素的hashCode值相同时，才继续判断元素的equals是否为true。

如果hashCode值不同，那么不判断equals，从而提高对象比较的速度。

对于HashSet集合，判断元素是否存在，或者删除元素，底层依据的是hashCode方法和equals方法。　　

特点：存储取出都比较快

1、不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化。

2、HashSet不是同步的，必须通过代码来保证其同步。

3、集合元素可以是null.

原理：简单说就是链表数组结合体

对象的哈希值：普通的一个整数,可以理解为身份证号，是hashset存储的依据

HashSet按Hash算法来存储集合中的元素。在存取和查找上有很好的性能。

当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该hashCode值决定该hashCode值决定该对象在HashSet中存储的位置。

如果有两个元素通过equals()方法比较返回true,但它们的hashCode()方法返回值不相等,hashSet将会把它们存储在不同位置，依然可以添加成功。如果两个对象的hashCode()方法返回的hashCode值相同，当它们的equals()方法返回false时，会在hashCode所在位置采用链式结构保存多个对象。这样会降低hashSet的查询性能。

在使用HashSet中重写hashCode()方法的基本原则

1、在程序运行过过程中，同一个对象多次调用hashCode()方法应该返回相同的值。

2、当两个对象的equals()方法比较返回true时，这个两个对象的hashCode()方法返回相同的值。

3、对象中用作equals()方法比较标准的实例变量，都应该用于计算hashCode值。

把对象内的每个意义的实例变量(即每个参与equals()方法比较标准的实例变量)计算出一个int类型的hashCode值。用第1步计算出来的多个hashCode值组合计算出一个hashCode值返回

 return f1.hashCode()+(int)f2; 

为了避免直接相加产生的偶然相等(两个对象的f1、f2实例变量并不相等，但他们的hashCode的和恰好相等)，可以通过为各个实例变量的hashCode值乘以一个质数后再相加

 return f1.hashCode()*19+f2.hashCode()*37; 

如果向HashSet中添加一个可变的对象后，后面的程序修改了该可变对想的实例变量，则可能导致它与集合中的其他元素的相同（即两个对象的equals()方法比较返回true,两个对象的hashCode值也相等），这就有可能导致HashSet中包含两个相同的对象。

(12)Linkedhashset

LinkedHashSet : 具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序

 LinkedHashSet 综合了链表+哈希表，根据元素的hashCode值来决定元素的存储位置，它同时使用链表维护元素的次序。

当遍历该集合时候，LinkedHashSet 将会以元素的添加顺序访问集合的元素。

对于 LinkedHashSet 而言，它继承与 HashSet、又基于 LinkedHashMap 来实现的。

这个相对于HashSet来说有一个很大的不一样是LinkedHashSet是有序的。LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

与HashSet相比，特点：

对集合迭代时，按增加顺序返回元素。

性能略低于HashSet，因为需要维护元素的插入顺序。但迭代访问元素时会有好性能，因为它采用链表维护内部顺序。

LinkedHashSet不允许元素的重复

存储的顺序是元素插入的顺序。

(13)TreeSet

TreeSet : 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。

TreeSet 继承AbstractSet类，实现NavigableSet、Cloneable、Serializable接口。与HashSet是基于HashMap实现一样，TreeSet 同样是基于TreeMap 实现的。由于得到Tree 的支持，TreeSet 最大特点在于排序，它的作用是提供有序的Set集合。

用于对 Set 集合进行元素的指定顺序排序，排序需要依据元素自身具备的比较性。

如果元素不具备比较性，在运行时会抛出ClassCastException 异常。 所以元素需要实现Comparable 接口 ，让元素具备可比较性， 重写 compareTo 方法 。依据 compareTo 方法的返回值，确定元素在 TreeSet 数据结构中的位置。 或者用比较器方式，将Comparator对象传递给TreeSet构造器来告诉树集使用不同的比较方法

　

TreeSet底层的数据结构就是二叉树。

　不能写入空数据

写入的数据是有序的。

不写入重复数据

TreeSet方法保证元素唯一性的方式：就是参考比较方法的结果是否为0，如果return 0，视为两个对象重复，不存。

TreeSet集合排序有两种方式，Comparable和Comparator区别：

1：让元素自身具备比较性，需要元素对象实现Comparable接口，覆盖compareTo方法。

2：让集合自身具备比较性，需要定义一个实现了Comparator接口的比较器，并覆盖compare方法，并将该类对象作为实际参数传递给TreeSet集合的构造函数。

TreeSet类是SortedSet接口的实现类。因为需要排序，所以性能肯定差于HashSet。与HashSet相比，额外增加的方法有：

first()：返回第一个元素

last()：返回最后一个元素

lower(Object o)：返回指定元素之前的元素

higher(Obect o)：返回指定元素之后的元素

subSet(fromElement, toElement)：返回子集合

可以定义比较器（Comparator）来实现自定义的排序。默认自然升序排序。

TreeSet两种排序方式：自然排序和定制排序，默认情况下，TreeSet采用自然排序

TreeSet会调用集合元素的compareTo(Object object)方法来比较元素之间的大小关系，然后将元素按升序排列

如果试图把一个元素添加到TreeSet中，则该对象必须实现Comparable接口实现Comparable接口必须实现compareTo(Object object)，两个对象即通过这个方法进行比较Comparable的典型实现

BigDecimal、BigInteger以及所有的数值类型对应的包装类型，按对应的数值大小进行比较

Character：按字符的Unicode值进行比较

Boolean：true对应的包装类实例大于false包装类对应的实例

String：按字符对应的Unicode值进行比较

Date、Time：后面的时间、日期比前面的时间、日期大

向TreeSet中添加一个元素，只有第一个不需要使用compareTo()方法，后面的都要调用该方法

因为只有相同类的两个实例才会比较大小，所以向TreeSet中添加的应该是同一个类的对象

TreeSet采用红黑树的数据结构来存储集合元素

对于TreeSet集合而言，它判断两个对象的是否相等的唯一标准是:两个对象的通过compareTo(Object obj)方法比较是否返回0--如果通过compareTo(Object obj)方法比较返回0，TreeSet则会认为它们相等，否则认为它们不相等。对于语句，obj1.compareTo(obj2),如果该方法返回一个正整数，则表明obj1大于obj2;如果该方法返回一个负整数，则表明obj1小于obj2.

在默认的compareTo方法中，需要将的两个的类型的对象的转换同一个类型，因此需要将的保证的加入到TreeSet中的数据类型是同一个类型，但是如果自己覆盖compareTo方法时，没有要求两个对象强制转换成同一个对象，是可以成功的添加treeSet中

如果两个对象通过CompareTo(Object obj)方法比较返回0时，但它们通过equals()方法比较返回false时，TreeSet不会让第二个元素添加进去

(14)Map

Map主要用于存储健值对，根据键得到值，因此不允许键重复，但允许值重复。

Map接口概述：Java.util.Map<k,v>接口：是一个双列集合

Map集合的特点： 是一个双列集合，有两个泛型key和value，使用的时候key和value的数据类型可以相同。也可以不同.

Key不允许重复的，value可以重复的；

一个key只能对应一个value

底层是一个哈希表（数组+单向链表）：查询快，增删快, 是一个无序集合

Map接口中的常用方法：

1.get(key)  根据key值返回对应的value值，key值不存在则返回null

2.put(key , value); 往集合中添加元素（key和value）

　　注意：添加的时候，如果key不存在，返回值null

　　如果Key已经存在的话，就会新值替换旧值，返回旧值

3. remove(key); 删除key值对应的键值对；如果key不存在 ，删除失败。返回值为     null，如果key存在则删除成功，返回值为删除的value

Map遍历方式

第一种方式：通过key找value的方式：

　　　Map中有一个方法：

　　　　　　Set <k>  keySet();  返回此映射包含的键的Set 集合

　　　操作步骤:

　　　1.调用Map集合的中方法keySet,把Map集合中所有的健取出来,存储到Set集合中

　　   2.遍历Set集合,获取Map集合中的每一个健

　　　3.通过Map集合中的方法get(key),获取value值

　　　  可以使用迭代器跟增强for循环遍历

第二种方式：Map集合遍历键值方式

　　　　Map集合中的一个方法：

　　　　Set<Map.Entry<k,v>> entrySet(); 返回此映射中包含的映射关系的Set视图

　使用步骤

　　　　*  1.使用Map集合中的方法entrySet,把键值对(键与值的映射关系),取出来存储到Set  集合中

　　　　*  2.遍历Set集合,获取每一个Entry对象

　　　　*  3.使用Entry对象中的方法getKey和getValue获取健和值

　　可以使用迭代器跟增强for循环遍历

Collection中的集合元素是孤立的，可理解为单身，是一个一个存进去的，称为单列集合

Map中的集合元素是成对存在的，可理解为夫妻，是一对一对存进去的，称为双列集合

Map中存入的是：键值对，键不可以重复，值可以重复

Map主要用于存储带有映射关系的数据（比如学号与学生信息的映射关系）

Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

Map具有将对象映射到其他对象的功能，是一个K-V形式存储容器，你可以通过containsKey()和containsValue()来判断集合是否包含某个减或某个值。Map可以很容以拓展到多维（值可以是其他容器甚至是其他Map）：

Map<Object,List<Object>>

Map集合的数据结构仅仅针对键有效，与值无关。

(15)HashMap

HashMap非线程安全，高效，支持null；

根据键的HashCode 来存储数据，根据键可以直接获取它的值，具有很快的访问速度。遍历时，取得数据的顺序是完全随机的。

HashMap最多只允许一条记录的键为Null；允许多条记录的值为 Null。（不允许键重复，但允许值重复）

HashMap不支持线程的同步（任一时刻可以有多个线程同时写HashMap，即线程非安全），可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap() 方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

Hashtable与 HashMap类似。不同的是：它不允许记录的键或者值为空；它支持线程的同步（任一时刻只有一个线程能写Hashtable，即线程安全），因此也导致了 Hashtable 在写入时会比较慢。

HashMap里面存入的值在取出的时候是随机的，它根据键的HashCode来存储数据，根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。

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

值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

Map map = Collections.synchronizedMap(new HashMap());

HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

HashMap是常用的Java集合之一，是基于哈希表的Map接口的实现。与HashTable主要区别为不支持同步和允许null作为key和value。由于HashMap不是线程安全的，如果想要线程安全，可以使用ConcurrentHashMap代替。

HashMap的底层是哈希数组，数组元素为Entry。HashMap通过key的hashCode来计算hash值，当hashCode相同时，通过“拉链法”解决冲突

相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。原本Map.Entry接口的实现类Entry改名为了Node。转化为红黑树时改用另一种实现TreeNode。

1.8中最大的变化就是在一个Bucket中，如果存储节点的数量超过了8个，就会将该Bucket中原来以链表形式存储节点转换为以树的形式存储节点;而如果少于6个，就会还原成链表形式存储。

为什么要这样做？前面已经说过LinkedList的遍历操作不太友好，如果在节点个数比较多的情况下性能会比较差，而树的遍历效率是比较好的，主要是优化遍历，提升性能。

HashMap:去掉了contains(),保留了containsKey(),containsValue()

HashMap:key,value可以为空.null作为key只能有一个,null作为value可以存在多个

HashMap:使用Iterator

HashMap:数组初始大小为16,扩容方式为2的指数幂形式

HashMap:重新计算hash值

HashMap是基于哈希表的Map接口的实现，HashMap是一个散列表，存储的内容是键值对（key-value）映射，键值对都可为null；

HashMap继承自 AbstractMap<K, V> 并实现 Map<K, V>, Cloneable, Serializable接口；

HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。底层是个数组，数组上存储的数据是Entry<K,V>类型的链表结构对象。

HashMap是无序的，LinkedHashMap和treeMap是有序的；

HashMap基于哈希原理，可以通过put和get方法存储和获取对象。当我们将键值对传递给put方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到对应的bucket位置存储键对象和值对象作为Map.Entry；如果两个对象的hashcode相同，所以对应的bucket位置是相同的，HashMap采用链表解决冲突碰撞，这个Entry（包含有键值对的Map.Entry对象）会存储到链表的下一个节点中；如果对应的hashcode和key值都相同，则修改对应的value的值。HashMap在每个链表节点中存储键值对对象。当使用get()方法获取对象时，HashMap会根据键对象的hashcode去找到对应的bucket位置，找到对应的bucket位置后会调用keys.equals()方法去找到连表中对应的正确的节点找到对象。

HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口,能被克隆。

HashMap存数据的过程是：

HashMap内部维护了一个存储数据的Entry数组，HashMap采用链表解决冲突，每一个Entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexFor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头。

HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。

HashMap内存储数据的Entry数组默认是16，如果没有对Entry扩容机制的话，当存储的数据一多，Entry内部的链表会很长，这就失去了HashMap的存储意义了。所以HasnMap内部有自己的扩容机制。HashMap内部有：

变量size，它记录HashMap的底层数组中已用槽的数量；

变量threshold，它是HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）

变量DEFAULT_LOAD_FACTOR = 0.75f，默认加载因子为0.75

HashMap扩容的条件是：当size大于threshold时，对HashMap进行扩容

扩容是是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。 很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。

加载因子，如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。另外，无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方。

HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。

HashMap扩容时是当前容量翻倍即:capacity*2，Hashtable扩容时是容量翻倍+1即:capacity*2+1。

HashMap和Hashtable的底层实现都是数组+链表结构实现。

HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸：

static int hash(int h) {     

h ^= (h >>> 20) ^ (h >>> 12);     

return h ^ (h >>> 7) ^ (h >>> 4);

}

static int indexFor(int h, int length) {     

return h & (length-1);

}

HashMap多线程put操作后，get操作导致死循环。为何出现死循环？

大家都知道，HashMap采用链表解决Hash冲突，具体的HashMap的分析因为是链表结构，那么就很容易形成闭合的链路，这样在循环的时候只要有线程对这个HashMap进行get操作就会产生死循环。但是，我好奇的是，这种闭合的链路是如何形成的呢。在单线程情况下，只有一个线程对HashMap的数据结构进行操作，是不可能产生闭合的回路的。那就只有在多线程并发的情况下才会出现这种情况，那就是在put操作的时候，如果size>initialCapacity*loadFactor，那么这时候HashMap就会进行rehash操作，随之HashMap的结构就会发生翻天覆地的变化。很有可能就是在两个线程在这个时候同时触发了rehash操作，产生了闭合的回路。

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

HashMap存储自定义类型:使用HashMap储存自定义类形式，因为要保证key的唯一性。需要 自定义类重写  hashCode()跟equals()方法；

HashMap的方法基本都是Map中声明的方法

实现原理：实现一个哈希表，存储元素(key/value)时，用key计算hash值，如果hash值没有碰撞，则只用数组存储元素；如果hash值碰撞了，则相同的hash值的元素用链表存储；如果相同hash值超过8个，则相同的hash值的元素用红黑树存储。获取元素时，用key计算hash值，用hash值计算元素在数组中的下标，取得元素如果命中，则返回；如果不是就在红黑树或链表中找。

PS：存储元素的数组是有冗余的。

采用了Fail-Fast机制，通过一个modCount值记录修改次数，在迭代过程中，判断modCount跟初始过程记录的expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常；另外扩容过程中还有可能产生环形链表。

synchronized是针对整张Hash表的，即每次锁住整张表让线程独占

(16)HashTable

HashTable线程安全，低效，不支持null ,Hashtable是同步的

HashTable这个类实现了哈希表从key映射到value的数据结构形式。任何非null的对象都可以作为key或者value。

要在hashtable中存储和检索对象，作为key的对象必须实现hashCode、equals方法。

一般来说，默认的加载因子（0.75）提供了一种对于空间、时间消耗比较好的权衡策略。太高的值（指加载因子loadFactor）虽然减少了空间开销但是增加了检索时间，这反应在对hashtable的很多操作中，比如get、put方法。

初始容量的控制也是在空间消耗和rehash操作耗时(该操作耗时较大)二者之间的权衡。 如果初始容量大于哈希表的当前最大的条目数除以加载因子，则不会发生rehash。但是，将初始容量设置过高会浪费空间。

如果有大量的数据需要放进hashtable，则选择设置较大的初始容量比它自动rehash更优。

如果不需要线程安全的实现，建议使用HashMap代替Hashtable

如果想要一个线程安全的高并发实现，那么建议使用java.util.concurrent.ConcurrentHashMap取代了Hashtable。

HashTable的父类是Dictionary

HashTable:线程安全,HashTable方法有synchronized修饰

HashTable:保留了contains(),containsKey(),containsValue()

HashTable:key,value都不能为空.原因是源码中方法里会遍历entry,然后用entry的key或者value调用equals(),所以要先判断key/value是否为空,如果为空就会抛出异常

HashTable:使用Enumeration,Iterator

HashTable:数组初始大小为11,扩容方式为2*old+1

HashTable: 直接使用hashcode()

Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

Hashtable也是JDK1.0引入的类，是线程安全的，能用于多线程环境中。

Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模：

int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;

底层数据结构是哈希表,特点和 hashMap 是一样的

　　　　Hashtable 是线程安全的集合,是单线程的,运行速度慢

　　　　HashMap 是线程不安全的集合,是多线程的,运行速度快

　　　　Hashtable 命运和 Vector 是一样的,从 JDK1.2 开始,被更先进的 HashMap 取代

　　　　 HashMap 允许存储 null 值,null 健

　　　　Hashtable 不允许存储 null 值,null 健

　　　　 Hashtable 他的孩子,子类 Properties 依然活跃在开发舞台

Properties

Java.util.Properties 集合extends Hashtable<k,v> 集合

Properties 集合特点：

Properties集合也是一个双列集合，key跟value都已经被内置为String类型

Properties集合是一个唯一和IO流相结合的集合

可以将集合中存储的临时数据，持久化到硬盘的文件中储存

可以把文件中储存对的键值对，读取到集合中使用

Properties集合的基本操作：添加数据，遍历集合,Key和value都已经被内置为String类型。里面包含了一些和String类的相关方法

Object setProperty(String key ,String value) 往集合中添加键值对，调用Hashtable的方法put添加

String getProperty(String key ) 通过key获取value的值，相当于Map集合中的get(key) 方法

Set<String >   stringPropertyNames()返回此属性列表的键集。相当于Map集合中的keySet()方法；

Properties类的load方法：

可以把文件中存储的键值对,读取到集合中使用

void load(Reader reader)

void load(InputStream inStream)

参数:

Reader reader:字符输入流,可以使用FileReader

InputStream inStream:字节输入流,可以使用FileInputStream

操作步骤:

1.创建Properties集合对象

2.创建字符输入流FileReader对象,构造方法中绑定要读取的数据源

3.使用Properties集合中的方法load,把文件中存储的键值对,读取到集合中使   用

4.释放资源

5.遍历Properties集合

注意:

1.流使用Reader字符流,可以读取中文数据

2.流使用InputStream字节流,不能操作中文,会有乱码

3.Properties集合的配置文件中,可以使用注释单行数据,使用#

4.Properties集合的配置文件中,key和value默认都是字符串,不用添加""(画蛇   添足)

5.Properties集合的配置文件中,key和value的连接符号可以使用=,也可以使用   空格

Properties类的store方法使用：

可以把集合中存储的临时数据,持久化都硬盘的文件中存储

void store(Writer writer, String comments)

void store(OutputStream out, String comments)

参数:

Writer writer:字符输出流,可以使用FileWriter

OutputStream out:字节输出流,可以使用FileOutputStream

String comments:注释,解释说明存储的文件,不能使用中文(乱码),默认编码格式为   Unicode编码

可以使用""空字符串

操作步骤:

1.创建Properties集合,往集合中添加数据

2.创建字符输出流FileWriter对象,构造方法中绑定要写入的目的地

3.调用Properties集合中的方法store,把集合中存储的临时数据,持久化都硬盘的文  件中存储

4.释放资源

注意:

1.流使用Writer字符流,可以写入中文数据的

2.流使用OutputStream字节流,不能操作中文,会有乱码

3.Propertie集合存储的文件,一般都以.properties结尾(程序员默认)

(17)LinkeHashMap

LinkedHashMap继承自HashMap，实现了Map<K,V>接口。其内部还维护了一个双向链表，在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。

默认情况，遍历时的顺序是按照插入节点的顺序。这也是其与HashMap最大的区别。

也可以在构造时传入accessOrder参数，使得其遍历顺序按照访问的顺序输出。

LinkedHashMap在实现时，就是重写override了几个方法。以满足其输出序列有序的需求。

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。

在遍历的时候会比HashMap慢，不过有种情况例外：当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢。因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和它的容量有关。

LinkedHashMap是HashMap的子类，保存了插入的顺序，需要输出的顺序和输入的顺序相同时可用LinkedHashMap；

LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现.

LinkedHashMap取键值对时，是按照你放入的顺序来取的。

LinkedHashMap由于它的插入有序特性，也是一种比较常用的Map集合。它继承了HashMap，很多方法都直接复用了父类HashMap的方法。本文将探讨LinkedHashMap的内部实现，以及它是如何保证插入元素是按插入顺序排序的。

在分析前可以先思考下，既然是按照插入顺序，并且以Linked-开头，就很有可能是链表实现。如果纯粹以链表实现，也不是不可以，LinkedHashMap内部维护一个链表，插入一个元素则把它封装成Entry节点，并把它插入到链表尾部。功能可以实现，但这带来的查找效率达到了O(n)，显然远远大于HashMap在没有冲突的情况下O(1)的时间复杂度。这就丝毫不能体现出Map这种数据结构随机存取快的优点。

所以显然，LinkedHashMap不可能只有一个链表来维护Entry节点，它极有可能维护了两种数据结构：散列表+链表。

　

LinkedHashMap的LRU特性

先讲一下LRU的定义：LRU(Least Recently Used),即最近最少使用算法，最初是用于内存管理中将无效的内存块腾出而用于加载数据以提高内存使用效率而发明的算法。

目前已经普遍用于提高缓存的命中率，如Redis、Memcached中都有使用。

为啥说LinkedHashMap本身就实现了LRU算法？原因就在于它额外维护的双向链表中。

在上面已经提到过，在做get/put操作时，LinkedHashMap会将当前访问/插入的节点移动到链表尾部，所以此时链表头部的那个节点就是 "最近最少未被访问"的节点。

举个例子：

往一个空的LinkedHashMap中插入A、B、C三个结点，那么链表会经历以下三个状态：

1.  A   插入A节点，此时整个链表只有这一个节点，既是头节点也是尾节点

2.  A  ->  B   插入B节点后，此时A为头节点，B为尾节点，而最近最常访问的节点就是B节点（刚被插入），而最近最少使用的节点就是A节点（相对B节点来讲，A节点已经有一段时间没有被访问过）

3.  A  ->  B  ->  C  插入C节点后，此时A为头节点，C为尾节点，而最近最常访问的节点就是C节点（刚被插入），最近最少使用的节点就是A节点 （应该很好理解了吧  : )）

那么对于缓存来讲，A就是我最长时间没访问过的缓存，C就是最近才访问过的缓存，所以当缓存队列满时就会从头开始替换新的缓存值进去，从而保证缓存队列中的缓存尽可能是最近一段时间访问过的缓存，提高缓存命中率。

LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

(18)TreeMap

TreeMap实现SortMap接口，能够把它保存的记录根据键排序。

默认是按键的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

TreeMap是基于红黑树结构实现的一种Map，要分析TreeMap的实现首先就要对红黑树有所了解。

要了解什么是红黑树，就要了解它的存在主要是为了解决什么问题，对比其他数据结构比如数组，链表，Hash表等树这种结构又有什么优点。

treeMap实现了sortMap接口，能够把保存的数据按照键的值排序，默认是按照自然数排序也可自定义排序方式。

TreeMap对键进行排序了。

当用Iterator遍历TreeMap时，得到的记录是排过序的。

如果使用排序的映射，建议使用TreeMap。

在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

二叉树插入元素是有顺序的，TreeSet的元素是有序的。

由于二叉树需要对结点排序（插入的结点位置），默认情况下没有排序方法，所以元素需要继承Comparator并重写compareTo方法来实现元素之间比较大小的功能。

对于TreeSet，compareTo方法来保证元素的唯一性。【这时候可以不重写equals】

二叉树需要结点排序，所以元素之间比较能够比较，所以对于自定义元素对象，需要继承Comparator并重写的compareTo方法。 两个元素相等时，compareTo返回0；左大于右时，返回正整数（一般返回1）;小于时返回负整数（一般返回-1）

TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n)

TreeMap中默认的排序为升序

使用entrySet遍历方式要比keySet遍历方式快

entrySet遍历方式获取Value对象是直接从Entry对象中直接获得，时间复杂度T(n)=o(1);

keySet遍历获取Value对象则要从Map中重新获取，时间复杂度T(n)=o(n);keySet遍历Map方式比entrySet遍历Map方式多了一次循环，多遍历了一次table，当Map的size越大时，遍历的效率差别就越大。

HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

在Map 中插入、删除和定位元素，HashMap是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。

TreeMap 底层数据结构是红黑树(一种自平衡的二叉树) ，其根据比较的返回值是否是0来保证元素唯一性， 元素的排序通过两种方式：第一种是自然排序(元素具备比较性) 即让元素所属的类实现Comparable接口，第二种是比较器排序(集合具备比较性) ，即让集合接收一个Comparator的实现类对象。

Comparable 和 Comparator 的区别：

　　Comparable 是一个比较的标准，里面有比较的方法，对象要具有比较的标准，就必须实现 Comparable 接口；类实现这个接口，就有比较的方法；把元素放到 TreeSet 里面去，就会自动的调用 CompareTo 方法；但是这个 Comparable  并不是专为 TreeSet 设计的；只是说，TreeSet 顺便利用而已；就像 HashCode 和 equals  也一样，不是专门为 HashSet 设计一样；只是你顺便利用而已。

　　Compartor 是个比较器，也不是专门为TreeSet设计. 就是一个第三方的比较器接口；如果对象没有比较性，自己就可以按照比较器的标准，设计一个比较器，创建一个类，实现这个接口，覆写方法。

(18)Queue

Queue用于模拟队列这种数据结构，实现“FIFO”等数据结构。即第一个放进去就是第一个拿出来的元素（从一端进去，从另一端出来）。队列常作被当作一个可靠的将对象从程序的某个区域传输到另一个区域的途径。通常，队列不允许随机访问队列中的元素。

Queue 接口并未定义阻塞队列的方法，而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法，这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

LinkedList提供了方法以支持队列的行为，并且实现了Queue接口。通过LinkedList向上转型（up cast）为Queue，看Queue的实现就知道相对于LinkedList，Queue添加了element、offer、peek、poll、remove方法

offer：在允许的情况下，将一个元素插入到队尾，或者返回false

peek，element：在不移除的情况下返回队头，peek在队列为空返回null，element抛异常NoSuchElementException

poll,remove：移除并返回队头，poll当队列为空是返回null，remove抛出NoSuchElementException异常

注意：queue.offer在自动包装机制会自动的把random.nextInt转化程Integer，把char转化成Character

(19)Deque

Deque是Queue的子接口,我们知道Queue是一种队列形式,而Deque则是双向队列,它支持从两个端点方向检索和插入元素,因此Deque既可以支持LIFO形式也可以支持LIFO形式.Deque接口是一种比Stack和Vector更为丰富的抽象数据形式,因为它同时实现了以上两者.

添加功能

void push(E) 向队列头部插入一个元素,失败时抛出异常

void addFirst(E) 向队列头部插入一个元素,失败时抛出异常

void addLast(E) 向队列尾部插入一个元素,失败时抛出异常

boolean offerFirst(E) 向队列头部加入一个元素,失败时返回false

boolean offerLast(E) 向队列尾部加入一个元素,失败时返回false

获取功能

E getFirst() 获取队列头部元素,队列为空时抛出异常

E getLast() 获取队列尾部元素,队列为空时抛出异常

E peekFirst() 获取队列头部元素,队列为空时返回null

E peekLast() 获取队列尾部元素,队列为空时返回null

删除功能

boolean removeFirstOccurrence(Object) 删除第一次出现的指定元素,不存在时返回false

boolean removeLastOccurrence(Object) 删除最后一次出现的指定元素,不存在时返回false

弹出功能

E pop() 弹出队列头部元素,队列为空时抛出异常

E removeFirst() 弹出队列头部元素,队列为空时抛出异常

E removeLast() 弹出队列尾部元素,队列为空时抛出异常

E pollFirst() 弹出队列头部元素,队列为空时返回null

E pollLast() 弹出队列尾部元素,队列为空时返回null

迭代器

Iterator<E> descendingIterator() 返回队列反向迭代器

同Queue一样,Deque的实现也可以划分成通用实现和并发实现.

　　通用实现主要有两个实现类ArrayDeque和LinkedList.

　　ArrayDeque是个可变数组,它是在Java 6之后新添加的,而LinkedList是一种链表结构的list,LinkedList要比ArrayDeque更加灵活,因为它也实现了List接口的所有操作,并且可以插入null元素,这在ArrayDeque中是不允许的.

　　从效率来看,ArrayDeque要比LinkedList在两端增删元素上更为高效,因为没有在节点创建删除上的开销.最适合使用LinkedList的情况是迭代队列时删除当前迭代的元素.此外LinkedList可能是在遍历元素时最差的数据结构,并且也LinkedList占用更多的内存,因为LinkedList是通过链表连接其整个队列,它的元素在内存中是随机分布的,需要通过每个节点包含的前后节点的内存地址去访问前后元素.

　　总体ArrayDeque要比LinkedList更优越,在大队列的测试上有3倍与LinkedList的性能,最好的是给ArrayDeque一个较大的初始化大小,以避免底层数组扩容时数据拷贝的开销.

　　LinkedBlockingDeque是Deque的并发实现,在队列为空的时候,它的takeFirst,takeLast会阻塞等待队列处于可用状态

(20)Stack

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得 Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

栈，是指“LIFO”先进后出的集合容器，最后一个压入的元素是第一个出来的，就好比我们洗碗一样（或者叠罗汉）第一个摆放的碗放在最下面，自然是最后一个拿出来的。Stack是由LinkedList实现的，作为Stack的实现，下面是《java编程思想》给出基本的Stack实现：

peek和pop是返回T类型的对象。peek方法提供栈顶元素，但不删除栈顶，而pop是返回并删除栈顶元素;

(20)ArrayDeque

ArrayDeque类是双端队列的实现类，类的继承结构如下面，继承自AbastractCollection（该类实习了部分集合通用的方法，其实现了Collection接口），其实现的接口Deque接口中定义了双端队列的主要的方法，比如从头删除，从尾部删除，获取头数据，获取尾部数据等等。

public class ArrayDeque<E> extends AbstractCollection<E>                           implements Deque<E>, Cloneable, Serializable

ArrayDeque基本特征

就其实现而言，ArrayDeque采用了循环数组的方式来完成双端队列的功能。

1. 无限的扩展，自动扩展队列大小的。（当然在不会内存溢出的情况下。）

2. 非线程安全的，不支持并发访问和修改。

3. 支持fast-fail.

4. 作为栈使用的话比比栈要快.

5. 当队列使用比linklist要快。

6. null元素被禁止使用。

最小初始化容量限制8(必须是2的幂次)

扩容:之所以说该ArrayDeque容量无限制，是因为只要检测到head==tail的时候，就直接调用doubleCapacity方法进行扩容。

删除元素:删除元素的基本思路为确定那一侧的数据少，少的一侧移动元素位置，这样效率相对于不比较更高些，然后，判断head是跨越最大值还是为跨越最大值，继而可以分两种不同的情况进行拷贝。但是该方法比较慢，因为存在数组的拷贝。

获取并删除元素:这里在举个简单点的例子，中间判断是不是null，可以看出该队列不支持null,通过把其值设为null就算是将其删除了。然后head向递增的方向退一位即可。

ArrayDeque和LinkedList是Deque的两个通用实现

ArrayDeque不是线程安全的。

ArrayDeque不可以存取null元素，因为系统根据某个位置是否为null来判断元素的存在。

当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

1.添加元素        addFirst(E e)在数组前面添加元素        addLast(E e)在数组后面添加元素        offerFirst(E e) 在数组前面添加元素，并返回是否添加成功        offerLast(E e) 在数组后天添加元素，并返回是否添加成功  2.删除元素        removeFirst()删除第一个元素，并返回删除元素的值,如果元素为null，将抛出异常        pollFirst()删除第一个元素，并返回删除元素的值，如果元素为null，将返回null           removeLast()删除最后一个元素，并返回删除元素的值，如果为null，将抛出异常        pollLast()删除最后一个元素，并返回删除元素的值，如果为null，将返回null           removeFirstOccurrence(Object o) 删除第一次出现的指定元素        removeLastOccurrence(Object o) 删除最后一次出现的指定元素      3.获取元素        getFirst() 获取第一个元素,如果没有将抛出异常        getLast() 获取最后一个元素，如果没有将抛出异常       4.队列操作        add(E e) 在队列尾部添加一个元素        offer(E e) 在队列尾部添加一个元素，并返回是否成功        remove() 删除队列中第一个元素，并返回该元素的值，如果元素为null，将抛出异常(其实底层调用的是removeFirst())           poll()  删除队列中第一个元素，并返回该元素的值,如果元素为null，将返回null(其实调用的是pollFirst())           element() 获取第一个元素，如果没有将抛出异常        peek() 获取第一个元素，如果返回null          5.栈操作        push(E e) 栈顶添加一个元素        pop(E e) 移除栈顶元素,如果栈顶没有元素将抛出异常            6.其他        size() 获取队列中元素个数        isEmpty() 判断队列是否为空        iterator() 迭代器，从前向后迭代        descendingIterator() 迭代器，从后向前迭代        contain(Object o) 判断队列中是否存在该元素        toArray() 转成数组        clear() 清空队列        clone() 克隆(复制)一个新的队列

(22)PriorityQueue

我们知道队列是遵循先进先出（First-In-First-Out）模式的，但有些时候需要在队列中基于优先级处理对象。举个例子，比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，Java的PriorityQueue(优先队列)会很有帮助。

PriorityQueue类在Java1.5中引入并作为 Java Collections Framework 的一部分。PriorityQueue是基于优先堆的一个*队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。

优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。

PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。

由于知道PriorityQueue是基于Heap的，当新的元素存储时，会调用siftUpUsingComparator方法

PriorityQueue的逻辑结构是一棵完全二叉树，存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组。

PriorityQueue优先队列,它逻辑上使用堆结构（完全二叉树）实现，物理上使用动态数组实现，并非像TreeMap一样完全有序，但是如果按照指定方式出队，结果可以是有序的。

这里的堆是一种数据结构而非计算机内存中的堆栈。堆结构在逻辑上是完全二叉树，物理存储上是数组。

完全二叉树并不是堆结构，堆结构是不完全有序的完全二叉树。

(23)BlockingQueue

Java中Queue的最重要的应用大概就是其子类BlockingQueue了。

考虑到生产者消费者模型，我们有多个生产者和多个消费者，生产者不断提供资源给消费者，但如果它们的生产/消费速度不匹配或者不稳定，则会造成大量的生产者闲置/消费者闲置。此时，我们需要使用一个缓冲区来存储资源，即生产者将资源置于缓冲区，而消费者不断地从缓冲区中取用资源，从而减少了闲置和阻塞。

BlockingQueue，阻塞队列，即可视之为一个缓冲区应用于多线程编程之中。当队列为空时，它会阻塞所有消费者线程，而当队列为满时，它会阻塞所有生产者线程。

在queue的基础上，BlockingQueue又添加了以下方法：

put：队列末尾添加一个元素，若队列已满阻塞。

take：移除并返回队列头部元素，若队列已空阻塞。

drainTo:一次性获取所有可用对象，可以用参数指定获取的个数，该操作是原子操作，不需要针对每个元素的获取加锁。

(24) ArrayBlockingQueue

由一个定长数组和两个标识首尾的整型index标识组成，生产者放入数据和消费者取出数据对于ArrayBlockingQueue而言使用了同一个锁（一个私有的ReentrantLock），因而无法实现真正的并行。可以在初始化时除长度参数以外，附加一个boolean类型的变量，用于给其私有的ReentrantLock进行初始化（初始化是否为公平锁，默认为false）。

(25) LinkedBlockingQueue

LinkedBlockingQueue的最大特点是，若没有指定最大容量，其可以视为*队列（有默认最大容量限制,往往系统资源耗尽也无法达到）。即，不对生产者的行为加以限制，只在队列为空的时候限制消费者的行为。LinkedBlockingQueue采用了读写分离的两个ReentrantLock去控制put和take，因而有了更好的性能（类似读写锁提供读写场景下更好的性能），如下：

/** Lock held by take, poll, etc */    private final ReentrantLock takeLock = new ReentrantLock();    /** Wait queue for waiting takes */    private final Condition notEmpty = takeLock.newCondition();    /** Lock held by put, offer, etc */    private final ReentrantLock putLock = new ReentrantLock();    /** Wait queue for waiting puts */    private final Condition notFull = putLock.newCondition();

ArrayBlockingQueue和LinkedBlockingQueue是最常用的两种阻塞队列。

(26) PriorityBlockingQueue

PriorityBlockingQueue是对PriorityQueue的包装，因而也是一个优先队列。其优先级默认是直接比较，大者先出队，也可以从构造器传入自定义的Comparator。由于PriorityQueue从实现上是一个*队列，PriorityBlockingQueue同样是一个*队列，对生产者不做限制。

(27) DelayQueue

DelayQueue是在PriorityBlockingQueue的基础上包装产生的，它用于存放Delayed对象，该队列的头部是延迟期满后保存时间最长的Delayed元素（即，以时间为优先级利用PriorityBlockingQueue），当没有元素延迟期满时，对其进行poll操作将会返回Null。take操作会阻塞。

(28) SynchronousQueue

SynchronousQueue十分特殊，它没有容量——换言之，它是一个长度为0的BlockingQueue，生产者和消费者进行的是无中介的直接交易，当生产者/消费者没有找到合适的目标时，即会发生阻塞。但由于减少了环节，其整体性能在一些系统中可能更加适合。该方法同样支持在构造时确定为公平/默认的非公平模式，如果是非公平模式，有可能会导致某些生产者/消费者饥饿。

(29)WeakHashMap

WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

(30)EnumSet类

EnumSet是一个专门为枚举设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值，该枚举类型的创建Enumset时显示会隐式的指定。Enumset的集合元素也是有序的，EnumSet以枚举值在Enum类内定义的顺序来决定集合元素的顺序。

(31)使用Java8新增的Predicate操作集合

Java 8为Collection集合新增了removeIf(Predicate filter)方法，该方法将会批量删除符合条件的filter条件的所有元素

(32)使用java 8 新增的Stream操作集合

Java8新增了Stream、IntStream、LongStream、DoubleStream等流式API，这些API代表了多个支持串行和并行聚集操作的元素，其中Stream是一个通用的流接口，而IntStream、LongStream、DoubleStream则代表了类型为int，long，double的流。

独立使用Stream的步骤如下:

1、使用Stream或XxxStream的builder()类方法创建该Stream对应的Builder。

2、重复调用Builder的add()方法向该流中的添加多个元素

3、调用Builder的build()方法获取对应的Stream

4、调用Stream的聚集方法。

在Stream中方法分为两类中间方法和末端方法

中间方法：中间操作允许流保持打开状态,并允许直接调用后续方法。上面程序中的map()方法就是中间方法。

末端方法：末端方法是对流的最终操作。当对某个Stream执行末端方法后，该流将会被"消耗"且不再可用。上面程序中的sum()、count()、average()等方法都是末端方法。

除此之外，关于流的方法还有如下特征：

有状态的方法：这种方法会给你流增加一些新的属性，比如元素的唯一性、元素的最大数量、保证元素的排序的方式被处理等。有状态的方法往往需要更大的性能开销

短路方法:短路方法可以尽早结束对流的操作，不必检查所有的元素。