List特点：元素有放入顺序，元素可重复，用来处理序列

Map特点：元素按键值对存储，无放入顺序. key-value

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

Map接口有三个实现类：HashMap，HashTable，LinkeHashMap，SortedMap有一个实现类：TreeMap。

Map UML:

ArrayList查找性能优秀，但是增删较慢，LinkedList则相反。

LinkedList既实现了List又实现了queue，它的内部实现是一个双向链表。

继承关系

Queue是一个超级接口，继承关系如下：

有如下方法：

Java集合是我么最经常使用的工具，我们称这些集合类为容器，和数组的不同： 数组长度固定，集合类长度可变，数组存放基本类型，集合类存放对象的引用。

常用集合： List， Set， Map。

Collection UML:

要学习Collection，除了数据结构基础之外还要有Iterable概念

Iterable

哈希表

哈希表在时间和空间上做出权衡，在很多情况下是简单符号表的最佳选择。
如果我们不受时间限制，可以用顺序查找的方式查找一个无序的数组，以降低空间成本，如果我们不考虑空间，将键值完全散列，以键值作为数组的索引，我们就能达到O（1）的访问速度。我们通过改变哈希表的参数来在空间和时间上做出取舍。

前面学习到的几种算法比如红黑树，二叉搜索树，查找插入时间复杂度最快也只能到O(logn)，散列表查找插入时间复杂度达到常数级别，但是需要牺牲一定的计算索引的时间。

二叉查找树最坏情况下的时间和树的高度成正比（O(n)），所以当最坏情况的性能还是很糟糕，所以我们可以用AVL、红黑树等数据结构，能保证无论如何构造他她的运行时间都是对数级（树的高度是LogN）

平衡二叉树（AVL）

定义：
父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增。

高效检索信息是处理海量信息的前提，二分查找适用的数据结构是有序数组，还有二叉查找树，红黑树，和散列表三种数据类型来实现高效的查找。

二分查找

二分查找一个有序的数组,复杂度O(logn)

java实现：

求二叉树的节点数

递归子问题：二叉树的节点数等于根+左子树的节点数+右子树的节点数。

递归终止条件：root == null，即该子树已经遍历结束

1
2
3
4
5
6

public int nodeCount(biNode root){
    if (root == null)
        return 0;
    return nodeCount(root.left)+nodeCount(root.right)+1;

}

熟悉了javascript，开始写java发现如下写法不能通过编译，因为这里root.value是Object，而’ ‘是一个char类型（基本类型),使用+运算符的时候由于类型不匹配产生错误。

在这种上下文环境中，(+) 号意味着 “字符串的连接”，并且如果必要他还执行字符串的转换。规则如下：当编译器观察到一个 String 后面紧跟着一个 (+) 号，而这个 (+) 号后面又紧跟着一个非 String 类型的元素时，就会尝试着将这个非 String 类型的参数转换为 String 类型。而我的代码中编译器不会把字符看作字符串，就不会进行类型转换，发生错误。

而这样写在js中是没有问题的。

因为

二叉树是一种树形数据结构，它的每个节点最多有两个孩子，被叫作左孩子和右孩子。二叉树可以用于二叉查找，哈夫曼树等算法。

常见特殊二叉树：

满二叉树