(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**了。<br /><br />
对于情况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发生，这要看具体情况了。
(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
Iterable接口包含一个能产生Iterator对象的方法，并且Iterable被foreach用来在序列中移动。因此如果创建了实现Iterable接口的类，都可以将它用于foreach中。
定义:
Package java.lang; import java.util.Iterator; public interface Iterable
Iterable是Java 1.5的新特性, 主要是为了支持forEach语法, 使用容器的时候, 如果不关心容器的类型, 那么就需要使用迭代器来编写代码. 使代码能够重用.
使用方法很简单:
List
好处：代码减少，方便遍历
弊端：没有索引，不能操作容器里的元素
增强for循环底层也是使用了迭代器获取的，只不过获取迭代器由jvm完成，不需要我们获取迭代器而已，所以在使用增强for循环变量元素的过程中不准使用集合对象对集合的元素个数进行修改；
[4].forEach()(1.8)
使用接收lambda表达式的forEach方法进行快速遍历.
List
[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的方法名称都比较长。
迭代器的好处：屏蔽了集合之间的不同，可以使用相同的方式取出
(6).集合类的作用
集合类也叫做容器类，和数组一样，用于存储数据，但数组类型单一，并且长度固定，限制性很大，而集合类可以动态增加长度。
集合存储的元素都是对象(引用地址)，所以集合可以存储不同的数据类型，但如果是需要比较元素来排序的集合，则需要类型一致。
集合中提供了统一的增删改查方法，使用方便。
支持泛型，避免数据不一致和转换异常，还对常用的数据结构进行了封装。
所有的集合类的都在java.util包下。
**
(7)集合框架体系的组成
集合框架体系是由Collection、Map(映射关系)和Iterator(迭代器)组成，各部分的作用如下所示。
[1]Collection体系中有三种集合：Set、List、Queue
Set(集)： 元素是无序的且不可重复。
List(列表)：元素是有序的且可重复。
Queue(队列)：封装了数据结构中的队列。
[2]Map体系
Map用于保存具有映射关系的数据，即key-value(键值对)。Map集合的key是唯一的，不可重复，而value可以重复。所以一个value可以对应多个key。
Map体系除了常用类之外，还有Properties（属性类）也属于Map体系。
**
(8)Collection的由来
由于数组中存放对象，对对象操作起来不方便。java中有一类容器，专门用来存储对象。
集合可以存储多个元素,但我们对多个元素也有不同的需求
多个元素,不能有相同的
多个元素,能够按照某个规则排序
针对不同的需求：java就提供了很多集合类，多个集合类的数据结构不同。但是，结构不重要，重要 的是能够存储东西,能够判断,获取.
把集合共性的内容不断往上提取,最终形成集合的继承体系——>Collection
并且所有的Collection实现类都重写了toString()方法.
(9)集合和数组
集合与数组的区别：
1.数组的长度固定的，而集合长度时可变的
2.数组只能储存同一类型的元素，而且能存基本数据类型和引用数据类型。集合可以存储不同类型的元素，只能存储引用数据类型
集合类和数组不一样,数组元素既可以是基本类型的值,也可以是对象(实际上保存的是对象的引用变量);而集合只能保存对象。
数组和集合的主要区别包括以下几个方面：
一：数组声明了它容纳的元素的类型，而集合不声明。这是由于集合以object形式来存储它们的元素。
二：一个数组实例具有固定的大小，不能伸缩。集合则可根据需要动态改变大小。
三：数组是一种可读/可写数据结构没有办法创建一个只读数组。然而可以使用集合提供的ReadOnly方 只读方式来使用集合。该方法将返回一个集合的只读版本。
集合的作用：
如果一个类的内部有很多相同类型的属性，并且他们的作用与意义是一样的，比如说学生能选课学生类就有很多课程类型的属性，或者工厂类有很多机器类型的属性，我们用一个类似于容器的集合去盛装他们，这样在类的内部就变的井然有序————-这就是：
- 在类的内部，对数据进行组织的作用。
- 简单而快速的搜索查找其中的某一条元素
- 有的集合接口，提供了一系列排列有序的元素，并且可以在序列中间快速的插入或者删除有关元素。
- 有的集合接口在其内部提供了映射关系的结构，可以通过关键字(key)去快速查找对应的唯一对象，而这个关键可以是任意类型的。
若有收获，就点个赞吧
0 人点赞
