<?php
/**
 *@author:xiaojiang 20140222
 * 一致性哈希php 实现
 */

class MyHash{
    
    //虚拟节点数
    private $_virtualCounts = 2; 
    //虚拟节点集合
    private $_circleItems = array();
    //实际节点
    private $_items = array();
    //实际节点数
    private $_itemsCount = 0;
    //是否需要排序
    private $_itemRelKey = array();
    private $needSort = false;


    private $algo;

    public function __construct( hash_algo $algo = null ){
        if( !$algo ){
            $this->algo = new algo_md5();
        }
    }

    public function addItem( $_item ){
        
        if( isset( $this->_items[$_item]) ){
            throw("item exists");
        }
        $this->_items[$_item] = array();
        for( $i = 0; $i < $this->_virtualCounts; $i++ ){
             $_virturalKey = $this->algo->run( $_item.$i );
             $this->_circleItems[$_virturalKey] = $_item;
             $this->_itemRelKey[$_item][] = $_virturalKey; 
        }
        $this->needSort = true;
        $this->_itemsCount++;
    }

    public function removeItem( $_item ){
    
        if( !isset( $this->_items[$_item] ) ){
            throw(‘item is not exists‘);
        }
        foreach( $this->_itemRelKey[$_item] as $key){
            unset( $this->_circleItems[$key] );
        }
        unset($this->_items[$_item]);
        $this->_itemsCount--;
    }


    public function getKey( $str ){

        if($this->needSort){
            $this->sortItems();
        }    
        
        $_sk = $this->algo->run( $str );
        echo $_sk;
        foreach( $this->_circleItems as $key => $_item){
            
            if( $key > $_sk ){
                return $_item;
            }
        }
        $ret = array_values(array_slice($this->_circleItems , 0 ,1));
        return $ret[0];

    }

    private function sortItems(){
        
         ksort( $this->_circleItems ,SORT_STRING );
         $this->needSort = false;
    }

    public function _t(){
        print_r($this->_circleItems);
    }
}
Interface  hash_algo{
    function run();
}
class algo_md5{
    function run( $_str ){
        return MD5( $_str );
    }
}
$_tstr = "B8aaaaa";
$thash = new MyHash();
$thash->addItem("10.100.200.3");


//$a = $thash->getKey($_tstr);
//$thash->_t();

$thash->removeItem("10.100.200.4");
$thash->_t();


?>