Maison > Article > développement back-end > Explication détaillée de l'algorithme de consensus HASH
Cette fois, je vais vous apporter une explication détaillée de l'algorithme de cohérence HASH. Quelles sont les précautions pour l'explication détaillée de l'algorithme de cohérence HASH. Ce qui suit est un cas pratique, jetons un coup d'œil.
L'exemple de cet article décrit l'algorithme HASH cohérent implémenté en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :
<?php // +---------------------------------------------------------------------- // | Perfect Is Shit // +---------------------------------------------------------------------- // | PHP实现:一致性HASH算法 // +---------------------------------------------------------------------- // | Author: alexander <gt199899@gmail.com> // +---------------------------------------------------------------------- // | Datetime: 2017-01-11 16:01:36 // +---------------------------------------------------------------------- // | Copyright: Perfect Is Shit // +---------------------------------------------------------------------- class ConsistentHashing { // 圆环 // hash -> 节点 private $_ring = array(); // 所有节点 // 节点 -> hash public $nodes = array(); // 每个节点的虚拟节点 public $virtual = 64; /** * 构造 * @param array $nodes 初始化的节点列表 */ public function construct($nodes = array()) { if (!empty($nodes)) { foreach ($nodes as $value) { $this->addNode($value); } } } /** * 获取圆环内容 * @return array $this->_ring */ public function getRing() { return $this->_ring; } /** * time33 函数 * @param string $str * @return 32位正整数 * @author 大神们 */ public function time33($str) { // hash(i) = hash(i-1) * 33 + str[i] // $hash = 5381; ## 将hash设置为0,竟然比设置为5381分布效果更好!!! $hash = 0; $s = md5($str); //相比其它版本,进行了md5加密 $seed = 5; $len = 32;//加密后长度32 for ($i = 0; $i < $len; $i++) { // (hash << 5) + hash 相当于 hash * 33 //$hash = sprintf("%u", $hash * 33) + ord($s{$i}); //$hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF; $hash = ($hash << $seed) + $hash + ord($s{$i}); } return $hash & 0x7FFFFFFF; } /** * 增加节点 * @param string $node 节点名称 * @return object $this */ public function addNode($node) { if (in_array($node, array_keys($this->nodes))) { return; } for ($i = 1; $i <= $this->virtual; $i++) { $key = $this->time33($node . '-' . $i); $this->_ring[$key] = $node; $this->nodes[$node][] = $key; } ksort($this->_ring, SORT_NUMERIC); return $this; } /** * 获取字符串的HASH在圆环上面映射到的节点 * @param string $key * @return string $node */ public function getNode($key) { $node = current($this->_ring); $hash = $this->time33($key); foreach ($this->_ring as $key => $value) { if ($hash <= $key) { $node = $value; break; } } return $node; } /** * 获取映射到特定节点的KEY * 此方法需手动调用,非特殊情况不建议程序中使用此方法 * @param string $node * @param string $keyPre * @return mixed */ public function getKey($node, $keyPre = ""){ if(!in_array($node, array_keys($this->nodes))){ return false; } $result = false; for($i=1;$i<=10000;$i++){ $key = $keyPre . md5(rand(1000, 9999)); if($this->getNode($key) == $node){ $result = true; break; } } return $result ? $key : false; } } $ch_obj = new ConsistentHashing(); $ch_obj->addNode('node_1'); $ch_obj->addNode('node_2'); $ch_obj->addNode('node_3'); $ch_obj->addNode('node_4'); $ch_obj->addNode('node_5'); $ch_obj->addNode('node_6'); // +---------------------------------------------------------------------- // | 查看key映射到的节点 // +---------------------------------------------------------------------- $key1 = "asofiwjamfdalksjfkasasdflasfja"; $key2 = "jaksldfjlasfjsdjfioafaslkjflsadkjfl"; $key3 = "asjldflkjasfsdjflkajkldsjfksajdlflajs"; $key4 = "iowanfasijfmasdnfoas"; $key5 = "pqkisndfhoalnfiewlkl"; $key6 = "qjklasjdifoajfalsjflsa"; echo sprintf("%-50s 映射到节点 %s\n", $key1, $ch_obj->getNode($key1)); echo sprintf("%-50s 映射到节点 %s\n", $key2, $ch_obj->getNode($key2)); echo sprintf("%-50s 映射到节点 %s\n", $key3, $ch_obj->getNode($key3)); echo sprintf("%-50s 映射到节点 %s\n", $key4, $ch_obj->getNode($key4)); echo sprintf("%-50s 映射到节点 %s\n", $key5, $ch_obj->getNode($key5)); echo sprintf("%-50s 映射到节点 %s\n", $key6, $ch_obj->getNode($key6)); // +---------------------------------------------------------------------- // | 查看圆环和节点信息 // +---------------------------------------------------------------------- // var_dump($ch_obj->getRing()); // var_dump($ch_obj->nodes); // +---------------------------------------------------------------------- // | 获取特定节点的KEY // +---------------------------------------------------------------------- // $key1 = $ch_obj->getKey('node_1', 'pre_'); // var_dump($key1); // +---------------------------------------------------------------------- // | 测试分布 // +---------------------------------------------------------------------- // $keys = array(); // $rings = array(); // for ($i = 1; $i <= 60000; $i++) { // $key = sha1(rand(1000000,9999999)); // $node = $ch_obj->getNode($key); // $rings[$node] = isset($rings[$node]) ? ++$rings[$node] : 1; // } // var_dump($rings);
Résultats d'exécution :
asofiwjamfdalksjfkasasdflasfja 映射到节点 node_1 jaksldfjlasfjsdjfioafaslkjflsadkjfl 映射到节点 node_2 asjldflkjasfsdjflkajkldsjfksajdlflajs 映射到节点 node_1 iowanfasijfmasdnfoas 映射到节点 node_2 pqkisndfhoalnfiewlkl 映射到节点 node_3 qjklasjdifoajfalsjflsa 映射到节点 node_5
Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention au site Web chinois php Autres articles connexes !
Lecture recommandée :
Explication détaillée de l'utilisation des fonctions de rappel PHP et des fonctions anonymes
Accès aux autorisations du service d'annuaire de phpstudy2018
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!