学习——数据结构

数组

线性表

顺序表

ArrayList

Iterator

链表

单链表

双链表

LInkList

队列

堆栈

树

N个结点构成的有限集合

结点的度：结点的子树个数

二叉树：度为2的树

二叉排序树：左子树的所有的值小于根节点的值；右子树的所有的值大于根节点的值

平衡二叉树：左右结点的高度差不超过1的二叉排序树

需要旋转调整

哈夫曼树（最优二叉树）：加权路径最小的二叉树

红黑树：（特殊的二叉树）（性能更优）

需要旋转调整、变色

从根到叶子的最长的路径不多于最短的可能路径的两倍长

图论

图由顶点（vertex）和边（edge）组成的一种结构。

邻接矩阵（二维数组）

图的遍历

1、深度优先算法

2、广度优先算法

图的最短路径树

关键路径

AVO网络拓扑排序

排序和查找

排序算法

十大排序算法：

冒泡排序，简单选择排序，简单插入排序，归并排序，堆排序，快速排序、希尔排序、计数排序，基数排序，桶排序

时间复杂度、空间复杂度

 快速排序  综合来说性能最好，用的最多

选择的基准，三取样划分和Dual-Pivot快排        

但是一般排序规模较小时，会改用插入排序或者其他排序算法

 查找

二分查找（折半查找）

内存缓存淘汰机制

1.FIFO （First In, First Out）

2.LFU (Least Frequently Used)        

3.LRU (Least Recently Used)

HashMap

顺序表和链表

Hash

Hash冲突

负载因子 0.75

问题：

布隆过滤器

是1970年由布隆提出的，布隆过滤器可以用于检索一个元素是否在一个集合中，因此它是一个空间效率极高的概率型算法；它实际上是一个很长的二进制向量和一系列随机映射函数；

优点：

仅仅保留数据的指纹信息，空间效率极高；

查询效率极高，时间复杂度为：O（n）；

信息安全性较高；

不足：

存在一定的误判；（可以控制误判率）

数据删除困难；

Google Guava实现了布隆过滤器！