<?php
header("content-type:text/html;charset=utf-8");


/**
 * Flexihash - A PHP的简单一致的散列实现.
 *
 * 使用、复制、修改、合并、发布、分发、授权和/或销售
 * 按照下列条件提供家具:
 * 使用可插入散列算法的简单一致的散列实现.
 */

class Flexihash
{
    /**
     * The number of positions to hash each target to.
     *
     * @var int
     * @comment 虚拟节点数,解决节点分布不均的问题
     */
    private $_replicas = 3;
    /**
     * 哈希算法,封装在一个灵活的哈希哈希的实现中.
     * @var object Flexihash_Hasher
     * @comment 使用的hash方法 : md5,crc32
     */
    private $_hasher;
    /**
     * 当前目标数的内部计数器.
     * @var int
     * @comment 节点记数器
     */
    private $_targetCount = 0;
    /**
     * 位置的内部映射(散列输出)到目标
     * @var array { position => target, ... }
     * @comment 位置对应节点,用于lookup中根据位置确定要访问的节点
     */
    private $_positionToTarget = array();
    /**
     * 目标的内部映射到目标列表的列表.
     * @var array { target => [ position, position, ... ], ... }
     * @comment 节点对应位置,用于删除节点
     */
    private $_targetToPositions = array();
    /**
     * 对目标的内部映射是否已经进行了排序.
     * @var boolean
     * @comment 是否已排序
     */
    private $_positionToTargetSorted = false;
    /**
     * 构造函数
     * @param object $hasher Flexihash_Hasher
     * @param int $replicas 对每个目标进行散列的数量.
     * @comment 构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢
     */
    public function __construct(Flexihash_Hasher $hasher = null, $replicas = null)
    {
        $this->_hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher();
        if (!empty($replicas)) $this->_replicas = $replicas;
    }
    /**
     * 添加一个目标.
     * @param string $target
     * @chainable
     * @comment 添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上
     */
    public function addTarget($target)
    {
        if (isset($this->_targetToPositions[$target]))
        {
            throw new Flexihash_Exception("目标 '$target' 已经存在.");
        }
        $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
            $this->_targetToPositions[$target] []= $position; // target removal
        }
        $this->_positionToTargetSorted = false;
        $this->_targetCount++;
        return $this;
    }
    /**
     * 添加目标列表.
     * @param array $targets
     * @chainable
     */
    public function addTargets($targets)
    {
        foreach ($targets as $target)
        {
            $this->addTarget($target);
        }
        return $this;
    }
    /**
     * 删除一个目标.
     * @param string $target
     * @chainable
     */
    public function removeTarget($target)
    {
        if (!isset($this->_targetToPositions[$target]))
        {
            throw new Flexihash_Exception("Target '$target' does not exist.");
        }
        foreach ($this->_targetToPositions[$target] as $position)
        {
            unset($this->_positionToTarget[$position]);
        }
        unset($this->_targetToPositions[$target]);
        $this->_targetCount--;
        return $this;
    }
    /**
     * 所有潜在目标的列表
     * @return array
     */
    public function getAllTargets()
    {
        return array_keys($this->_targetToPositions);
    }

    /*
     * 获取目标节点
     * */
    public function get_targetToPositions($target,$_replicas = false)
    {
        if($_replicas){ $this->_replicas = $_replicas; }
        isset($this->_targetToPositions[$target])?$this->_targetToPositions[$target]:$this->addTarget($target);
        return $this->_targetToPositions[$target];
    }

    /*
     * 获取目标在哈希环上的临近节点
     * 返回:当前目标节点 临进目标及节点
     * */
    public function get_target($target)
    {
        $list_positionTos = array_keys($this->_positionToTarget);
        sort($list_positionTos);
        $this->_replicas = 1;
        $this->addTarget($target);
        $targets[$target] = $this->_targetToPositions[$target][0];
        foreach ($list_positionTos as $key=>$val)
        {
            if(isset($list_positionTos[$key+1]))
            {
                if($targets[$target]>$val&&$targets[$target]<=$list_positionTos[$key+1])
                {
                    $targets[$this->_positionToTarget[$val]] = $this->_targetToPositions[$this->_positionToTarget[$val]];
                }
            }else
            {
                if($targets[$target]<=$list_positionTos[0]||$targets[$target]>$val)
                {
                    $targets[$this->_positionToTarget[$val]] = $this->_targetToPositions[$this->_positionToTarget[$val]];
                }
            }
        }
        return $targets;
    }

    /**
     * 查找给定资源的目标.
     * @param string $resource
     * @return string
     */
    public function lookup($resource)
    {
        $targets = $this->lookupList($resource, 1);
        if (empty($targets)) throw new Flexihash_Exception('不存在的目标');
        return $targets[0];
    }
    /**
     * Get a list of targets for the resource, in order of precedence.
     * Up to $requestedCount targets are returned, less if there are fewer in total.
     *
     * @param string $resource
     * @param int $requestedCount The length of the list to return
     * @return array List of targets
     * @comment 查找当前的资源对应的节点,
     *     节点为空则返回空,节点只有一个则返回该节点,
     *     对当前资源进行hash,对所有的位置进行排序,在有序的位置列上寻找当前资源的位置
     *     当全部没有找到的时候,将资源的位置确定为有序位置的第一个(形成一个环)
     *     返回所找到的节点
     */
    public function lookupList($resource, $requestedCount)
    {
        if (!$requestedCount)
            throw new Flexihash_Exception('无效的请求数');
        // handle no targets
        if (empty($this->_positionToTarget))
            return array();
        // optimize single target
        if ($this->_targetCount == 1)
            return array_unique(array_values($this->_positionToTarget));
        // hash resource to a position
        $resourcePosition = $this->_hasher->hash($resource);
        $results = array();
        $collect = false;
        $this->_sortPositionTargets();
        // search values above the resourcePosition
        foreach ($this->_positionToTarget as $key => $value)
        {
            // start collecting targets after passing resource position
            if (!$collect && $key > $resourcePosition)
            {
                $collect = true;
            }
            // only collect the first instance of any target
            if ($collect && !in_array($value, $results))
            {
                $results []= $value;
            }
            // return when enough results, or list exhausted
            if (count($results) == $requestedCount || count($results) == $this->_targetCount)
            {
                return $results;
            }
        }
        // loop to start - search values below the resourcePosition
        foreach ($this->_positionToTarget as $key => $value)
        {
            if (!in_array($value, $results))
            {
                $results []= $value;
            }
            // return when enough results, or list exhausted
            if (count($results) == $requestedCount || count($results) == $this->_targetCount)
            {
                return $results;
            }
        }
        // return results after iterating through both "parts"
        return $results;
    }
    public function __toString()
    {
        return sprintf(
            '%s{targets:[%s]}',
            get_class($this),
            implode(',', $this->getAllTargets())
        );
    }
    // ----------------------------------------
    // private methods
    /**
     * Sorts the internal mapping (positions to targets) by position
     */
    private function _sortPositionTargets()
    {
        // sort by key (position) if not already
        if (!$this->_positionToTargetSorted)
        {
            ksort($this->_positionToTarget, SORT_REGULAR);
            $this->_positionToTargetSorted = true;
        }
    }
}
/**
 * Hashes given values into a sortable fixed size address space.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses/mit-license.php
 */
interface Flexihash_Hasher
{
    /**
     * Hashes the given string into a 32bit address space.
     *
     * Note that the output may be more than 32bits of raw data, for example
     * hexidecimal characters representing a 32bit value.
     *
     * The data must have 0xFFFFFFFF possible values, and be sortable by
     * PHP sort functions using SORT_REGULAR.
     *
     * @param string
     * @return mixed A sortable format with 0xFFFFFFFF possible values
     */
    public function hash($string);
}
/**
 * Uses CRC32 to hash a value into a signed 32bit int address space.
 * Under 32bit PHP this (safely) overflows into negatives ints.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses/mit-license.php
 */
class Flexihash_Crc32Hasher implements Flexihash_Hasher
{
    /* (non-phpdoc)
     * @see Flexihash_Hasher::hash()
     */
    public function hash($string)
    {
        return crc32($string);
    }
}
/**
 * Uses CRC32 to hash a value into a 32bit binary string data address space.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses/mit-license.php
 */
class Flexihash_Md5Hasher implements Flexihash_Hasher
{
    /* (non-phpdoc)
     * @see Flexihash_Hasher::hash()
     */
    public function hash($string)
    {
        return substr(md5($string), 0, 8); // 8 hexits = 32bit
        // 4 bytes of binary md5 data could also be used, but
        // performance seems to be the same.
    }
}
/**
 * An exception thrown by Flexihash.
 *
 * @author Paul Annesley
 * @package Flexihash
 * @licence http://www.opensource.org/licenses/mit-license.php
 */
class Flexihash_Exception extends Exception
{
}

 

---------------------------------------------------------------------------------------------
唯有志存高远,方能风行天下。

道之所存,虽千万人吾往矣! 情之所钟,虽千万里吾念矣~

原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。