hash算法的原理和实现代码

1.memcache中作为查询用的服务器往往不止一台，需要多台协同处理查询！分布式应用时需要考虑多台服务器间压力的分摊，所以往往采用hash算法来实现；
2.hash算法的实现原理可以简单理解为在一个有序排列（整数）的圆盘中存在多个节点，节点按照由小到大的顺序排列，当有查询任务时，将查询的key名转换为整数之后与节点进行对比，如果小于等于某个特定节点，则将此次查询分摊到该节点对应的服务器下；

<?php
    //将接收到的字符串转化为整数的方法
    interface hash{ 
        public function _hash($str);
    }   

    //找节点的功能
    interface distribution{ 
        public function lookup($key);
    }

    class Consistent implements hash,distribution{ 
        // protected $_node=array(); 
        protected $_mul=64;                    //设置一个真实服务器的虚拟节点为64个
        protected $_position=array();      //放置虚拟节点的数组
        //将字符串转化成整数的方法
        public function _hash($str){ 
            return sprintf('%u',crc32($str));
        }

        //核心功能,检查比对要传入的键,存储到小于或等于该键的节点
        public function lookup($key){ 
            $point=$this->_hash($key);
            //默认返回数组中的第一个单元
            $node=current($this->_position);
            foreach($this->_position as $k => $v){
                //如果传入的point值小于或等于某个节点，则找出该节点终止遍历
                if($point<=$k){
                    $node=$v;
                    break;
                }
            }
            return $node;
        }

        //增加节点
        public function addNode($node){ 
            //添加虚拟节点
            for($i=0;$i<$this->_mul;$i++){
                $node_hash=$this->_hash($node.'_'.$i);   
                //将虚拟节点存入数组 
                $this->_position[$node_hash]=$node;
            }
            $this->sort_position();
        }

        //删除某个节点
        public function delNode($node){ 
            foreach($this->_position as $k=>$v){
                if($v==$node){
                    unset($this->_position[$k]);
                }
            }
        }

        //对节点进行排序
        public function sort_position(){ 
            ksort($this->_position,SORT_REGULAR);
        }

        //调试方法:打印
        public function print_position(){ 
            echo "<pre>";
            print_r($this->_position);
        }
    }
    //实例化对象
    $hash=new Consistent();
    //添加3台服务器a、b、c
    $hash->addNode('a');
    $hash->addNode('b');
    $hash->addNode('c');
    //打印存储虚拟节点的数组
    $hash->print_position();
    echo "当前查询的键名对应的数值为：".$hash->_hash('name')."<br>";
    //查询当前键名查询所指定的服务器
    echo $hash->lookup('name');
?>

原文链接：https://blog.csdn.net/living_ren/article/details/79211406

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。