集合框架（怎么实现、适用场景） hash相关
其中Set代表无序、不可重复的集合；List代表有序、重复的集合；而Map则代表具
有映射关系的集合。Java 5 又增加了Queue体系集合，代表一种队列集合实现。
1.Java集合和数组的区别：
①.数组长度在初始化时指定，意味着只能保存定长的数据。而集合可以保存数量不
确定的数据。同时可以保存具有映射关系的数据（即关联数组，键值对 keyvalue）。
②.数组元素即可以是基本类型的值，也可以是对象。集合里只能保存对象（实际上
只是保存对象的引用变量），基本数据类型的变量要转换成对应的包装类才能放入
集合类中。
Java集合框架
集合类主要分为两大类：Collection和Map
Collection-List接口通常表示一个列表（数组、队列、链表、栈等），其中的元素可以重复，常用实现类为ArrayList和LinkedList，另外还有不常用的Vector。
Map-Set接口通常表示一个集合，其中的元素不允许重复（通过hashcode和equals函数保证），常用实现类有HashSet和TreeSet，HashSet是通过Map中的HashMap实现的，而TreeSet是通过Map中的TreeMap实现的。
所有的集合类都必须能提供友好的交互操作，采用了适配器模式，这包括没有继承Collection类的数组对象。因此，框架提供一套方法，让集合类与数组可以相互转化，并且可以把Map看作成集合。
Map
Map并不是一个真正意义上的集合，但是这个接口提供了三种“集合视角”，使得可以像操作集合一样操作它们，具体如下：
- 把map的内容看作key的集合
- 把map的内容看作value的集合
- 把map的内容看作key-value映射的集合
树是一种由节点组成的数据结构，每个节点都包含数据元素，并且有一个或多个子节点，每个子节点指向一个父节点（除了根节点）可以表示层级关系或者数据元素的顺序关系。常用的场景有表示一个组织里的雇员层级关系，XML元素的层级关系，等等。如果树的每个子节点最多有两个叶子节点，那么这种树被称为二叉树。二叉树是一种非常常用的树形结构， 因为它的这种结构使得节点的插入和删除都非常高效。树的边表示从一个节点到另外一个节点的快捷路径。
二叉树的递归遍历 P114
先中后
平衡二叉树
任意子树都满足|左深度-右深度|<=1的二叉树
B-树 P221
B-树是一种平衡多路查找树。一棵m阶B-树，具有下列性质：
（1）树中每个节点至多有m棵子树；
（2）若根节点不是叶子节点，则至少有2棵子树；
（3）除根节点之外的所有非终端节点至少有[m/2]棵子树；
（4）每个节点中的信息结构为（n,A0,K1,A1,K2......Kn,An），其中n表示关键字个数，Ki为关键字，Ai为只想字数根节点的指针；（指针A(i-1)所指子树中所有节点的关键字均小于Ki，An所指字数中所有节点的关键字均大于Kn）
（5）所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。
hash相关
散列表（Hash table，也叫哈希表），是依据键值(Key value)直接进行访问的数据结构。它通过把键值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
什么叫冲突
key1！= key2，但是value1 = value2
解决冲突的办法：
（1）线性探查法：冲突后，线性向前试探，找到近期的一个空位置。缺点是会出现堆积现象。存取时，可能不是同义词的词也位于探查序列，影响效率。（“同义词”：两个元素通过散列函数得到的地址同样）
（2）双散列函数法：在位置d冲突后，再使用另一个散列函数产生一个与散列表桶容量m互质的数c，依次试探(d+n*c)%m，使探查序列跳跃式分布。
Hash算法在信息安全方面的应用
（1) 文件校验（MD5 Hash算法的”数字指纹”特性，使它成为眼下应用最广泛的一种文件完整性校验算法）
（2) 数字签名（对 Hash 值，又称”数字摘要”进行数字签名，在统计上能够觉得与对文件本身进行数字签名是等效的）
（3) 鉴权协议（在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法）
