第 5 周 技术选型：技术选型能力反映了架构师的综合水平（一）

<?php

class ConsistentHashing
{
    protected $nodes = [];
    protected $positions = [];
    protected $indexes = [];
    protected $len = 0;
    protected $virtualNum = 1024;

    public function hashCode($str)
    {
        $hash = 5381;
        $md5 = md5($str);
        $seed = 5;
        $len = 32;
        for ($i = 0; $i < $len; $i++) {
            $hash = ($hash << $seed) + $hash + ord($md5{$i});
        }
        return $hash & 0x7FFFFFFF;
    }

    public function lookup($key)
    {
        $code = $this->hashCode($key);
        $low = 0;
        $height = $this->len -1;
        $index = null;
        $min = 0;
        while ($low <= $height) {
            $mid = floor(($low + $height) / 2);
            if ($this->indexes[$mid] === $code) {
                $index = $mid;
                break;
            } elseif ($this->indexes[$mid] < $code ) {
                $low = $mid + 1;
            } elseif ($this->indexes[$mid] > $code ) {
                $min =  $mid;
                $height = $mid -1;
            }
        }

        if ($index === null) {
            $index = $min;
        }
        $position = $this->indexes[$index];
        return $this->positions[$position];
    }

    public function addNode($node)
    {
        if (isset($this->nodes[$node])) {
            return;
        }
        for ($i = 0; $i < $this->virtualNum; $i++) {
            $position = $this->hashCode($node . '-' . $i);
            $this->positions[$position] = $node;
            $this->nodes[$node][] = $position;
        }
        $this->sortPositions();
    }

    public function delNode($node)
    {
        if (!isset($this->nodes[$node])) {
            return;
        }
        foreach ($this->nodes[$node] as $position) {
            unset($this->positions[$position]);
        }
        unset($this->nodes[$node]);
    }

    public function sortPositions()
    {
        ksort($this->positions, SORT_REGULAR);
        $this->indexes = array_keys($this->positions);
        $this->len = count($this->indexes);
    }
}

$ch = new ConsistentHashing();

for ($i = 1; $i <= 10; $i++) {
    $ch->addNode($i);
}

$data = [];
for ($i = 1; $i <= 1000000; $i++) {
    $node = $ch->lookup($i);
    if (!isset($data[$node])) {
        $data[$node] = 0;
    }
    $data[$node]++;
}
print_r($data);
$avg = 100000;
$total = 0;
foreach ($data as $v) {
    $total += ($v - $avg) ** 2;
}
echo sqrt($total / 10);

Array
(
    [9] => 98147
    [10] => 99861
    [2] => 99196
    [7] => 100465
    [6] => 98903
    [4] => 103516
    [3] => 102046
    [5] => 95635
    [8] => 103289
    [1] => 98942
)
2303.4205434527%