代码如下：
<?php
function myHash($str) {
// hash(i) = hash(i-1) * 33 + str[i]
$hash = 0;
$s = md5($str);
$seed = 5;
$len = 32;
for ($i = 0; $i < $len; $i++) {
// (hash << 5) + hash 相当于 hash * 33
//$hash = sprintf("%u", $hash * 33) + ord($s{$i});
//$hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF;
$hash = ($hash << $seed) + $hash + ord($s{$i});
}
return $hash & 0x7FFFFFFF;
}
class ConsistentHash
{
// server列表
private $_server_list = array();
// 延迟排序，因为可能会执行多次addServer
private $_layze_sorted = FALSE;
public function addServer($server)
{
$hash = myHash($server);
$this->_layze_sorted = FALSE;
if (!isset($this->_server_list[$hash]))
{
$this->_server_list[$hash] = $server;
}
return $this;
}
public function find_my_hash($key='')
{
// 寻找区间值 比如当前 server_list已排好序的hash对照表为
// array( 3=>"server1",9=>"server2","30"=>"server3")
// 则 hash 会区分为3块
// 1 <3的 分布在server3
// 2 >=3的并且<9的 分布在server1
// 3 >=9的并且<30的 分布在server2
// 4 >=30的 分布在server3
$find_hash=myHash($key);//计算当前hash
$length=count($this->_server_list);
if($length==0){return false;}//如果是空的 返回false
if($length==1){return current($this->_server_list);}//如果是只有1个 就立即返回当前这个
if (!$this->_layze_sorted)
{
ksort($this->_server_list);//尚未排序 首次进行排序
$this->_layze_sorted = TRUE;//后面就不需要排序了
}
reset($this->_server_list);
$first_key=key($this->_server_list);//获取首个key
if($find_hash<$first_key)
{
return end($this->_server_list);//如果小于等于第一个 立即返回最后一个
}
reset($this->_server_list);//重置数组
$result=current($this->_server_list);//获取当前第一个作为假定的结果
foreach ($this->_server_list as $key => $v)
{
if($find_hash>=$key)
{
$result=$v;//如果要找的hash大于这个起点 认为该区域就是要寻找的区块
}else
{
reset($this->_server_list);
return $result;//要找的hash已经小于了当前区块起点 说明上一个就是要找的区块结果 立即返回
}
}
return $result;//最后也没找到说明 大于了最大值
}
}
$consisHash = new ConsistentHash();
for ($i=0; $i < 1000; $i++)
{
$consisHash->addServer("serv{$i}");
}
$start_time=microtime(true);
for ($i=0; $i < 10000; $i++)
{
var_dump("key{$i}-->".$consisHash->find_my_hash("key{$i}"));
}
$end_time=microtime(true);
$result=($end_time-$start_time)*1000;
var_dump($result);
?>
效果如图：
