这篇文章主要介绍了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 (!emptyempty($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 (emptyempty($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 (emptyempty($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. } 

Tags: PHP哈希算法

分享到：