就是把鏈表的結(jié)構(gòu)稍加改造，這種數(shù)據(jù)結(jié)構(gòu)叫
創(chuàng)新互聯(lián)公司客戶idc服務(wù)中心，提供托管服務(wù)器、成都服務(wù)器、成都主機(jī)托管、成都雙線服務(wù)器等業(yè)務(wù)的一站式服務(wù)。通過各地的服務(wù)中心，我們向成都用戶提供優(yōu)質(zhì)廉價(jià)的產(chǎn)品以及開放、透明、穩(wěn)定、高性價(jià)比的服務(wù)，資深網(wǎng)絡(luò)工程師在機(jī)房提供7*24小時(shí)標(biāo)準(zhǔn)級(jí)技術(shù)保障。
為了提升鏈表的查詢效率，怎么讓鏈表支持類似‘?dāng)?shù)組’那樣的‘二分’算法呢
跳表是一個(gè)各方面性能都比較優(yōu)秀的 動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) ，可以支持快速地插入、刪除、查找操作，寫起來也不復(fù)雜，甚至可以替代紅黑樹。
Redis 中的有序集合（Sorted Set）就是用跳表來實(shí)現(xiàn)的。
那 Redis 為什么會(huì)選擇用跳表(和散列表)來實(shí)現(xiàn)有序集合呢？ 為什么不用紅黑樹呢？這個(gè)問題一會(huì)在回答，先看看跳表的數(shù)據(jù)結(jié)構(gòu)
其實(shí)概念很簡單，就是在鏈表上加上了
當(dāng)我們?cè)诓煌２迦霐?shù)據(jù)，如果我們不更新索引，可能出現(xiàn)某 2 個(gè)索引結(jié)點(diǎn)之間數(shù)據(jù)非常多的情況。極端情況下，跳表還會(huì)退化成單鏈表。
紅黑樹、AVL 樹這樣平衡二叉樹，是通過左右旋的方式保持左右子樹的大小平衡，而跳表是通過 隨機(jī)函數(shù) 來維護(hù)平衡性。
插入、刪除、查找以及迭代輸出有序序列這幾個(gè)操作，紅黑樹也可以完成，時(shí)間復(fù)雜度跟跳表是一樣的。但是， 按照區(qū)間來查找數(shù)據(jù)這個(gè)操作，紅黑樹的效率沒有跳表高。
對(duì)于按照區(qū)間查找數(shù)據(jù)這個(gè)操作，跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了。
Redis 鍵值構(gòu)建一個(gè)散列表，這樣按照 key 來刪除、查找一個(gè)成員對(duì)象的時(shí)間復(fù)雜度就變成了 O(1)。同時(shí)，借助跳表結(jié)構(gòu)，其他操作也非常高效。
散列表的英文叫“Hash Table”，我們平時(shí)也叫它“哈希表”或者“Hash 表”
散列技術(shù)是在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系 f，使得每個(gè)關(guān)鍵字 key 對(duì)應(yīng)一個(gè)存儲(chǔ)位置 f(key)。查找時(shí)根據(jù)這個(gè)對(duì)應(yīng)關(guān)系匠互給定的 key 的映射 f(key)
這種關(guān)系 f 稱為散列函數(shù)（又稱哈希函數(shù)）。散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)存儲(chǔ)空間稱為散列表或哈希表。那么關(guān)鍵字對(duì)應(yīng)的記錄存儲(chǔ)位置稱為散列地址。
散列函數(shù)的構(gòu)造方法特點(diǎn)就是：計(jì)算簡單、散列地址分布均勻
大家一定聽說過 hash 碰撞。就是2個(gè)不同的 key 對(duì)應(yīng)著不同的 f 關(guān)系。但這是幾乎不可能的，即便像業(yè)界著名的MD5、SHA、CRC等哈希算法，也無法完全避免這種散列沖突。而且，因?yàn)閿?shù)組的存儲(chǔ)空間有限，也會(huì)加大散列沖突的概率。
我們只能通過其它途徑來尋找方法。我們常用的散列沖突解決方法有兩類，開放尋址法（open addressing）和鏈表法（chaining）。
所謂的開放尋址法就是一但發(fā)生了沖突，就去尋找下一個(gè)空的散地址，只要散列表足夠大，空的散列表地址總能找到，并將記錄存入。
鏈地址法又稱鏈表法，其實(shí)當(dāng)發(fā)生沖突時(shí)存入鏈表，如下圖很容易就可以看明白。此時(shí)，已經(jīng)不存在什么沖突地址的問題，無論有多少?zèng)_突，都只是在當(dāng)前位置給單鏈表增加結(jié)點(diǎn)的問題。
這種不常見，就是把沖突的單獨(dú)找個(gè)地方。
顧名思義，紅黑樹中的節(jié)點(diǎn)，一類被標(biāo)記為黑色，一類被標(biāo)記為紅色。除此之外，一棵紅黑
平衡二叉樹 是一種二叉排序樹，其中每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度不能大于 1
紅黑樹是一種平衡二叉查找樹。它是為了解決普通二叉查找樹在數(shù)據(jù)更新的過程中，復(fù)雜度退化的問題而產(chǎn)生的。紅黑樹的高度近似 log2n，所以它是近似平衡，插入、刪除、查找操作的時(shí)間復(fù)雜度都是 O(logn)。
平衡二叉查找樹其實(shí)有很多，比如，Splay Tree（伸展樹）、Treap（樹堆）等，但是我們提到平衡二叉查找樹，聽到的基本都是紅黑樹。
紅黑樹在眾多里面，表現(xiàn)的最為平衡。
“近似平衡”就等價(jià)為性能不會(huì)退化得太嚴(yán)重。
一棵紅黑樹還需要滿足這樣幾個(gè)要求：
看到這里你會(huì)很頭大，什么黑的紅的，完全不懂。賦上連接，有時(shí)間在看
散列表 ：插入刪除查找都是O(1), 是最常用的，但其缺點(diǎn)是不能順序遍歷(存入的數(shù)據(jù)是無順序的)以及擴(kuò)容縮容的性能損耗。適用于那些不需要順序遍歷，數(shù)據(jù)更新不那么頻繁的。
散列表總和鏈表、跳表一起出現(xiàn)組合使用。
跳表 ：插入刪除查找都是O(logn), 并且能順序遍歷。缺點(diǎn)是空間復(fù)雜度O(n)。適用于不那么在意內(nèi)存空間的，其順序遍歷和區(qū)間查找非常方便。
跳表還可以和散列表組合讓刪除、查找一個(gè)成員對(duì)象操作變?yōu)镺(1)，也就是說利用了散列表查找速度，跳表的順序結(jié)構(gòu)
紅黑樹 ：插入刪除查找都是O(logn), 中序遍歷即是順序遍歷，穩(wěn)定。缺點(diǎn)是難以實(shí)現(xiàn)，去查找不方便。其實(shí)跳表更佳，但紅黑樹已經(jīng)用于很多地方了。
?
//--------------------
// 基本數(shù)據(jù)結(jié)構(gòu)算法
//--------------------
//二分查找（數(shù)組里查找某個(gè)元素）
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;
}
//順序查找（數(shù)組里查找某個(gè)元素）
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;
}
}
//線性表的刪除（數(shù)組中實(shí)現(xiàn)）
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 ;
}
//冒泡排序（數(shù)組排序）
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;
}
//快速排序（數(shù)組排序）
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內(nèi)置字符串函數(shù)實(shí)現(xiàn)
//------------------------
//字符串長度
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;
}
//字符串翻轉(zhuǎn)
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 ;
}
//--------------------
// 自實(shí)現(xiàn)字符串處理函數(shù)
//--------------------
//插入一段字符串
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;
}
//復(fù)制字符串
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;
}
//簡單編碼函數(shù)（與php_decode函數(shù)對(duì)應(yīng)）
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;
}
//簡單解碼函數(shù)（與php_encode函數(shù)對(duì)應(yīng)）
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;
}
//簡單加密函數(shù)（與php_decrypt函數(shù)對(duì)應(yīng)）
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;
}
//簡單解密函數(shù)（與php_encrypt函數(shù)對(duì)應(yīng)）
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（中文名：“超文本預(yù)處理器”）是一種通用開源腳本語言。語法吸收了C語言、Java和Perl的特點(diǎn)，利于學(xué)習(xí)，使用廣泛，主要適用于Web開發(fā)領(lǐng)域。
PHP獨(dú)特的語法混合了C、Java、Perl以及PHP自創(chuàng)的語法。它可以比CGI或者Perl更快速地執(zhí)行動(dòng)態(tài)網(wǎng)頁。用PHP做出的動(dòng)態(tài)頁面與其他的編程語言相比，PHP是將程序嵌入到HTML文檔中去執(zhí)行，執(zhí)行效率比完全生成HTML標(biāo)記的CGI要高許多。
PHP還可以執(zhí)行編譯后代碼，編譯可以達(dá)到加密和優(yōu)化代碼運(yùn)行，使代碼運(yùn)行更快。
PHP在數(shù)據(jù)庫方面的豐富支持，也是它迅速走紅的原因之一，它支持下列的數(shù)據(jù)庫或是數(shù)據(jù)文件：
Adabas 、D、 DBA、dBase 、dbm 、filePro 、Informix 、InterBase、mSQL 、Microsoft SQL Server、·MySQL、Solid、Sybase、 Oracle 、PostgreSQL
而在Internet上它也支持了相當(dāng)多的通訊協(xié)議 (protocol），包括了與電子郵件相關(guān)的 IMAP,POP3；網(wǎng)管系統(tǒng) SNMP；網(wǎng)絡(luò)新聞NNTP；帳號(hào)共用 NIS；全球信息網(wǎng)HTTP及Apache服務(wù)器；目錄協(xié)議LDAP以及其它網(wǎng)絡(luò)的相關(guān)函數(shù)。
擴(kuò)展資料：
PHP的特性包括：
1、PHP獨(dú)特的語法混合了 C、Java、Perl 以及 PHP 自創(chuàng)新的語法。
2、PHP可以比CGI或者Perl更快速的執(zhí)行動(dòng)態(tài)網(wǎng)頁——?jiǎng)討B(tài)頁面方面，與其他的編程語言相比，PHP是將程序嵌入到HTML文檔中去執(zhí)行，執(zhí)行效率比完全生成htmL標(biāo)記的CGI要高許多；PHP具有非常強(qiáng)大的功能，所有的CGI的功能PHP都能實(shí)現(xiàn)。
3、PHP支持幾乎所有流行的數(shù)據(jù)庫以及操作系統(tǒng)。
4、PHP可以用C、C++進(jìn)行程序的擴(kuò)展。
參考資料：
百度百科--PHP
重慶分公司
重慶分公司
