php如何實現映射

小編給大家分享一下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

二叉樹實現

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

以上是“php如何實現映射”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！