PHP实现的一致性哈希算法完整实例
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考，具体如下：
<?php
/**
*Flexihash-AsimpleconsistenthashingimplementationforPHP.
*
*TheMITLicense
*
*Copyright(c)2008PaulAnnesley
*
*Permissionisherebygranted,freeofcharge,toanypersonobtainingacopy
*ofthissoftwareandassociateddocumentationfiles(the"Software"),todeal
*intheSoftwarewithoutrestriction,includingwithoutlimitationtherights
*touse,copy,modify,merge,publish,distribute,sublicense,and/orsell
*copiesoftheSoftware,andtopermitpersonstowhomtheSoftwareis
*furnishedtodoso,subjecttothefollowingconditions:
*
*Theabovecopyrightnoticeandthispermissionnoticeshallbeincludedin
*allcopiesorsubstantialportionsoftheSoftware.
*
*THESOFTWAREISPROVIDED"ASIS",WITHOUTWARRANTYOFANYKIND,EXPRESSOR
*IMPLIED,INCLUDINGBUTNOTLIMITEDTOTHEWARRANTIESOFMERCHANTABILITY,
*FITNESSFORAPARTICULARPURPOSEANDNONINFRINGEMENT.INNOEVENTSHALLTHE
*AUTHORSORCOPYRIGHTHOLDERSBELIABLEFORANYCLAIM,DAMAGESOROTHER
*LIABILITY,WHETHERINANACTIONOFCONTRACT,TORTOROTHERWISE,ARISINGFROM,
*OUTOFORINCONNECTIONWITHTHESOFTWAREORTHEUSEOROTHERDEALINGSIN
*THESOFTWARE.
*
*@authorPaulAnnesley
*@linkhttp://paul.annesley.cc/
*@copyrightPaulAnnesley,2008
*@commentbyMyZ(http://blog.csdn.net/mayongzhan)
*/
/**
*Asimpleconsistenthashingimplementationwithpluggablehashalgorithms.
*
*@authorPaulAnnesley
*@packageFlexihash
*@licencehttp://www.opensource.org/licenses/mit-license.php
*/
classFlexihash
{
/**
*Thenumberofpositionstohasheachtargetto.
*
*@varint
*@comment虚拟节点数,解决节点分布不均的问题
*/
private$_replicas=64;
/**
*Thehashalgorithm,encapsulatedinaFlexihash_Hasherimplementation.
*@varobjectFlexihash_Hasher
*@comment使用的hash方法:md5,crc32
*/
private$_hasher;
/**
*Internalcounterforcurrentnumberoftargets.
*@varint
*@comment节点记数器
*/
private$_targetCount=0;
/**
*Internalmapofpositions(hashoutputs)totargets
*@vararray{position=>target,...}
*@comment位置对应节点,用于lookup中根据位置确定要访问的节点
*/
private$_positionToTarget=array();
/**
*Internalmapoftargetstolistsofpositionsthattargetishashedto.
*@vararray{target=>[position,position,...],...}
*@comment节点对应位置,用于删除节点
*/
private$_targetToPositions=array();
/**
*Whethertheinternalmapofpositionstotargetsisalreadysorted.
*@varboolean
*@comment是否已排序
*/
private$_positionToTargetSorted=false;
/**
*Constructor
*@paramobject$hasherFlexihash_Hasher
*@paramint$replicasAmountofpositionstohasheachtargetto.
*@comment构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢
*/
publicfunction__construct(Flexihash_Hasher$hasher=null,$replicas=null)
{
$this->_hasher=$hasher?$hasher:newFlexihash_Crc32Hasher();
if(!empty($replicas))$this->_replicas=$replicas;
}
/**
*Addatarget.
*@paramstring$target
*@chainable
*@comment添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上
*/
publicfunctionaddTarget($target)
{
if(isset($this->_targetToPositions[$target]))
{
thrownewFlexihash_Exception("Target'$target'alreadyexists.");
}
$this->_targetToPositions[$target]=array();
//hashthetargetintomultiplepositions
for($i=0;$i<$this->_replicas;$i++)
{
$position=$this->_hasher->hash($target.$i);
$this->_positionToTarget[$position]=$target;//lookup
$this->_targetToPositions[$target][]=$position;//targetremoval
}
$this->_positionToTargetSorted=false;
$this->_targetCount++;
return$this;
}
/**
*Addalistoftargets.
*@paramarray$targets
*@chainable
*/
publicfunctionaddTargets($targets)
{
foreach($targetsas$target)
{
$this->addTarget($target);
}
return$this;
}
/**
*Removeatarget.
*@paramstring$target
*@chainable
*/
publicfunctionremoveTarget($target)
{
if(!isset($this->_targetToPositions[$target]))
{
thrownewFlexihash_Exception("Target'$target'doesnotexist.");
}
foreach($this->_targetToPositions[$target]as$position)
{
unset($this->_positionToTarget[$position]);
}
unset($this->_targetToPositions[$target]);
$this->_targetCount--;
return$this;
}
/**
*Alistofallpotentialtargets
*@returnarray
*/
publicfunctiongetAllTargets()
{
returnarray_keys($this->_targetToPositions);
}
/**
*Looksupthetargetforthegivenresource.
*@paramstring$resource
*@returnstring
*/
publicfunctionlookup($resource)
{
$targets=$this->lookupList($resource,1);
if(empty($targets))thrownewFlexihash_Exception('Notargetsexist');
return$targets[0];
}
/**
*Getalistoftargetsfortheresource,inorderofprecedence.
*Upto$requestedCounttargetsarereturned,lessiftherearefewerintotal.
*
*@paramstring$resource
*@paramint$requestedCountThelengthofthelisttoreturn
*@returnarrayListoftargets
*@comment查找当前的资源对应的节点,
*节点为空则返回空,节点只有一个则返回该节点,
*对当前资源进行hash,对所有的位置进行排序,在有序的位置列上寻找当前资源的位置
*当全部没有找到的时候,将资源的位置确定为有序位置的第一个(形成一个环)
*返回所找到的节点
*/
publicfunctionlookupList($resource,$requestedCount)
{
if(!$requestedCount)
thrownewFlexihash_Exception('Invalidcountrequested');
//handlenotargets
if(empty($this->_positionToTarget))
returnarray();
//optimizesingletarget
if($this->_targetCount==1)
returnarray_unique(array_values($this->_positionToTarget));
//hashresourcetoaposition
$resourcePosition=$this->_hasher->hash($resource);
$results=array();
$collect=false;
$this->_sortPositionTargets();
//searchvaluesabovetheresourcePosition
foreach($this->_positionToTargetas$key=>$value)
{
//startcollectingtargetsafterpassingresourceposition
if(!$collect&&$key>$resourcePosition)
{
$collect=true;
}
//onlycollectthefirstinstanceofanytarget
if($collect&&!in_array($value,$results))
{
$results[]=$value;
}
//returnwhenenoughresults,orlistexhausted
if(count($results)==$requestedCount||count($results)==$this->_targetCount)
{
return$results;
}
}
//looptostart-searchvaluesbelowtheresourcePosition
foreach($this->_positionToTargetas$key=>$value)
{
if(!in_array($value,$results))
{
$results[]=$value;
}
//returnwhenenoughresults,orlistexhausted
if(count($results)==$requestedCount||count($results)==$this->_targetCount)
{
return$results;
}
}
//returnresultsafteriteratingthroughboth"parts"
return$results;
}
publicfunction__toString()
{
returnsprintf(
'%s{targets:[%s]}',
get_class($this),
implode(',',$this->getAllTargets())
);
}
//----------------------------------------
//privatemethods
/**
*Sortstheinternalmapping(positionstotargets)byposition
*/
privatefunction_sortPositionTargets()
{
//sortbykey(position)ifnotalready
if(!$this->_positionToTargetSorted)
{
ksort($this->_positionToTarget,SORT_REGULAR);
$this->_positionToTargetSorted=true;
}
}
}
/**
*Hashesgivenvaluesintoasortablefixedsizeaddressspace.
*
*@authorPaulAnnesley
*@packageFlexihash
*@licencehttp://www.opensource.org/licenses/mit-license.php
*/
interfaceFlexihash_Hasher
{
/**
*Hashesthegivenstringintoa32bitaddressspace.
*
*Notethattheoutputmaybemorethan32bitsofrawdata,forexample
*hexidecimalcharactersrepresentinga32bitvalue.
*
*Thedatamusthave0xFFFFFFFFpossiblevalues,andbesortableby
*PHPsortfunctionsusingSORT_REGULAR.
*
*@paramstring
*@returnmixedAsortableformatwith0xFFFFFFFFpossiblevalues
*/
publicfunctionhash($string);
}
/**
*UsesCRC32tohashavalueintoasigned32bitintaddressspace.
*Under32bitPHPthis(safely)overflowsintonegativesints.
*
*@authorPaulAnnesley
*@packageFlexihash
*@licencehttp://www.opensource.org/licenses/mit-license.php
*/
classFlexihash_Crc32Hasher
implementsFlexihash_Hasher
{
/*(non-phpdoc)
*@seeFlexihash_Hasher::hash()
*/
publicfunctionhash($string)
{
returncrc32($string);
}
}
/**
*UsesCRC32tohashavalueintoa32bitbinarystringdataaddressspace.
*
*@authorPaulAnnesley
*@packageFlexihash
*@licencehttp://www.opensource.org/licenses/mit-license.php
*/
classFlexihash_Md5Hasher
implementsFlexihash_Hasher
{
/*(non-phpdoc)
*@seeFlexihash_Hasher::hash()
*/
publicfunctionhash($string)
{
returnsubstr(md5($string),0,8);//8hexits=32bit
//4bytesofbinarymd5datacouldalsobeused,but
//performanceseemstobethesame.
}
}
/**
*AnexceptionthrownbyFlexihash.
*
*@authorPaulAnnesley
*@packageFlexihash
*@licencehttp://www.opensource.org/licenses/mit-license.php
*/
classFlexihash_ExceptionextendsException
{
}
希望本文所述对大家PHP程序设计有所帮助。