经典数据结构和算法小结

Tree

Hash

布隆过滤器

（查找一条记录是否在海量数据中出现过）例如：一百万条数据记录比如黑名单，随便给你一条记录问在不在黑名单中，怎么做？

一致性哈希

Graph

遍历

DFS

BFS

SortTopology

要求必须为有向无环图，并且有入度为0的节点。算法思想：每次把入度为0的节点输出并标记为该节点已经访问，同时将入度为0的节点的下一个节点入度减去1。然后输出。循环这个过程直到没有入度为0的节点。

最短路径

Dijkstra

Bellman-Ford

最小生成树

Prim

算法步骤：从任一节点开始，每次找一条最小的边，这条边必须满足之前没有被添加到最小生成树中。

1. 取一个节点node。同时将node的边信息加入一个最小堆中（按照边长度比较）
2. 弹出堆顶节点即最短边e，result.add(e),同时加入到set中，同时将e的另一个节点的边信息中（不属于set的边）加入到堆中，如果在set中则继续2。

Kruskal

算法步骤：从最小边开始通过并查集贪心的构建最小生成树

1. 利用所有的 [edges] 构建一个最小堆，poll出堆顶的元素minEdge，即最小边的from节点与to节点合并到一个集合中，union(from,to)，同时result.add(minEdge)。
2. 继续从最小堆中弹出minEdge，利用UnionFindSet查询当前minEdge的from和to是否在同一集合中，如果在执行步骤2。如果不在就执行union(from,to)，同时result.add(minEdge)。
3. 重复步骤2直到最小堆为空。