Skip to content

Latest commit

 

History

History
267 lines (159 loc) · 13.4 KB

alogrithm.md

File metadata and controls

267 lines (159 loc) · 13.4 KB

算法和数据结构

PS:待开发中。。。。

作者网页：www.jcohy.com

我的学习笔记，记录学习过程中的笔记以及遇到的问题,以及我的一些经验总结。如果出现链接失效,或者想知道更多的内容等情况可以提交 Issues 提醒我修改相关内容。

算法和数据结构

RBT红黑树

二叉搜索树:(Binary Search Tree又名：二叉查找树，二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树： 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

红黑树是一棵二叉搜索树，它在每个结点上增加一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树没有一条路径会比其他路径长出2倍，所以红黑树是近似平衡的，使得红黑树的查找、插入、删除等操作的时间复杂度最坏为O(log n)，但需要注意到在红黑树上执行插入或删除后将不在满足红黑树性质，恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。具体如何保证？引出红黑树的5个性质。

红黑树的5个性质：满足以下五个性质的二叉搜索树

  1. 每个结点或是红色的或是黑色的
  2. 根结点是黑色的
  3. 每个叶结点是黑色的
  4. 如果一个结点是红色的,则它的两个子结点是黑色的
  5. 对于每个结点,从该结点到其后代叶结点的简单路径上,均包含相同数目的黑色结点

插入操作：

由于性质的约束，插入的结点都是红色的。插入时性质1、3始终保持。破坏性质2当且仅当当前插入结点为根节点。变一下颜色即可。如果是破坏性质4或5，则需要旋转和变色来继续满足红黑树的性质。下面说一说插入的几种情况，约定当前插入结点为N，其父结点为P，叔叔为U，祖父为G

情形1：树空，直接插入违反性质1，将红色改黑。

情形2：N的父结点为黑，不必修改，直接插入

从情形3开始的情形假定N结点的父结点P为红色，所以存在G，并且G为黑色。且N存在一个叔叔结点U，尽管U可能为叶结点。

情形3：P为红，U为红（G结点一定存在且为黑）这里不论P是G的左孩子还是右孩子；不论N是P的左孩子还是右孩子。

首先把P、U改黑，G改红，并以G作为一个新插入的红结点重新进行各种情况的检查，若一路检索至根节点还未结束，则将根结点变黑。

情形4：P为红，U为黑或不存在（G结点一定存在且为黑），且P为G的左孩子，N为P的左孩子（或者P为G的右孩子，N为P的右孩子，保证同向的）。 P、G右旋并将P、G变相反色。因为P取代之前黑G的位置，所以P变黑可以理解，而G变红是为了不违反性质5。

情形5：P为红，U为黑或不存在，且P为G的左孩子，N为P的右孩子（或P为G的右孩子，N为P的左孩子，保证是反向的），对N，P进行一次左旋转换为情形4

删除操作比插入复杂一些，但最多不超过三次旋转可以让红黑树恢复平衡。

其他

  • 黑高从某个结点x出发(不含x)到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高。红黑树的黑高为其根结点的黑高。
  • 一个具有n个内部结点的红黑树的高度h<=2lg(n+1)
  • 结点的属性(五元组):color key left right p
  • 动态集合操作最坏时间复杂度为O(lgn)

排序算法

  • 稳定排序:插入排序、冒泡排序、归并排序、基数排序

  • 插入排序[稳定] 适用于小数组,数组已排好序或接近于排好序速度将会非常快 复杂度：O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]

  • 归并排序[稳定] 采用分治法 复杂度：O(nlogn) - O(nlgn) - O(nlgn) - O(n)[平均 - 最好 - 最坏 - 空间复杂度]

  • 冒泡排序[稳定] 复杂度：O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]

  • 基数排序 分配+收集[稳定] 复杂度： O(d(n+r)) r为基数d为位数 空间复杂度O(n+r)

  • 树排序[不稳定] 应用：TreeSet的add方法、TreeMap的put方法 不支持相同元素,没有稳定性问题 复杂度：平均最差O(nlogn)

  • 堆排序(就地排序)[不稳定] 复杂度：O(nlogn) - O(nlgn) - O(nlgn) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]

  • 快速排序[不稳定] 复杂度：O(nlgn) - O(nlgn) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度] 栈空间0(lgn) - O(n)

  • 选择排序[不稳定] 复杂度：O(n^2) - O(n^2) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]

  • 希尔排序[不稳定] 复杂度 小于O(n^2) 平均 O(nlgn) 最差O(n^s)[1<s<2] 空间O(1)

查找与散列

4.1 散列函数设计

  • 直接定址法:f(key) = a*key+b

简单、均匀,不易产生冲突。但需事先知道关键字的分布情况,适合查找表较小且连续的情况,故现实中并不常用

  • 除留余数法:f(key) = key mod p (p<=m) p取小于表长的最大质数 m为表长

  • DJBX33A算法(time33哈希算法hash = hash*33+(unsigned int)str[i];

平方取中法 折叠法 更多....

4.2 冲突处理

闭散列(开放地址方法):要求装填因子a较小，闭散列方法把所有记录直接存储在散列表中

  • 线性探测:易产生堆积现象(基地址不同堆积在一起)
  • 二次探测:f(key) = (f(key)+di) % m di=1^2,-1^2,2^2,-2^2...可以消除基本聚集
  • 随机探测:f(key) = (f(key)+di),di采用随机函数得到,可以消除基本聚集
  • 双散列:避免二次聚集

开散列(链地址法):原地处理

  • 同义词记录存储在一个单链表中,散列表中子存储单链表的头指针。
  • 优点:无堆积 事先无需确定表长 删除结点易于实现 装载因子a>=1,缺点:需要额外空间

跳表

为什么选择跳表？

目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。 想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树 出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树， 还要参考网上的代码，相当麻烦。 用跳表吧，跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它， 它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表， 就能去实现一个 SkipList。

跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。

Skip list(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。Skip list让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，是一种“空间来换取时间”的一个算法，在每个节点中增加了指向下一层的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。

在Java的API中已经有了实现：分别是

ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap) ；

ConcurrentSkipListSet(在功能上对应HashSet)

Skip list的性质

(1) 由很多层结构组成，level是通过一定的概率随机产生的

(2) 每一层都是一个有序的链表，默认是升序

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现

(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素

时间复杂度O(lgn) 最坏O(2lgn)

Java实现参见我的GitHub Repo Algorithm

AVL树

1.LL型

在某一节点的左孩子的左子树上插入一个新的节点，使得该节点不再平衡。 举例 A B Ar Bl Br 在Bl下插入N，执行一次右旋即可，即把B变为父结点，原来的根节点A变为B的左孩子，B的右子树变为A的左子树。

2.RR型

与LL型是对称的，执行一次左旋即可。

3.LR型

指在AVL树某一结点左孩子的右子树上插入一个结点，使得该节点不在平衡。这时需要两次旋转，先左旋再右旋。

4.RL型

与LR对称，执行一次右旋，再执行一次左旋。

删除

1、被删的节点是叶子节点

将该节点直接从树中删除，并利用递归的特点和高度的变化，反向推算其父节点和祖先节点是否失衡。

2、被删的节点只有左子树或只有右子树

将左子树（右子树）替代原有节点的位置，并利用递归的特点和高度的变化，反向推算父节点和祖先节点是否失衡。

3、被删的节点既有左子树又有右子树

找到被删节点的左子树的最右端的节点，将该结点的的值赋给待删除结点，再用该结点的左孩子替换它本来的位置，然后释放该结点，并利用递归特点，反向推断父节点和祖父节点是否失衡。

一致性Hash

第一：简单介绍 一致性哈希算法是分布式系统中常用的算法。比如，一个分布式的存储系统，要将对象存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N，N是机器节点数。

1、考虑到比如一个服务器down掉，服务器结点N变为N-1，映射公式必须变为key%(N-1)

2、访问量加重，需要添加服务器结点，N变为N+1，映射公式变为hash(object)%(N+1)

当出现1,2的情况意味着我们的映射都将无效，对服务器来说将是一场灾难，尤其是对缓存服务器来说，因为缓存服务器映射的失效，洪水般的访问都将冲向后台服务器。

第二点：hash算法的单调性

Hash 算法的一个衡量指标是单调性，单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

consistent hash 也是一种hash 算法，简单的说，在移除 / 添加一个结点时，它能够尽可能小的改变已存在的映射关系，尽可能的满足单调性的要求。

第三点：将对象和服务器结点分别映射到环型空间

通常的一致性哈希做法是将 value 映射到一个 32 位的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环。

我们可以通过hash函数将我们的key映射到环型空间中，同时根据相同的哈希算法把服务器也映射到环型空间中，顺便提一下服务器或者某个计算节点的 hash 计算，一般的方法可以使用机器的 IP 地址或者机器名作为 hash 输入。

第四点：将对象映射到服务器

在这个环形空间中，如果沿着顺时针方向从对象的 key 值出发，直到遇见一个 服务器结点，那么就将该对象存储在这个服务器结点上，因为对象和服务器的hash 值是固定的，因此这个 cache 必然是唯一和确定的。

这时候考察某个服务器down机或者需要添加服务器结点，也就是移除和添加的操作，我们只需要几个对象的映射。

第五点：虚拟结点

Hash 算法的另一个指标是平衡性 (Balance)。平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

对于上述的做法，可能导致某些对象都映射到某个服务器，使得分布不平衡。为此可以采用“虚拟结点”的做法。

“虚拟结点”（ virtual node ）是实际节点在 hash 空间的复制品，一实际结点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。引入“虚拟结点”会让我们的映射分布更为平衡一些。

引入“虚拟结点”前： Hash(“192.168.1.1”);

引入“虚拟结点”后： Hash(“192.168.1.1#1”); Hash(“192.168.1.1#2”);

如何判断链表是否有环

方法1：快慢指针法 2.设两个工作指针p、q，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。比如p从A走到D，用了4步，而q则用了14步。因而步数不等，出现矛盾，存在环。

熟悉哪些算法？

  • [哈希算法] 一致性哈希 time33哈希 FNV1_32_HASH
  • [排序算法] 快速排序
  • [搜索算法] DFS BFS
  • [最小生成树算法] Kruskal Prim
  • [最短路径算法] Dijkstra Floyed