PHP 实现普通hash和一致性hash

1. 普通hash实现代码

class CommonHash
{
    protected $_ser = [];
    protected $_num = 0;

    public function _hash($str)
    {
        return sprintf("%u", crc32($str));
    }

    public function lookup($key)
    {
        $index = $this->_hash($key) % 4;
        return $this->_ser[$index];
    }

    public function addNode($s)
    {
        $this->_ser[] = $s;
        $this->_num += 1;
    }

    public function delNode($s)
    {
        foreach ($this->_ser as $k => $v) {
            if ($s == $v) {
                unset($this->_ser[$k]);
                $this->_num -= 1;
            }
        }
    }
}

//测试
$commonHash = new CommonHash();
$commonHash->addNode("a");
$commonHash->addNode("b");
$commonHash->addNode("c");
$commonHash->addNode("d");

for ($i = 1; $i < 100; $i++) {
    echo "serv : " . $commonHash->lookup("key:" . $i) . "\n";
}

2. 一致性hash实现代码

class ConsistentHash
{
    protected $nodes = []; //服务节点
    protected $points = []; //虚拟节点的数组
    protected $mul = 64; //每个节点做出64个虚拟节点


    public function _hash($str)
    {
        return sprintf("%u", crc32($str));
    }

    public function lookup($key)
    {
        //重置数组指针,好像是个坑...哈哈哈
        reset($this->points);
        $nodePoint = key($this->points); //默认等于第一个point

        $keyPoint = $this->_hash($key);
        foreach ($this->points as $point => $node) {
            if ($keyPoint <= $point) {
                $nodePoint = $point;
                break;
            }
        }
        return $this->points[$nodePoint];
    }

    public function addNodes($node)
    {
        $this->nodes[$node] = [];
        for ($i = 0; $i < $this->mul; $i++) {
            $key = md5($node . "_" . $i);
            $point = $this->_hash($key); //计算hash值
            $this->points[$point] = $node; //放入虚拟节点中, 虚拟节点的node节点
            $this->nodes[$node][] = $point; //node节点下哪些虚拟节点
        }
        $this->resort();
    }

    public function delNode($node)
    {
        foreach ($this->points as $point => $no) {
            if ($no == $node) {
                unset($this->points[$point]);
            }
        }
        unset($this->nodes[$node]);
        $this->resort();
    }

    //给虚拟节点排序
    public function resort()
    {
        ksort($this->points);
    }


}

//测试一下.发现,随着服务器的台数增加,节点可能落到别的服务器上,不是始终定死到一台服务器的, 一般情况下问题不大
$consistentHash = new ConsistentHash();
for ($i = 0; $i < 6; $i++) {
    $consistentHash->addNodes("A{$i}");
    $consistentHash->addNodes("B{$i}");
    $consistentHash->addNodes("C{$i}");
    $consistentHash->addNodes("D{$i}");
    $consistentHash->addNodes("E{$i}");
    $consistentHash->addNodes("F{$i}");
    $consistentHash->addNodes("G{$i}");
    $consistentHash->addNodes("H{$i}");
    $consistentHash->addNodes("I{$i}");
}
$node = $consistentHash->lookup("woshishui");

print_r($node);