一貫性のあるハッシュ - PHP

/**
* Flexihash - PHP 用の単純な一貫したハッシュの実装です。
*
* MIT ライセンス
*
* Copyright (c) 2008 Paul Annesley
*
* コピーを入手する人には、ここに無料で許可が与えられます
* このソフトウェアおよび関連ドキュメント ファイル (「ソフトウェア」) を、使用、コピー、変更、マージ、公開、配布、サブライセンス、および/または使用する権利
* を含むがこれらに限定されずに、ソフトウェアを無制限に取引するための権利
*以下の条件に従って、ソフトウェアのコピーを販売
*し、ソフトウェアが提供された人にその販売を許可する
*:
*
* 上記の著作権表示およびこの許可通知は、
* すべてのコピーに含まれるものとします。
*
* ソフトウェアは「現状のまま」で提供され、明示的または黙示的、商品性、
* 特定目的への適合性の保証を含むがこれらに限定されない、いかなる種類の保証も行われません。非侵害。いかなる場合においても、
* 作者または著作権所有者は、契約行為、不法行為またはその他の行為であるかどうかにかかわらず、
* に起因する、またはソフトウェアまたはそれに関連して生じる、あらゆる請求、損害、その他の
* 責任に対して責任を負わないものとします。
* ソフトウェアの使用またはその他の取引。
*
* @author Paul Annesley
* @link http://paul.annesley.cc/
* @copyright Paul Annesley、2008
* MyZ による @comment (http:/ /blog.csdn.net/mayongzhan)
 */
/**
* プラガブルなハッシュ アルゴリズムを使用したシンプルな一貫性のあるハッシュの実装。
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
 */
class Flexihash
{
/**
* 各ターゲットをハッシュする位置の数
*
* @var int
* @comment 不均一なノード分散の問題を解決するための仮想ノードの数
*/
private $_replicas = 64;
/**
* Flexihash_Hasher 実装にカプセル化されたハッシュ アルゴリズム。
* @var object Flexihash_Hasher
* @comment 使用するハッシュ メソッド : md5,crc32
*/
private $_hasher;
/**
* 現在のターゲット数の内部カウンター
* @var int
* @comment ノードカウンター
*/
private $_targetCount = 0;
/**
* ターゲットへの位置 (ハッシュ出力) の内部マップ
* @var array {position => target, ... }
* @comment ルックアップの位置に基づいて訪問するノードを決定するために使用される、位置に対応するノード
*/
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 コンストラクターは、使用するハッシュ方法と必要な仮想ノードの数を決定します。仮想ノードの数が多いほど、分散はより均一になりますが、プログラムの分散操作は遅くなります
*/
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();
// ターゲットを複数の位置にハッシュします
for ($i = 0; $i < $this->_replicas; $i++)
{
$position = $this->_hasher- >hash($target . $i);
$this->_positionToTarget[$position] = $target; // lookup
$this->_targetToPositions[$target] []= $position; // ターゲットの削除
}
$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' は存在しません。");
}
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);
}
/**
* 指定されたリソースのターゲットを検索します。
* @param string $resource
* @return string
*/
public function lookup($resource)
{
$targets = $this->lookupList($resource, 1);
if ( empty($targets)) throw new Flexihash_Exception('ターゲットが存在しません');
return $targets[0];
}
/**
* リソースのターゲットのリストを優先順位順に取得します。
* $requestedCount までのターゲットが返されますが、合計が少ない場合は少なくなります。
*
* @param string $resource
* @param int $requestedCount返すリストの長さ
* @return array ターゲットのリスト
* @comment 現在のリソースに対応するノードを見つけます
* ノードが空の場合は空を返し、ノードが 1 つしかない場合はノードを返し、
*ハッシュし、すべての位置をソートし、順序付けされた位置列で現在のリソースの位置を見つけます
* すべて見つからない場合は、リソースの位置を最初の順序付けされた位置として決定します(リングを形成します)
* ノードを返します見つけました
*/
public function lookupList($resource, $requestedCount)
{
if (!$requestedCount)
throw new Flexihash_Exception('Invalid count requested');
// ターゲットを処理しません
if (empty($this->_positionToTarget))
return array();
// 単一のターゲットを最適化します
if ($this->_targetCount == 1)
return array_unique(array_values($this->>_positionToTarget));
// リソースを位置にハッシュします
$resourcePosition = $this-> _hasher->hash($resource);
$results = array();
$collect = false;
$this->_sortPositionTargets();
// resourcePosition
foreach ($this-> _positionToTarget as $key => $value)
{
// リソース位置を渡した後にターゲットの収集を開始します
if (!$collect && $key > $resourcePosition)
{
$collect = true;
}
// ターゲットの最初のインスタンスのみを収集します
if ($collect && !in_array($value, $results))
{
$results []= $value;
}
// 十分な結果が得られた場合、またはリストが枯渇した場合に返されます
if (count($results) == $requestedCount || count($results) == $this->_targetCount)
{
return $results;
}
}
// 開始するループ - resourcePosition
foreach ($this->_positionToTarget) より下の値を検索as $key => $value)
{
if (!in_array($value, $results))
{
$results []= $value;
}
// 十分な結果が得られた場合、またはリストが枯渇した場合に返す
if (count($results) == $requestedCount || count($results) == $this->_targetCount)
{
return $results;
}
}
// 両方の「部分」を反復した後に結果を返します
return $results;
}
public function __toString()
{
return sprintf(
'%s{targets:[%s]}',
get_class($this),
implode(',', $this-> ;getAllTargets())
);
}
// ------------------------------------- ---
// プライベートメソッド
/**
* 内部マッピング (位置からターゲットへ) を位置ごとに並べ替えます
*/
プライベート関数 _sortPositionTargets()
{
// まだキー (位置) でソートされていない場合は
if (!$this->_positionToTargetSorted)
{
ksort($this->_positionToTarget, SORT_REGULAR);
$this->_positionToTargetSorted = true;
}
}
}
/**
* 指定された値をソート可能な固定サイズのアドレス空間にハッシュします。
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
 */
インターフェース Flexihash_Hasher
{
/**
* 指定された文字列を 32 ビットのアドレス空間にハッシュします。
*
* 出力は 32 ビットを超える生データになる可能性があることに注意してください。たとえば、
* 32 ビット値を表す 16 進文字です。
*
* データには 0xFFFFFFFF が含まれている必要があります。値を並べ替え可能です
* SORT_REGULAR を使用した PHP ソート関数
*
* @param string
* @returnmixed 0xFFFFFFFF の可能な値を持つ並べ替え可能な形式
*/
パブリック関数ハッシュ($string);
}
/**
* CRC32 を使用して、値を符号付き 32 ビット int アドレス空間にハッシュします。
* 32 ビット PHP では、これは (安全に) 負の int にオーバーフローします。
*
* @author Paul Annesley
* @package Flexihash
* @licence http:/ /www.opensource.org/licenses/mit-license.php
 */
class Flexihash_Crc32Hasher
implements Flexihash_Hasher
{
/* (非phpdoc)
* @see Flexihash_Hasher::hash()
*/
public function hash($string)
{
return crc32($string);
}
}
/**
* CRC32 を使用して、値を 32 ビット バイナリ文字列データ アドレス空間にハッシュします。
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license. php
 */
class Flexihash_Md5Hasher
Flexihash_Hasherを実装します
{
/* (non-phpdoc)
* @see Flexihash_Hasher::hash()
*/
public function hash($string)
{
return substr(md5($string), 0, 8); // 8 hexits = 32bit
// 4 バイトのバイナリ md5 データも使用できますが、
//
}
}
/**
* Flexihash によってスローされた 例外。
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
 */
class Flexihash_ExceptionはException
{
}

上記は例外コンテンツを含む一貫性のあるハッシュ - php を紹介しました。PHP チュートリアルに興味のある友人に役立つことを願っています。