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

运行结果：

asofiwjamfdalksjfkasasdflasfja           映射到节点 node_1

jaksldfjlasfjsdjfioafaslkjflsadkjfl        映射到节点 node_2

asjldflkjasfsdjflkajkldsjfksajdlflajs       映射到节点 node_1

iowanfasijfmasdnfoas                映射到节点 node_2

pqkisndfhoalnfiewlkl                映射到节点 node_3

qjklasjdifoajfalsjflsa               映射到节点 node_5

Tags: HASH算法

分享到：