浅谈php实现映射的两种方法（链表和二叉树）

本篇文章给大家介绍一下php使用链表或二叉树来实现映射的方法。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。

【推荐学习：《PHP视频教程》】

映射

映射，或者射影，在数学及相关的领域经常等同于函数。基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。

映射（Map）是用于存取键值对的数据结构（key,value），一个键只能对应一个值且键不能重复。

实现

映射的实现方式可以使用链表或二叉树实现。

链表实现：

<?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

二叉树实现

<?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);              //替换当前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;     } }

复杂度分析

链表 O(n)

二分搜索树 O（log n）