php数据结构链表,php数组和链表的区别

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

php-红黑树、散列表、跳表理解入门

就是把链表的结构稍加改造，这种数据结构叫

为了提升链表的查询效率，怎么让链表支持类似‘数组’那样的‘二分’算法呢

跳表是一个各方面性能都比较优秀的动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树。

Redis 中的有序集合（Sorted Set）就是用跳表来实现的。

那 Redis 为什么会选择用跳表(和散列表)来实现有序集合呢？为什么不用红黑树呢？这个问题一会在回答，先看看跳表的数据结构

其实概念很简单，就是在链表上加上了

当我们在不停插入数据，如果我们不更新索引，可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。

红黑树、AVL 树这样平衡二叉树，是通过左右旋的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护平衡性。

插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。

Redis 键值构建一个散列表，这样按照 key 来删除、查找一个成员对象的时间复杂度就变成了 O(1)。同时，借助跳表结构，其他操作也非常高效。

散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)。查找时根据这个对应关系匠互给定的 key 的映射 f(key)

这种关系 f 称为散列函数（又称哈希函数）。散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。那么关键字对应的记录存储位置称为散列地址。

散列函数的构造方法特点就是：计算简单、散列地址分布均匀

大家一定听说过 hash 碰撞。就是2个不同的 key 对应着不同的 f 关系。但这是几乎不可能的，即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。

我们只能通过其它途径来寻找方法。我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

所谓的开放寻址法就是一但发生了冲突，就去寻找下一个空的散地址，只要散列表足够大，空的散列表地址总能找到，并将记录存入。

链地址法又称链表法，其实当发生冲突时存入链表，如下图很容易就可以看明白。此时，已经不存在什么冲突地址的问题，无论有多少冲突，都只是在当前位置给单链表增加结点的问题。

这种不常见，就是把冲突的单独找个地方。

顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑

平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度不能大于 1

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。

平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。

红黑树在众多里面，表现的最为平衡。

“近似平衡”就等价为性能不会退化得太严重。

一棵红黑树还需要满足这样几个要求：

看到这里你会很头大，什么黑的红的，完全不懂。赋上连接，有时间在看

散列表：插入删除查找都是O(1), 是最常用的，但其缺点是不能顺序遍历(存入的数据是无顺序的)以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。

散列表总和链表、跳表一起出现组合使用。

跳表：插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。

跳表还可以和散列表组合让删除、查找一个成员对象操作变为O(1)，也就是说利用了散列表查找速度，跳表的顺序结构

红黑树：插入删除查找都是O(logn), 中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。