本篇文章給大家介紹一下php使用鏈表或二叉樹來實現(xiàn)映射的方法。有一定的參考價值，有需要的朋友可以參考一下，希望對大家有所幫助。

【推薦學(xué)習(xí)：《PHP視頻教程》】

映射

映射，或者射影，在數(shù)學(xué)及相關(guān)的領(lǐng)域經(jīng)常等同于函數(shù)?；诖?，部分映射就相當(dāng)于部分函數(shù)，而完全映射相當(dāng)于完全函數(shù)。

映射（Map）是用于存取鍵值對的數(shù)據(jù)結(jié)構(gòu)（key,value），一個鍵只能對應(yīng)一個值且鍵不能重復(fù)。

實現(xiàn)

映射的實現(xiàn)方式可以使用鏈表或二叉樹實現(xiàn)。

鏈表實現(xiàn)：

<?php /**  * 接口 字典  * Interface Dict  * @package appmodels  */ Interface Dict {      public function set( $key , $value );      public function get( $key );      public function isExist( $key );      public function delete($key);      public function getSize();   }  class DictLinkList implements Dict {     protected $size=0;     public $key;     public $value;     public $next;      public function __construct($key=null,$value=null,$next=null)     {         $this->key = $key;         $this->value = $value;         $this->next = $next;     }      public function set($key,$value){         $node = $this;         while( $node && $node->next ){             if( $node->next->key==$key ){                 $node->next->value = $value;                 return $node->next;             }             $node = $node->next;         }          $node->next =  new self($key,$value,$node->next);         $this->size++;         return  $node->next;     }       public function get($key){         $node = $this;         while($node){             if( $node->key ==$key  ){                 return $node->value;             }             $node = $node->next;         }          throw new Exception('cannot found key');     }       public function isExist($key)     {         $node = $this;         while($node){             if( $node->key ==$key  ){                 return true;             }             $node = $node->next;         }         return false;     }      public function delete($key)     {         if( $this->size==0)             throw new Exception('key is not exist');          $node = $this;         while($node->next){             if( $node->next->key == $key  ){                 $node->next = $node->next->next;                 $this->size--;                 break;             }             $node = $node->next;         }          return $this;     }      public function getSize()     {         return $this->size;     } }

測試：

<?php         $dict = new DictLinkList();         $dict->set('sun',111); //O(n)         $dict->set('sun',222);         $dict->set('w',111);         $dict->set('k',111);         var_dump($dict->get('w'));   //O(n)         var_dump($dict->isExist('v'));   //O(n)         var_dump($dict->delete('sun'));    //O(n)         var_dump($dict->getSize());          /******************************************/ //111 //false //true //2

二叉樹實現(xiàn)

<?php class DictBtree implements Dict {     public $key;     public $value;      public $left;     public $right;     private $size;      public function __construct($key=null,$value=null)     {         $this->key = $key;         $this->value = $value;         $this->left = null;         $this->right = null;         $this->size = 0;     }      public function set( $key , $value ){         if( $this->size ==0 ){             $node = new static( $key,$value );             $this->key = $node->key;             $this->value = $node->value;             $this->size++;         }else{             $node = $this;             while($node){                 if( $node->key == $key ){                     $node->value = $value;                     break;                 }                 if($node->key>$key){                     if($node->left==null){                         $node->left = new static( $key,$value );                         $this->size++;                         break;                     }                     $node = $node->left;                 }else{                     if($node->right==null){                         $node->right = new static( $key,$value );                         $this->size++;                         break;                     }                     $node = $node->right;                 }             }         }          return $this;     }      public function get( $key ){         if( $this->size ==0 )             throw new Exception('empty');         $node = $this;         while($node) {             if ($node->key == $key) {                 return $node->value;             }             if ($node->key > $key) {                 $node = $node->left;             } else {                 $node = $node->right;             }         }         throw new Exception('this key not exist');     }      public function isExist( $key ){         if( $this->size ==0 )             return false;         $node = $this;         while($node) {             if ($node->key == $key) {                 return true;             }             if ($node->key > $key) {                 $node = $node->left;             } else {                 $node = $node->right;             }         }         return false;     }      public function delete($key){          //找到元素，尋找元素左邊最小元素         $node = $this->select($key);         if( $node->right!=null ){             $node1 = $node->selectMin($node->right);              //替換當(dāng)前node             $node->key = $node1->key;             $node->value = $node1->value;              //刪除$node->right最小元素，獲取最終元素賦給$node->right             $nodeMin = $this->deleteMin($node->right);             $node->right = $nodeMin;         }else{             $node1 = $node->selectMax($node->left);              $node->key = $node1->key;             $node->value = $node1->value;              $nodeMax = $this->deleteMax($node->left);             $node->left = $nodeMax;         }         return $this;      }      protected function deleteMin( $node ){ //        if( $this->size ==0 ) //            throw new Exception('empty');  //        $prev = new static(); //        $prev->left = $node; //        while($prev->left->left!=null){ // //            $prev = $prev->left; //        } //        $prev->left = $prev->left->right;          if( $node->left==null ){             $rightNode = $node->right;             $node->right = null;             $this->size--;             return $rightNode;         }         $node->left = $this->deleteMin($node->left);          return $node;     }      protected function deleteMax($node){          if( $node->right==null ){             $leftNode = $node->left;             $node->left = null;             $this->size--;             return $leftNode;         }          $node->right = $this->deleteMax($node->right);         return $node;      }      public function getSize(){         return $this->size;     }       public function select($key){         $node = $this;          while($node){             if($node->key==$key){                 return $node;             }             if ($node->key > $key) {                 $node = $node->left;             } else {                 $node = $node->right;             }         }          throw new Exception('this key not exist');     }      public function selectMin( $node ){         while($node->left){              $node = $node->left;         }         return $node;     }       public function selectMax( $node ){         while($node->right){              $node = $node->right;         }         return $node;     } }

復(fù)雜度分析

鏈表 O(n)

二分搜索樹 O（log n）