2N 方定点算法

(1)比对哈希环的代码有个bug 

(2)虚拟节点设置的量不够

1. 两个节点的时候，节点分布在环的 原点和1/2 处。
2. 第三个节点的来的时候，插入在1/4处，第四个节点插入在3/4处
3. 第五个节点在1/8 ....
4. 1/2 = 2/4 = 4/8 也就是节点按2分法插入，插满对应位置。
   再来节点，再做一次2等分切分，原先的节点位置不变，但是新切分位置，多处于本轮新增切分点的1/2处

f(k) = (2(k-(2^level-1) +1)/2^level)*2^n
      = (2k-(2^level) +1) * (2^n/2^level)
      = (2k-(2^level) +1) * (2 ^ (n-level))
h(k)  = level

L(uid) = uid % 1024   
//为啥是1024,因为1024对于一个学校足够小。不会有学校学生低于1024个学生。
//对于节点来说足够大，很少需要扩容超过1024个节点
//1024 = 1GB = 1级棒 魔数口号

<?php
/**
 * @file RingHash.php
 * @synopsis  2N方哈希 ，独家定制的哈希方法
 * @author fangle
 * @version 1
 * @date 2020-08-20
 */

class RingHash
{

    protected $n = 10;  //定义环节点数 为 2^n 次方

    /**
     * nodes array
     * @var array
     */
    protected $nodes = [];

    protected $virtualNodes = [];

    /**
     * sort
     * @var boolean
     */
    protected $isSort = false;



    /**
     * 添加节点
     * @param $node
     * @return bool
     */
    public function addNode($nodeKey,$node)
    {
        if(!is_numeric($nodeKey))
            throw new Exception("nodeKey should be a numeric");

        $this->nodes[] = $node;
        $virtualHash = $this->getNodeHash($nodeKey,$this->getNodeLevel($nodeKey));
        $this->virtualNodes[$virtualHash] = $node;
        return true;
    }


    /**
     * h(k) = level
     * 传入k 找到 k > 2^level k < 2^level+1 (level < n)
     * 先用遍历法。后面采用二分法 递归来优化
     * @param $nodeKey
     * @return int
     */
    protected function getNodeLevel($nodeKey,$maxLev = 0){
        if($nodeKey <= 0)
            return 0;

        if($nodeKey > $this->n)
            return $this->n;


        if($nodeKey >= pow(2,$maxLev))
            $maxLev = $this->getNodeLevel($nodeKey,$maxLev+1);

        return $maxLev;
    }



    /**
     * f(k) = (2(k-(2^level-1) +1)/2^level)*2^n
     *      = (2k-(2^level) +1) * (2^n/2^level)
     *      = (2k-(2^level) +1) * (2 ^ (n-level))
     * @param $nodeKey
     * @param $level
     * @return int
     */
    protected function getNodeHash($nodeKey, $level){
        //if($nodeKey == 0) return 0;
        //var_dump($nodeKey,$level);
        //$hashKey = (floor($nodeKey)-pow(2,$level-1) + 1)/pow(2,$level) * pow(2,$this->n);
        $hashKey = (2*intval($nodeKey)-pow(2,$level) + 1)*(pow(2,$this->n - $level));

        return $hashKey;
    }


    /**
     * 更新添加节点
     * @param $nodes
     */
    public function addNodes($nodes)
    {
        foreach ($nodes as $nodeKey => $node) {
            $this->addNode($nodeKey,$node);
        }
        return true;
    }

    /**
     * 获取节点
     * @param $key 可以用uid之类
     * @return mixed
     */
    public function getNode($key)
    {
        if (!$this->isSort) {
            ksort($this->virtualNodes);
            $this->isSort = true;
        }
        $hashKey = intval($key) % pow(2,$this->n);

        foreach ($this->virtualNodes as $hashNode => $node) {
            if ($hashKey < $hashNode) {
                break; //这个key的hash值大于节点的hash,返回取小节点的。先默认是第一个
            }
            $hitNode = $node;
        }

        reset($this->virtualNodes);

        return $hitNode;
    }
}