本文实例讲述了php实现映射操作。分享给大家供大家参考，具体如下：

映射

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

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

实现

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

链表实现：

<?php/** * 接口 字典 * Interface Dict * @package app\models */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

二叉树实现

<?phpclass 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;  }}