【推荐学习：《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; }}复杂度分析
链表 O(n)
二分搜索树 O（log n）
更多编程相关知识，请访问：编程视频！！
以上就是浅谈php实现映射的两种方法（链表和二叉树）的知识。速戳>>知识兔学习精品课！