<?php
class Hash
{
    private $servers;
    private $virMap;
    private $virNum = 10; //服务器虚节点个数
    private $data;
    /**
     * 配置单服务器虚节点数量
     */
    public function setVirNum($virNum)
    {
        $this->virNum = $virNum;
    }
    /**
     * 增加服务器
     * @param string $name #服务器名称
     */
    public function addServer($name)
    {
        $this->servers[$name] = $name;
        for($i=0;$i<$this->virNum;$i++) {
            $vname = $name.'#'.$i;
            $posi  = static::hashVal($vname);
            $this->virMap['posi'][$posi]        = $name;
            $this->virMap['name'][$name][$posi] = $vname;
        }
        ksort($this->virMap['posi']);
    }
    /**
     * 移除服务器
     * @param string $name #服务器名称
     */
    public function delServer($name)
    {
        if (isset($this->virMap['name'][$name])) {
            $list = $this->virMap['name'][$name];
            foreach ($list as $posi => $vname) {
                unset($this->virMap['posi'][$posi]);
            }
            unset($this->virMap['name'][$name]);
        }
    }
    /**
     * 缓存设置
     * @param string $key #key
     * @param mixed  $val #value
     */
    public function set($key, $val)
    {
        $server = $this->findServer($key);
        $this->data[$server][$key] = $val;
    }
    /**
     * 缓存获取
     * @param string $key #key
     */
    public function get($key)
    {
        $server = $this->findServer($key);
        return isset($this->data[$server][$key])?$this->data[$server][$key]:null;
    }
    /**
     * 寻找key所在的服务器
     * @param string $key
     */
    public function findServer($key)
    {
        $keyPos = static::hashVal($key);
        $posi   = $this->findVirServerPos($keyPos);
        return $this->virMap['posi'][$posi];
    }
    /**
     * 根据key的hash值计算应该存储的虚拟结点
     * @param int $keyPos
     */
    public function findVirServerPos($keyPos)
    {
        $list = array_keys($this->virMap['posi']);
        $low  = 0;
        $high = count($list) - 1;
        while ($low <= $high) {
            $mid = intval(($low + $high) / 2);
            if ($list[$mid] > $keyPos) {
                $high = $mid;
            } else if ($list[$mid] < $keyPos) {
                $low  = $mid;
            } else {
                return $list[$mid];
            }
            if ($low+1 == $high) {
                if ($keyPos <= $list[$low]) {
                    return $list[$low];
                } else {
                    return $list[$high];
                }
            }
        }
        return $list[$high];
    }
    /**
     * 字符串转hash值算法
     * @param string $str
     */
    public static function hashVal($str)
    {
        $str = sha1($str);
        return sprintf('%u', crc32($str));
    }
}

$serverNum = isset($argv[1])?(int)$argv[1]:10;
$testNum   = isset($argv[2])?(int)$argv[2]:1000000;
$keyPre    = isset($argv[3])?$argv[3]:'key';
if ($serverNum <= 0) $serverNum = 10;
$hash    = new Hash();
$servers = [];
for ($i=1;$i<=$serverNum;$i++) {
    $name = "server".$i;
    $hash->addServer($name);
    $servers[$name] = 0;
}
for ($i=1;$i<=$testNum;$i++) {
    $name = $hash->findServer($keyPre.'#'.$i);
    $servers[$name] ++;
}
$avg = array_sum($servers) / $serverNum;
$ret = 0;
foreach ($servers as $val) {
    $ret += pow($val - $avg, 2);
}
$ret = number_format(sqrt($ret/$serverNum), 2, ".", "");
foreach ($servers as $name=>$val) {
    echo "服务器".$name." 存储数量：".$val."\n";
}
echo "******************\n";
echo "服务器数".$serverNum." 测试".$testNum." 标准方差=".$ret."\n";

F:\软件架构师\极客大学>php ch5.php 10 1000000 k2
服务器server1 存储数量：132545
服务器server2 存储数量：86661
服务器server3 存储数量：55324
服务器server4 存储数量：98202
服务器server5 存储数量：119108
服务器server6 存储数量：60348
服务器server7 存储数量：80375
服务器server8 存储数量：73794
服务器server9 存储数量：159036
服务器server10 存储数量：134607
******************
服务器数10 测试1000000 标准方差=33058.24

F:\软件架构师\极客大学>php ch5.php 10 1000000 keytest
服务器server1 存储数量：132552
服务器server2 存储数量：87176
服务器server3 存储数量：55597
服务器server4 存储数量：97463
服务器server5 存储数量：118772
服务器server6 存储数量：60161
服务器server7 存储数量：81138
服务器server8 存储数量：73812
服务器server9 存储数量：158998
服务器server10 存储数量：134331
******************
服务器数10 测试1000000 标准方差=32928.18