当前位置:首页 > PHP教程 > php应用 > 列表

PHP实现的一致性HASH算法示例

发布:smiling 来源: PHP粉丝网  添加日期:2021-09-05 16:39:32 浏览: 评论:0 

这篇文章主要介绍了PHP实现的一致性HASH算法,结合具体实例形式分析了hash算法的具体定义与使用技巧,需要的朋友可以参考下,本文实例讲述了PHP实现的一致性HASH算法,分享给大家供大家参考,具体如下:

  1. <?php 
  2. // +---------------------------------------------------------------------- 
  3. // | Perfect Is Shit 
  4. // +---------------------------------------------------------------------- 
  5. // | PHP实现:一致性HASH算法 
  6. // +---------------------------------------------------------------------- 
  7. // | Author: alexander <gt199899@gmail.com> 
  8. // +---------------------------------------------------------------------- 
  9. // | Datetime: 2017-01-11 16:01:36 
  10. // +---------------------------------------------------------------------- 
  11. // | Copyright: Perfect Is Shit 
  12. // +---------------------------------------------------------------------- 
  13. class ConsistentHashing 
  14.   // 圆环 
  15.   // hash -> 节点 
  16.   private $_ring = array(); 
  17.   // 所有节点 
  18.   // 节点 -> hash 
  19.   public $nodes = array(); 
  20.   // 每个节点的虚拟节点 
  21.   public $virtual = 64; 
  22.   /** 
  23.    * 构造 
  24.    * @param array $nodes 初始化的节点列表 
  25.    */ 
  26.   public function __construct($nodes = array()) 
  27.   { 
  28.     if (!emptyempty($nodes)) { 
  29.       foreach ($nodes as $value) { 
  30.         $this->addNode($value); 
  31.       } 
  32.     } 
  33.   } 
  34.   /** 
  35.    * 获取圆环内容 
  36.    * @return array $this->_ring 
  37.    */ 
  38.   public function getRing() 
  39.   { 
  40.     return $this->_ring; 
  41.   } 
  42.   /** 
  43.    * time33 函数 
  44.    * @param string $str 
  45.    * @return 32位正整数 
  46.    * @author 大神们 
  47.    */ 
  48.   public function time33($str
  49.   { 
  50.     // hash(i) = hash(i-1) * 33 + str[i] 
  51.     // $hash = 5381; ## 将hash设置为0,竟然比设置为5381分布效果更好!!! 
  52.     $hash = 0; 
  53.     $s  = md5($str); //相比其它版本,进行了md5加密 
  54.     $seed = 5; 
  55.     $len = 32;//加密后长度32 
  56.     for ($i = 0; $i < $len$i++) { 
  57.       // (hash << 5) + hash 相当于 hash * 33 
  58.       //$hash = sprintf("%u", $hash * 33) + ord($s{$i}); 
  59.       //$hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF; 
  60.       $hash = ($hash << $seed) + $hash + ord($s{$i}); 
  61.     } 
  62.     return $hash & 0x7FFFFFFF; 
  63.   } 
  64.   /** 
  65.    * 增加节点 
  66.    * @param string $node 节点名称 
  67.    * @return object $this 
  68.    */ 
  69.   public function addNode($node
  70.   { 
  71.     if (in_array($nodearray_keys($this->nodes))) { 
  72.       return
  73.     } 
  74.     for ($i = 1; $i <= $this->virtual; $i++) { 
  75.       $key         = $this->time33($node . '-' . $i); 
  76.       $this->_ring[$key]  = $node
  77.       $this->nodes[$node][] = $key
  78.     } 
  79.     ksort($this->_ring, SORT_NUMERIC); 
  80.     return $this
  81.   } 
  82.   /** 
  83.    * 获取字符串的HASH在圆环上面映射到的节点 
  84.    * @param string $key 
  85.    * @return string $node 
  86.    */ 
  87.   public function getNode($key
  88.   { 
  89.     $node = current($this->_ring); 
  90.     $hash = $this->time33($key); 
  91.     foreach ($this->_ring as $key => $value) { 
  92.       if ($hash <= $key) { 
  93.         $node = $value
  94.         break
  95.       } 
  96.     } 
  97.     return $node
  98.   } 
  99.   /** 
  100.    * 获取映射到特定节点的KEY 
  101.    * 此方法需手动调用,非特殊情况不建议程序中使用此方法 
  102.    * @param string $node 
  103.    * @param string $keyPre 
  104.    * @return mixed 
  105.    */ 
  106.   public function getKey($node$keyPre = ""){ 
  107.     if(!in_array($nodearray_keys($this->nodes))){ 
  108.       return false; 
  109.     } 
  110.     $result = false; 
  111.     for($i=1;$i<=10000;$i++){ 
  112.       $key = $keyPre . md5(rand(1000, 9999)); 
  113.       if($this->getNode($key) == $node){ 
  114.         $result = true; 
  115.         break
  116.       } 
  117.     } 
  118.     return $result ? $key : false; 
  119.   } 
  120. $ch_obj = new ConsistentHashing(); 
  121. $ch_obj->addNode('node_1'); 
  122. $ch_obj->addNode('node_2'); 
  123. $ch_obj->addNode('node_3'); 
  124. $ch_obj->addNode('node_4'); 
  125. $ch_obj->addNode('node_5'); 
  126. $ch_obj->addNode('node_6'); 
  127. // +---------------------------------------------------------------------- 
  128. // | 查看key映射到的节点 
  129. // +---------------------------------------------------------------------- 
  130. $key1 = "asofiwjamfdalksjfkasasdflasfja"
  131. $key2 = "jaksldfjlasfjsdjfioafaslkjflsadkjfl"
  132. $key3 = "asjldflkjasfsdjflkajkldsjfksajdlflajs"
  133. $key4 = "iowanfasijfmasdnfoas"
  134. $key5 = "pqkisndfhoalnfiewlkl"
  135. $key6 = "qjklasjdifoajfalsjflsa"
  136. echo sprintf("%-50s 映射到节点 %s\n"$key1$ch_obj->getNode($key1)); 
  137. echo sprintf("%-50s 映射到节点 %s\n"$key2$ch_obj->getNode($key2)); 
  138. echo sprintf("%-50s 映射到节点 %s\n"$key3$ch_obj->getNode($key3)); 
  139. echo sprintf("%-50s 映射到节点 %s\n"$key4$ch_obj->getNode($key4)); 
  140. echo sprintf("%-50s 映射到节点 %s\n"$key5$ch_obj->getNode($key5)); 
  141. echo sprintf("%-50s 映射到节点 %s\n"$key6$ch_obj->getNode($key6)); 
  142. // +---------------------------------------------------------------------- 
  143. // | 查看圆环和节点信息 
  144. // +---------------------------------------------------------------------- 
  145. // var_dump($ch_obj->getRing()); 
  146. // var_dump($ch_obj->nodes); 
  147. // +---------------------------------------------------------------------- 
  148. // | 获取特定节点的KEY 
  149. // +---------------------------------------------------------------------- 
  150. // $key1 = $ch_obj->getKey('node_1', 'pre_'); 
  151. // var_dump($key1); 
  152. // +---------------------------------------------------------------------- 
  153. // | 测试分布 
  154. // +---------------------------------------------------------------------- 
  155. // $keys = array(); 
  156. // $rings = array(); 
  157. // for ($i = 1; $i <= 60000; $i++) { 
  158. //   $key = sha1(rand(1000000,9999999)); 
  159. //   $node = $ch_obj->getNode($key); 
  160. //   $rings[$node] = isset($rings[$node]) ? ++$rings[$node] : 1; 
  161. // } 
  162. // var_dump($rings); 

运行结果:

asofiwjamfdalksjfkasasdflasfja           映射到节点 node_1

jaksldfjlasfjsdjfioafaslkjflsadkjfl        映射到节点 node_2

asjldflkjasfsdjflkajkldsjfksajdlflajs       映射到节点 node_1

iowanfasijfmasdnfoas                映射到节点 node_2

pqkisndfhoalnfiewlkl                映射到节点 node_3

qjklasjdifoajfalsjflsa               映射到节点 node_5

Tags: HASH算法

分享到: