电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 基于一致性hash算法 C++语言的实现详解（2） [打印本页]

作者: yuyang911220 时间: 2017-4-23 17:05 标题: 基于一致性hash算法 C++语言的实现详解（2）

CMD5HashFun 类继承CHashFun接口，实现获取hash值的getHashVal函数：
复制代码代码如下:
/*用MD5算法计算结点的hash值，继承CHashFun父类*/
class CMD5HashFun : public CHashFun
{
public:
virtual long getHashVal (const char * );
};
long CMD5HashFun::getHashVal(const char * instr)
{
int i;
long hash = 0;
unsigned char digest[16];
/*调用MD5相关函数，生成instr的MD5码，存入digest*/
md5_state_t md5state;
md5_init(&md5state);
md5_append(&md5state, (const unsigned char *)instr, strlen(instr));
md5_finish(&md5state, digest);
/* 每四个字节构成一个32位整数，
将四个32位整数相加得到instr的hash值（可能溢出） */
for(i = 0; i < 4; i++)
{
      hash += ((long)(digest[i*4 + 3]&0xFF) << 24)
         | ((long)(digest[i*4 + 2]&0xFF) << 16)
         | ((long)(digest[i*4 + 1]&0xFF) <<  8)
         | ((long)(digest[i*4 + 0]&0xFF));
}
return hash;
}
3、扩展红黑树结构中的查找函数，用于查找红黑树中大于key值中最小的结点。
复制代码代码如下:
util_rbtree_node_t* util_rbtree_lookup(util_rbtree_t *rbtree, long key)
{
if((rbtree != NULL) && !util_rbtree_isempty(rbtree))
{
      util_rbtree_node_t *node = NULL;
      util_rbtree_node_t *temp = rbtree->root;
      util_rbtree_node_t *null = _NULL(rbtree);
      while(temp != null)
      {
         if(key <= temp->key)
         {
            node = temp; /* update node */
            temp = temp->left;
         }
         else if(key > temp->key)
         {
            temp = temp->right;
         }
      }
      /* if node==NULL return the minimum node */
      return ((node != NULL) ? node : util_rbtree_min(rbtree));
}
return NULL;
}
4、创建一致性hash类。使其具有插入、删除、查找实体结点的功能。
具体算法和操作过程已经在代码注释中说明。
复制代码代码如下:
class CConHash
{
public:
/*构造函数*/
CConHash(CHashFun * pFunc);
/*设置hash函数*/
void setFunc(CHashFun * pFunc);
/*增加实体结点 , 0代表成功 , -1代表失败*/
int addNode_s(CNode_s * pNode);
/*删除实体结点 , 0代表成功 , -1代表失败*/
int delNode_s(CNode_s * pNode);
/*查找实体结点*/
CNode_s * lookupNode_s(const char * object);
/*获取一致性hash结构的所有虚拟结点数量*/
int getVNodes();
private:
/*Hash函数*/
CHashFun * func;
/*虚拟结点总个数*/
int vNodes;
/*存储虚拟结点的红黑树*/
util_rbtree_t * vnode_tree;
};
/*辅助函数，虚拟结点转化为红黑树结点*/
util_rbtree_node_t * vNode2RBNode(CVirtualNode_s * vnode);

CConHash::CConHash(CHashFun * pFunc)
{
/*设置hash函数*/
assert(pFunc!=NULL);
this->func = pFunc;
this->vNodes = 0;
/*初始化红黑树*/
vnode_tree = new util_rbtree_s();
util_rbtree_init(vnode_tree);
}
int CConHash::addNode_s(CNode_s * pNode)
{
if(pNode==NULL) return -1;
int vCount = pNode->getVNodeCount();
if(vCount<=0) return -1;
CVirtualNode_s * virtualNode ;
util_rbtree_node_t * rbNode;
char str [100];
char num[10];
strcpy(str,pNode->getIden());
long hash = 0;
/*生成虚拟结点并插入到红黑树中*/
for(int i=0;i<vCount;i++)
{
      virtualNode = new CVirtualNode_s(pNode);
      /*采用str+“i”的方法产生不同的iden串，用于后面的hash值计算*/
      itoa(i,num,10);
      strcat(str,num);
      hash = func->getHashVal(str);
      virtualNode->setHash(hash);
      if(!util_rbtree_search(vnode_tree,hash))
      {
         /*生成红黑树结点*/
         rbNode = vNode2RBNode(virtualNode);
         if(rbNode!=NULL)
         {
            /*将该结点插入到红黑树中*/
            util_rbtree_insert(vnode_tree,rbNode);
            this->vNodes++;
         }
      }
}
return 0;
}
int CConHash::delNode_s(CNode_s * pNode)
{
if(pNode==NULL) return -1;
util_rbtree_node_t * rbNode;
char str [100];
char num [10];
strcpy(str,pNode->getIden());
int vCount = pNode->getVNodeCount();
long hash = 0;
CVirtualNode_s * node = NULL;
/*将该实体结点产生的所有虚拟结点进行删除*/
for(int i=0;i<vCount;i++)
{
      itoa(i,num,10);
      strcat(str,num);/*采用该方法产生不同的iden串*/
      hash = func->getHashVal(str);
      rbNode = util_rbtree_search(vnode_tree,hash);
      if(rbNode!=NULL)
      {
         node = (CVirtualNode_s *) rbNode->data;
         if(node->getNode_s()==pNode && node->getHash()==hash)
         {
            this->vNodes--;
            /*将该结点从红黑树中删除*/
            util_rbtree_delete(vnode_tree,rbNode);
            delete rbNode;
            delete node;
         }
      }
}
return 0;
}
CNode_s * CConHash::lookupNode_s(const char * object)
{
if(object==NULL||this->vNodes==0) return NULL;
util_rbtree_node_t * rbNode;
int key = this->func->getHashVal(object);
/*在红黑树中查找key值比key大的最小的结点*/
rbNode = util_rbtree_lookup(vnode_tree,key);
if(rbNode!=NULL)
{
      return ((CVirtualNode_s *) rbNode->data)->getNode_s();
}
return NULL;
}
int CConHash::getVNodes()
{
return this->vNodes;
}

util_rbtree_node_t * vNode2RBNode(CVirtualNode_s * vnode)
{
if(vnode==NULL) return NULL;
util_rbtree_node_t *rbNode = new util_rbtree_node_t();
rbNode->key = vnode->getHash();
rbNode->data = vnode;
return rbNode;
}

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)