欢迎来到 黑吧安全网 聚焦网络安全前沿资讯,精华内容,交流技术心得!

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

来源:本站整理 作者:佚名 时间:2015-11-16 TAG: 我要投稿

<?php
/**
 * Flexihash - A simple consistent hashing implementation for PHP.
 *
 * The MIT License
 *
 * Copyright (c) 2008 Paul Annesley
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 * @author Paul Annesley
 * @link http://paul.annesley.cc/
 * @copyright Paul Annesley, 2008
 * @comment by MyZ (http://blog.csdn.net/mayongzhan)
 */
/**
 * A simple consistent hashing implementation with pluggable hash algorithms.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses/mit-license.php
 */
class Flexihash
{
  /**
   * The number of positions to hash each target to.
   *
   * @var int
   * @comment 虚拟节点数,解决节点分布不均的问题
   */
  private $_replicas = 64;
  /**
   * The hash algorithm, encapsulated in a Flexihash_Hasher implementation.
   * @var object Flexihash_Hasher
   * @comment 使用的hash方法 : md5,crc32
   */
  private $_hasher;
  /**
   * Internal counter for current number of targets.
   * @var int
   * @comment 节点记数器
   */
  private $_targetCount = 0;
  /**
   * Internal map of positions (hash outputs) to targets
   * @var array { position => target, ... }
   * @comment 位置对应节点,用于lookup中根据位置确定要访问的节点
   */
  private $_positionToTarget = array();
  /**
   * Internal map of targets to lists of positions that target is hashed to.
   * @var array { target => [ position, position, ... ], ... }
   * @comment 节点对应位置,用于删除节点
   */
  private $_targetToPositions = array();
  /**
   * Whether the internal map of positions to targets is already sorted.
   * @var boolean
   * @comment 是否已排序
   */
  private $_positionToTargetSorted = false;
  /**
   * Constructor
   * @param object $hasher Flexihash_Hasher
   * @param int $replicas Amount of positions to hash each target to.
   * @comment 构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢
   */
  public function __construct(Flexihash_Hasher $hasher = null, $replicas = null)
  {
    $this->_hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher();
    if (!empty($replicas)) $this->_replicas = $replicas;
  }
  /**
   * Add a target.
   * @param string $target
   * @chainable
   * @comment 添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上
   */
  public function addTarget($target)
  {
    if (isset($this->_targetToPositions[$target]))
    {
      throw new Flexihash_Exception("Target '$target' already exists.");
    }
    $this->_targetToPositions[$target] = array();
    // hash the target into multiple positions
    for ($i = 0; $i < $this->_replicas; $i++)
    {
      $position = $this->_hasher->hash($target . $i);
      $this->_positionToTarget[$position] = $target; // lookup

[1] [2] [3]  下一页

【声明】:黑吧安全网(http://www.myhack58.com)登载此文出于传递更多信息之目的,并不代表本站赞同其观点和对其真实性负责,仅适于网络安全技术爱好者学习研究使用,学习中请遵循国家相关法律法规。如有问题请联系我们,联系邮箱admin@myhack58.com,我们会在最短的时间内进行处理。
  • 最新更新
    • 相关阅读
      • 本类热门
        • 最近下载