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

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

发布:smiling 来源: PHP粉丝网  添加日期:2021-06-26 19:13:38 浏览: 评论:0 

这篇文章主要介绍了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.    * The number of positions to hash each target to. 
  42.    * 
  43.    * @var int 
  44.    * @comment 虚拟节点数,解决节点分布不均的问题 
  45.    */ 
  46.   private $_replicas = 64; 
  47.   /** 
  48.    * The hash algorithm, encapsulated in a Flexihash_Hasher implementation. 
  49.    * @var object Flexihash_Hasher 
  50.    * @comment 使用的hash方法 : md5,crc32 
  51.    */ 
  52.   private $_hasher
  53.   /** 
  54.    * Internal counter for current number of targets. 
  55.    * @var int 
  56.    * @comment 节点记数器 
  57.    */ 
  58.   private $_targetCount = 0; 
  59.   /** 
  60.    * Internal map of positions (hash outputs) to targets 
  61.    * @var array { position => target, ... } 
  62.    * @comment 位置对应节点,用于lookup中根据位置确定要访问的节点 
  63.    */ 
  64.   private $_positionToTarget = array(); 
  65.   /** 
  66.    * Internal map of targets to lists of positions that target is hashed to. 
  67.    * @var array { target => [ position, position, ... ], ... } 
  68.    * @comment 节点对应位置,用于删除节点 
  69.    */ 
  70.   private $_targetToPositions = array(); 
  71.   /** 
  72.    * Whether the internal map of positions to targets is already sorted. 
  73.    * @var boolean 
  74.    * @comment 是否已排序 
  75.    */ 
  76.   private $_positionToTargetSorted = false; 
  77.   /** 
  78.    * Constructor 
  79.    * @param object $hasher Flexihash_Hasher 
  80.    * @param int $replicas Amount of positions to hash each target to. 
  81.    * @comment 构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢 
  82.    */ 
  83.   public function __construct(Flexihash_Hasher $hasher = null, $replicas = null) 
  84.   { 
  85.     $this->_hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher(); 
  86.     if (!emptyempty($replicas)) $this->_replicas = $replicas
  87.   } 
  88.   /** 
  89.    * Add a target. 
  90.    * @param string $target 
  91.    * @chainable 
  92.    * @comment 添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上 
  93.    */ 
  94.   public function addTarget($target
  95.   { 
  96.     if (isset($this->_targetToPositions[$target])) 
  97.     { 
  98.       throw new Flexihash_Exception("Target '$target' already exists."); 
  99.     } 
  100.     $this->_targetToPositions[$target] = array(); 
  101.     // hash the target into multiple positions 
  102.     for ($i = 0; $i < $this->_replicas; $i++) 
  103.     { 
  104.       $position = $this->_hasher->hash($target . $i); 
  105.       $this->_positionToTarget[$position] = $target// lookup 
  106.       $this->_targetToPositions[$target] []= $position// target removal 
  107.     } 
  108.     $this->_positionToTargetSorted = false; 
  109.     $this->_targetCount++; 
  110.     return $this
  111.   } 
  112.   /** 
  113.    * Add a list of targets. 
  114.    * @param array $targets 
  115.    * @chainable 
  116.    */ 
  117.   public function addTargets($targets
  118.   { 
  119.     foreach ($targets as $target
  120.     { 
  121.       $this->addTarget($target); 
  122.     } 
  123.     return $this
  124.   } 
  125.   /** 
  126.    * Remove a target. 
  127.    * @param string $target 
  128.    * @chainable 
  129.    */ 
  130.   public function removeTarget($target
  131.   { 
  132.     if (!isset($this->_targetToPositions[$target])) 
  133.     { 
  134.       throw new Flexihash_Exception("Target '$target' does not exist."); 
  135.     } 
  136.     foreach ($this->_targetToPositions[$targetas $position
  137.     { 
  138.       unset($this->_positionToTarget[$position]); 
  139.     } 
  140.     unset($this->_targetToPositions[$target]); 
  141.     $this->_targetCount--; 
  142.     return $this
  143.   } 
  144.   /** 
  145.    * A list of all potential targets 
  146.    * @return array 
  147.    */ 
  148.   public function getAllTargets() 
  149.   { 
  150.     return array_keys($this->_targetToPositions); 
  151.   } 
  152.   /** 
  153.    * Looks up the target for the given resource. 
  154.    * @param string $resource 
  155.    * @return string 
  156.    */ 
  157.   public function lookup($resource
  158.   { 
  159.     $targets = $this->lookupList($resource, 1); 
  160.     if (emptyempty($targets)) throw new Flexihash_Exception('No targets exist'); 
  161.     return $targets[0]; 
  162.   } 
  163.   /** 
  164.    * Get a list of targets for the resource, in order of precedence. 
  165.    * Up to $requestedCount targets are returned, less if there are fewer in total. 
  166.    * 
  167.    * @param string $resource 
  168.    * @param int $requestedCount The length of the list to return 
  169.    * @return array List of targets 
  170.    * @comment 查找当前的资源对应的节点, 
  171.    *     节点为空则返回空,节点只有一个则返回该节点, 
  172.    *     对当前资源进行hash,对所有的位置进行排序,在有序的位置列上寻找当前资源的位置 
  173.    *     当全部没有找到的时候,将资源的位置确定为有序位置的第一个(形成一个环) 
  174.    *     返回所找到的节点 
  175.    */ 
  176.   public function lookupList($resource$requestedCount
  177.   { 
  178.     if (!$requestedCount
  179.       throw new Flexihash_Exception('Invalid count requested'); 
  180.     // handle no targets 
  181.     if (emptyempty($this->_positionToTarget)) 
  182.       return array(); 
  183.     // optimize single target 
  184.     if ($this->_targetCount == 1) 
  185.       return array_unique(array_values($this->_positionToTarget)); 
  186.     // hash resource to a position 
  187.     $resourcePosition = $this->_hasher->hash($resource); 
  188.     $results = array(); 
  189.     $collect = false; 
  190.     $this->_sortPositionTargets(); 
  191.     // search values above the resourcePosition 
  192.     foreach ($this->_positionToTarget as $key => $value
  193.     { 
  194.       // start collecting targets after passing resource position 
  195.       if (!$collect && $key > $resourcePosition
  196.       { 
  197.         $collect = true; 
  198.       } 
  199.       // only collect the first instance of any target 
  200.       if ($collect && !in_array($value$results)) 
  201.       { 
  202.         $results []= $value
  203.       } 
  204.       // return when enough results, or list exhausted 
  205.       if (count($results) == $requestedCount || count($results) == $this->_targetCount) 
  206.       { 
  207.         return $results
  208.       } 
  209.     } 
  210.     // loop to start - search values below the resourcePosition 
  211.     foreach ($this->_positionToTarget as $key => $value
  212.     { 
  213.       if (!in_array($value$results)) 
  214.       { 
  215.         $results []= $value
  216.       } 
  217.       // return when enough results, or list exhausted 
  218.       if (count($results) == $requestedCount || count($results) == $this->_targetCount) 
  219.       { 
  220.         return $results
  221.       } 
  222.     } 
  223.     // return results after iterating through both "parts" 
  224.     return $results
  225.   } 
  226.   public function __toString() 
  227.   { 
  228.     return sprintf( 
  229.       '%s{targets:[%s]}'
  230.       get_class($this), 
  231.       implode(','$this->getAllTargets()) 
  232.     ); 
  233.   } 
  234.   // ---------------------------------------- 
  235.   // private methods 
  236.   /** 
  237.    * Sorts the internal mapping (positions to targets) by position 
  238.    */ 
  239.   private function _sortPositionTargets() 
  240.   { 
  241.     // sort by key (position) if not already 
  242.     if (!$this->_positionToTargetSorted) 
  243.     { 
  244.       ksort($this->_positionToTarget, SORT_REGULAR); 
  245.       $this->_positionToTargetSorted = true; 
  246.     } 
  247.   } 
  248. /** 
  249.  * Hashes given values into a sortable fixed size address space. 
  250.  * 
  251.  * @author Paul Annesley 
  252.  * @package Flexihash 
  253.  * @licence http://www.opensource.org/licenses/mit-license.php 
  254.  */ 
  255. interface Flexihash_Hasher 
  256.   /** 
  257.    * Hashes the given string into a 32bit address space. 
  258.    * 
  259.    * Note that the output may be more than 32bits of raw data, for example 
  260.    * hexidecimal characters representing a 32bit value. 
  261.    * 
  262.    * The data must have 0xFFFFFFFF possible values, and be sortable by 
  263.    * PHP sort functions using SORT_REGULAR. 
  264.    * 
  265.    * @param string 
  266.    * @return mixed A sortable format with 0xFFFFFFFF possible values 
  267.    */ 
  268.   public function hash($string); 
  269. /** 
  270.  * Uses CRC32 to hash a value into a signed 32bit int address space. 
  271.  * Under 32bit PHP this (safely) overflows into negatives ints. 
  272.  * 
  273.  * @author Paul Annesley 
  274.  * @package Flexihash 
  275.  * @licence http://www.opensource.org/licenses/mit-license.php 
  276.  */ 
  277. class Flexihash_Crc32Hasher 
  278.   implements Flexihash_Hasher 
  279.   /* (non-phpdoc) 
  280.    * @see Flexihash_Hasher::hash() 
  281.    */ 
  282.   public function hash($string
  283.   { 
  284.     return crc32($string); 
  285.   } 
  286. /** 
  287.  * Uses CRC32 to hash a value into a 32bit binary string data address space. 
  288.  * 
  289.  * @author Paul Annesley 
  290.  * @package Flexihash 
  291.  * @licence http://www.opensource.org/licenses/mit-license.php 
  292.  */ 
  293. class Flexihash_Md5Hasher 
  294.   implements Flexihash_Hasher 
  295.   /* (non-phpdoc) 
  296.    * @see Flexihash_Hasher::hash() 
  297.    */ 
  298.   public function hash($string
  299.   { 
  300.     return substr(md5($string), 0, 8); // 8 hexits = 32bit 
  301.     // 4 bytes of binary md5 data could also be used, but 
  302.     // performance seems to be the same. 
  303.   } 
  304. /** 
  305.  * An exception thrown by Flexihash. 
  306.  * 
  307.  * @author Paul Annesley 
  308.  * @package Flexihash 
  309.  * @licence http://www.opensource.org/licenses/mit-license.php 
  310.  */ 
  311. class Flexihash_Exception extends Exception 
希望本文所述对大家PHP程序设计有所帮助。

Tags: PHP哈希算法

分享到: