映射

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

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

实现

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

链表实现：

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

测试：

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

二叉树实现

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