PHP实现的一致性哈希算法完整实例

这篇文章主要介绍了PHP实现的一致性哈希算法,以完整实例形式分析了PHP哈希算法的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下

本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考，具体如下：

1. <?php 
2. /** 
3. * Flexihash - A simple consistent hashing implementation for PHP. 
4. *  
5. * The MIT License 
6. *  
7. * Copyright (c) 2008 Paul Annesley 
8. *  
9. * Permission is hereby granted, free of charge, to any person obtaining a copy 
10. * of this software and associated documentation files (the "Software"), to deal 
11. * in the Software without restriction, including without limitation the rights 
12. * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
13. * copies of the Software, and to permit persons to whom the Software is 
14. * furnished to do so, subject to the following conditions: 
15. *  
16. * The above copyright notice and this permission notice shall be included in 
17. * all copies or substantial portions of the Software. 
18. *  
19. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
20. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
21. * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
22. * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
23. * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
24. * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
25. * THE SOFTWARE. 
26. *  
27. * @author Paul Annesley 
28. * @link http://paul.annesley.cc/ 
29. * @copyright Paul Annesley, 2008 
30. * @comment by MyZ (http://blog.csdn.net/mayongzhan) 
31. */ 
32. /** 
33. * A simple consistent hashing implementation with pluggable hash algorithms. 
34. * 
35. * @author Paul Annesley 
36. * @package Flexihash 
37. * @licence http://www.opensource.org/licenses/mit-license.php 
38. */ 
39. class Flexihash 
40. { 
41. /** 
42. * The number of positions to hash each target to. 
43. * 
44. * @var int 
45. * @comment 虚拟节点数,解决节点分布不均的问题 
46. */ 
47. private $_replicas = 64; 
48. /** 
49. * The hash algorithm, encapsulated in a Flexihash_Hasher implementation. 
50. * @var object Flexihash_Hasher 
51. * @comment 使用的hash方法 : md5,crc32 
52. */ 
53. private $_hasher; 
54. /** 
55. * Internal counter for current number of targets. 
56. * @var int 
57. * @comment 节点记数器 
58. */ 
59. private $_targetCount = 0; 
60. /** 
61. * Internal map of positions (hash outputs) to targets 
62. * @var array { position => target, ... } 
63. * @comment 位置对应节点,用于lookup中根据位置确定要访问的节点 
64. */ 
65. private $_positionToTarget = array(); 
66. /** 
67. * Internal map of targets to lists of positions that target is hashed to. 
68. * @var array { target => [ position, position, ... ], ... } 
69. * @comment 节点对应位置,用于删除节点 
70. */ 
71. private $_targetToPositions = array(); 
72. /** 
73. * Whether the internal map of positions to targets is already sorted. 
74. * @var boolean 
75. * @comment 是否已排序 
76. */ 
77. private $_positionToTargetSorted = false; 
78. /** 
79. * Constructor 
80. * @param object $hasher Flexihash_Hasher 
81. * @param int $replicas Amount of positions to hash each target to. 
82. * @comment 构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢 
83. */ 
84. public function __construct(Flexihash_Hasher $hasher = null, $replicas = null) 
85. { 
86. $this->_hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher(); 
87. if (!empty($replicas)) $this->_replicas = $replicas; 
88. } 
89. /** 
90. * Add a target. 
91. * @param string $target 
92. * @chainable 
93. * @comment 添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上 
94. */ 
95. public function addTarget($target) 
96. { 
97. if (isset($this->_targetToPositions[$target])) 
98. { 
99. throw new Flexihash_Exception("Target '$target' already exists."); 
100. } 
101. $this->_targetToPositions[$target] = array(); 
102. // hash the target into multiple positions 
103. for ($i = 0; $i < $this->_replicas; $i++) 
104. { 
105. $position = $this->_hasher->hash($target . $i); 
106. $this->_positionToTarget[$position] = $target; // lookup 
107. $this->_targetToPositions[$target] []= $position; // target removal 
108. } 
109. $this->_positionToTargetSorted = false; 
110. $this->_targetCount++; 
111. return $this; 
112. } 
113. /** 
114. * Add a list of targets. 
115. * @param array $targets 
116. * @chainable 
117. */ 
118. public function addTargets($targets) 
119. { 
120. foreach ($targets as $target) 
121. { 
122. $this->addTarget($target); 
123. } 
124. return $this; 
125. } 
126. /** 
127. * Remove a target. 
128. * @param string $target 
129. * @chainable 
130. */ 
131. public function removeTarget($target) 
132. { 
133. if (!isset($this->_targetToPositions[$target])) 
134. { 
135. throw new Flexihash_Exception("Target '$target' does not exist."); 
136. } 
137. foreach ($this->_targetToPositions[$target] as $position) 
138. { 
139. unset($this->_positionToTarget[$position]); 
140. } 
141. unset($this->_targetToPositions[$target]); 
142. $this->_targetCount--; 
143. return $this; 
144. } 
145. /** 
146. * A list of all potential targets 
147. * @return array 
148. */ 
149. public function getAllTargets() 
150. { 
151. return array_keys($this->_targetToPositions); 
152. } 
153. /** 
154. * Looks up the target for the given resource. 
155. * @param string $resource 
156. * @return string 
157. */ 
158. public function lookup($resource) 
159. { 
160. $targets = $this->lookupList($resource, 1); 
161. if (empty($targets)) throw new Flexihash_Exception('No targets exist'); 
162. return $targets[0]; 
163. } 
164. /** 
165. * Get a list of targets for the resource, in order of precedence. 
166. * Up to $requestedCount targets are returned, less if there are fewer in total. 
167. * 
168. * @param string $resource 
169. * @param int $requestedCount The length of the list to return 
170. * @return array List of targets 
171. * @comment 查找当前的资源对应的节点, 
172. * 节点为空则返回空,节点只有一个则返回该节点, 
173. * 对当前资源进行hash,对所有的位置进行排序,在有序的位置列上寻找当前资源的位置 
174. * 当全部没有找到的时候,将资源的位置确定为有序位置的第一个(形成一个环) 
175. * 返回所找到的节点 
176. */ 
177. public function lookupList($resource, $requestedCount) 
178. { 
179. if (!$requestedCount) 
180. throw new Flexihash_Exception('Invalid count requested'); 
181. // handle no targets 
182. if (empty($this->_positionToTarget)) 
183. return array(); 
184. // optimize single target 
185. if ($this->_targetCount == 1) 
186. return array_unique(array_values($this->_positionToTarget)); 
187. // hash resource to a position 
188. $resourcePosition = $this->_hasher->hash($resource); 
189. $results = array(); 
190. $collect = false; 
191. $this->_sortPositionTargets(); 
192. // search values above the resourcePosition 
193. foreach ($this->_positionToTarget as $key => $value) 
194. { 
195. // start collecting targets after passing resource position 
196. if (!$collect && $key > $resourcePosition) 
197. { 
198. $collect = true; 
199. } 
200. // only collect the first instance of any target 
201. if ($collect && !in_array($value, $results)) 
202. { 
203. $results []= $value; 
204. } 
205. // return when enough results, or list exhausted 
206. if (count($results) == $requestedCount || count($results) == $this->_targetCount) 
207. { 
208. return $results; 
209. } 
210. } 
211. // loop to start - search values below the resourcePosition 
212. foreach ($this->_positionToTarget as $key => $value) 
213. { 
214. if (!in_array($value, $results)) 
215. { 
216. $results []= $value; 
217. } 
218. // return when enough results, or list exhausted 
219. if (count($results) == $requestedCount || count($results) == $this->_targetCount) 
220. { 
221. return $results; 
222. } 
223. } 
224. // return results after iterating through both "parts" 
225. return $results; 
226. } 
227. public function __toString() 
228. { 
229. return sprintf( 
230. '%s{targets:[%s]}', 
231. get_class($this), 
232. implode(',', $this->getAllTargets()) 
233. ); 
234. } 
235. // ---------------------------------------- 
236. // private methods 
237. /** 
238. * Sorts the internal mapping (positions to targets) by position 
239. */ 
240. private function _sortPositionTargets() 
241. { 
242. // sort by key (position) if not already 
243. if (!$this->_positionToTargetSorted) 
244. { 
245. ksort($this->_positionToTarget, SORT_REGULAR); 
246. $this->_positionToTargetSorted = true; 
247. } 
248. } 
249. } 
250. /** 
251. * Hashes given values into a sortable fixed size address space. 
252. * 
253. * @author Paul Annesley 
254. * @package Flexihash 
255. * @licence http://www.opensource.org/licenses/mit-license.php 
256. */ 
257. interface Flexihash_Hasher 
258. { 
259. /** 
260. * Hashes the given string into a 32bit address space. 
261. * 
262. * Note that the output may be more than 32bits of raw data, for example 
263. * hexidecimal characters representing a 32bit value. 
264. * 
265. * The data must have 0xFFFFFFFF possible values, and be sortable by 
266. * PHP sort functions using SORT_REGULAR. 
267. * 
268. * @param string 
269. * @return mixed A sortable format with 0xFFFFFFFF possible values 
270. */ 
271. public function hash($string); 
272. } 
273. /** 
274. * Uses CRC32 to hash a value into a signed 32bit int address space. 
275. * Under 32bit PHP this (safely) overflows into negatives ints. 
276. * 
277. * @author Paul Annesley 
278. * @package Flexihash 
279. * @licence http://www.opensource.org/licenses/mit-license.php 
280. */ 
281. class Flexihash_Crc32Hasher 
282. implements Flexihash_Hasher 
283. { 
284. /* (non-phpdoc) 
285. * @see Flexihash_Hasher::hash() 
286. */ 
287. public function hash($string) 
288. { 
289. return crc32($string); 
290. } 
291. } 
292. /** 
293. * Uses CRC32 to hash a value into a 32bit binary string data address space. 
294. * 
295. * @author Paul Annesley 
296. * @package Flexihash 
297. * @licence http://www.opensource.org/licenses/mit-license.php 
298. */ 
299. class Flexihash_Md5Hasher 
300. implements Flexihash_Hasher 
301. { 
302. /* (non-phpdoc) 
303. * @see Flexihash_Hasher::hash() 
304. */ 
305. public function hash($string) 
306. { 
307. return substr(md5($string), 0, 8); // 8 hexits = 32bit 
308. // 4 bytes of binary md5 data could also be used, but 
309. // performance seems to be the same. 
310. } 
311. } 
312. /** 
313. * An exception thrown by Flexihash. 
314. * 
315. * @author Paul Annesley 
316. * @package Flexihash 
317. * @licence http://www.opensource.org/licenses/mit-license.php 
318. */ 
319. class Flexihash_Exception extends Exception 
320. { 
321. } 

希望本文所述对大家PHP程序设计有所帮助。