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

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

创新互联公司客户idc服务中心，提供托管服务器、成都服务器、成都主机托管、成都双线服务器等业务的一站式服务。通过各地的服务中心，我们向成都用户提供优质廉价的产品以及开放、透明、稳定、高性价比的服务，资深网络工程师在机房提供7*24小时标准级技术保障。

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

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

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), 中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。

php现在有哪些常用的算法

?

//--------------------

// 基本数据结构算法

//--------------------

//二分查找（数组里查找某个元素）

function bin_sch($array, $low, $high, $k){

if ( $low = $high){

$mid = intval(($low+$high)/2 );

if ($array[$mid] == $k){

return $mid;

}elseif ( $k $array[$mid]){

return bin_sch($array, $low, $mid-1, $k);

}else{

return bin_sch($array, $mid+ 1, $high, $k);

}

}

return -1;

}

//顺序查找（数组里查找某个元素）

function seq_sch($array, $n, $k){

$array[$n] = $k;

for($i=0; $i$n; $i++){

if( $array[$i]==$k){

break;

}

}

if ($i$n){

return $i;

}else{

return -1;

}

}

//线性表的删除（数组中实现）

function delete_array_element($array , $i)

{

$len = count($array);

for ($j= $i; $j$len; $j ++){

$array[$j] = $array [$j+1];

}

array_pop ($array);

return $array ;

}

//冒泡排序（数组排序）

function bubble_sort( $array)

{

$count = count( $array);

if ($count = 0 ) return false;

for($i=0 ; $i$count; $i ++){

for($j=$count-1 ; $j$i; $j--){

if ($array[$j] $array [$j-1]){

$tmp = $array[$j];

$array[$j] = $array[ $j-1];

$array [$j-1] = $tmp;

}

}

}

return $array;

}

//快速排序（数组排序）

function quick_sort($array ) {

if (count($array) = 1) return $array;

$key = $array [0];

$left_arr = array();

$right_arr = array();

for ($i= 1; $icount($array ); $i++){

if ($array[ $i] = $key)

$left_arr [] = $array[$i];

else

$right_arr[] = $array[$i ];

}

$left_arr = quick_sort($left_arr );

$right_arr = quick_sort( $right_arr);

return array_merge($left_arr , array($key), $right_arr);

}

//------------------------

// PHP内置字符串函数实现

//------------------------

//字符串长度

function strlen ($str)

{

if ($str == '' ) return 0;

$count = 0;

while (1){

if ( $str[$count] != NULL){

$count++;

continue;

}else{

break;

}

}

return $count;

}

//截取子串

function substr($str, $start, $length=NULL)

{

if ($str== '' || $startstrlen($str )) return;

if (($length!=NULL) ( $start0) ($length strlen($str)-$start)) return;

if (( $length!=NULL) ($start 0) ($lengthstrlen($str )+$start)) return;

if ($length == NULL) $length = (strlen($str ) - $start);

if ($start 0){

for ($i=(strlen( $str)+$start); $i(strlen ($str)+$start+$length ); $i++) {

$substr .= $str[$i];

}

}

if ($length 0){

for ($i= $start; $i($start+$length ); $i++) {

$substr .= $str[$i];

}

}

if ( $length 0){

for ($i =$start; $i(strlen( $str)+$length); $i++) {

$substr .= $str[$i ];

}

}

return $substr;

}

//字符串翻转

function strrev($str)

{

if ($str == '') return 0 ;

for ($i=(strlen($str)- 1); $i=0; $i --){

$rev_str .= $str[$i ];

}

return $rev_str;

}

//字符串比较

function strcmp($s1, $s2)

{

if (strlen($s1) strlen($s2)) return -1 ;

if (strlen($s1) strlen( $s2)) return 1;

for ($i =0; $istrlen($s1 ); $i++){

if ($s1[ $i] == $s2[$i]){

continue;

}else{

return false;

}

}

return 0;

}

//查找字符串

function strstr($str, $substr)

{

$m = strlen($str);

$n = strlen($substr );

if ($m $n) return false ;

for ($i=0; $i =($m-$n+1); $i ++){

$sub = substr( $str, $i, $n);

if ( strcmp($sub, $substr) == 0) return $i;

}

return false ;

}

//字符串替换

function str_replace($substr , $newsubstr, $str)

{

$m = strlen($str);

$n = strlen($substr );

$x = strlen($newsubstr );

if (strchr($str, $substr ) == false) return false;

for ( $i=0; $i=($m- $n+1); $i++){

$i = strchr($str, $substr);

$str = str_delete ($str, $i, $n);

$str = str_insert($str, $i, $newstr);

}

return $str ;

}

//--------------------

// 自实现字符串处理函数

//--------------------

//插入一段字符串

function str_insert($str, $i , $substr)

{

for($j=0 ; $j$i; $j ++){

$startstr .= $str[$j ];

}

for ($j=$i; $j strlen($str); $j ++){

$laststr .= $str[$j ];

}

$str = ($startstr . $substr . $laststr);

return $str ;

}

//删除一段字符串

function str_delete($str , $i, $j)

{

for ( $c=0; $c$i; $c++){

$startstr .= $str [$c];

}

for ($c=( $i+$j); $cstrlen ($str); $c++){

$laststr .= $str[$c];

}

$str = ($startstr . $laststr );

return $str;

}

//复制字符串

function strcpy($s1, $s2 )

{

if (strlen($s1)==NULL || !isset( $s2)) return;

for ($i=0 ; $istrlen($s1); $i++){

$s2[] = $s1 [$i];

}

return $s2;

}

//连接字符串

function strcat($s1 , $s2)

{

if (!isset($s1) || !isset( $s2)) return;

$newstr = $s1 ;

for($i=0; $i count($s); $i ++){

$newstr .= $st[$i ];

}

return $newsstr;

}

//简单编码函数（与php_decode函数对应）

function php_encode($str)

{

if ( $str=='' strlen( $str)128) return false;

for( $i=0; $istrlen ($str); $i++){

$c = ord($str[$i ]);

if ($c31 $c 107) $c += 20 ;

if ($c106 $c 127) $c -= 75 ;

$word = chr($c );

$s .= $word;

}

return $s;

}

//简单解码函数（与php_encode函数对应）

function php_decode($str)

{

if ( $str=='' strlen($str )128) return false;

for( $i=0; $istrlen ($str); $i++){

$c = ord($word);

if ( $c106 $c127 ) $c = $c-20;

if ($c31 $c 107) $c = $c+75 ;

$word = chr( $c);

$s .= $word ;

}

return $s;

}

//简单加密函数（与php_decrypt函数对应）

function php_encrypt($str)

{

$encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';

$decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';

if ( strlen($str) == 0) return false;

for ($i=0; $istrlen($str); $i ++){

for ($j=0; $j strlen($encrypt_key); $j ++){

if ($str[$i] == $encrypt_key [$j]){

$enstr .= $decrypt_key[$j];

break;

}

}

}

return $enstr;

}

//简单解密函数（与php_encrypt函数对应）

function php_decrypt($str)

{

$encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';

$decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';

if ( strlen($str) == 0) return false;

for ($i=0; $istrlen($str); $i ++){

for ($j=0; $j strlen($decrypt_key); $j ++){

if ($str[$i] == $decrypt_key [$j]){

$enstr .= $encrypt_key[$j];

break;

}

}

}

return $enstr;

}

?

PHP是什么？

PHP（中文名：“超文本预处理器”）是一种通用开源脚本语言。语法吸收了C语言、Java和Perl的特点，利于学习，使用广泛，主要适用于Web开发领域。

PHP独特的语法混合了C、Java、Perl以及PHP自创的语法。它可以比CGI或者Perl更快速地执行动态网页。用PHP做出的动态页面与其他的编程语言相比，PHP是将程序嵌入到HTML文档中去执行，执行效率比完全生成HTML标记的CGI要高许多。

PHP还可以执行编译后代码，编译可以达到加密和优化代码运行，使代码运行更快。

PHP在数据库方面的丰富支持，也是它迅速走红的原因之一，它支持下列的数据库或是数据文件：

Adabas 、D、 DBA、dBase 、dbm 、filePro 、Informix 、InterBase、mSQL 、Microsoft SQL Server、·MySQL、Solid、Sybase、 Oracle 、PostgreSQL

而在Internet上它也支持了相当多的通讯协议 (protocol），包括了与电子邮件相关的 IMAP,POP3；网管系统 SNMP；网络新闻NNTP；帐号共用 NIS；全球信息网HTTP及Apache服务器；目录协议LDAP以及其它网络的相关函数。

扩展资料：

PHP的特性包括：

1、PHP独特的语法混合了 C、Java、Perl 以及 PHP 自创新的语法。

2、PHP可以比CGI或者Perl更快速的执行动态网页——动态页面方面，与其他的编程语言相比，PHP是将程序嵌入到HTML文档中去执行，执行效率比完全生成htmL标记的CGI要高许多；PHP具有非常强大的功能，所有的CGI的功能PHP都能实现。

3、PHP支持几乎所有流行的数据库以及操作系统。

4、PHP可以用C、C++进行程序的扩展。

参考资料：

百度百科--PHP