架构师训练营第五周作业

class ConsistentHash{public:	ConsistentHash(int node_num, int virtual_node_num)		: server_nodes_{}, node_num_{node_num}, virtual_node_num_{virtual_node_num} {}
	~ConsistentHash() {		if (!server_nodes_.empty())			server_nodes_.clear();	}
	void Initialize();	size_t GetServerIndex(const char* key);
	void DeleteNode(const int index);	void AddNewNode(const int index);
private:	std::string getKeyStr(int node, int virtual_node);
	map<uint32_t,size_t> server_nodes_;	int node_num_;	int virtual_node_num_;};

#include <map>#include <string.h>#include <sstream>#include "consistentHash.h"using namespace std;
uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed = 17) {	static const uint32_t c1 = 0xcc9e2d51;	static const uint32_t c2 = 0x1b873593;	static const uint32_t r1 = 15;	static const uint32_t r2 = 13;	static const uint32_t m = 5;	static const uint32_t n = 0xe6546b64; 	uint32_t hash = seed; 	const int nblocks = len / 4;	const uint32_t *blocks = (const uint32_t *) key;	int i;	for (i = 0; i < nblocks; i++) 	{		uint32_t k = blocks[i];		k *= c1;		k = (k << r1) | (k >> (32 - r1));		k *= c2; 		hash ^= k;		hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;	} 	const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);	uint32_t k1 = 0; 	switch (len & 3) 	{	case 3:		k1 ^= tail[2] << 16;	case 2:		k1 ^= tail[1] << 8;	case 1:		k1 ^= tail[0]; 		k1 *= c1;		k1 = (k1 << r1) | (k1 >> (32 - r1));		k1 *= c2;		hash ^= k1;	} 	hash ^= len;	hash ^= (hash >> 16);	hash *= 0x85ebca6b;	hash ^= (hash >> 13);	hash *= 0xc2b2ae35;	hash ^= (hash >> 16); 	return hash;}
std::string ConsistentHash::getKeyStr(int node, int virtual_node) {	stringstream node_key;	node_key << "Server-" << node << "-Node-" << virtual_node;	return node_key.str();}
void ConsistentHash::Initialize(){	for (int i = 0; i < node_num_; ++i) {		for (int j = 0; j < virtual_node_num_; ++j) {			std::string key = getKeyStr(i, j);			uint32_t partition = murmur3_32(key.c_str(), key.length());			server_nodes_.insert(pair<uint32_t, size_t>(partition, i));		}	}}

size_t ConsistentHash::GetServerIndex(const char* key){	uint32_t partition = murmur3_32(key, strlen(key));	map<uint32_t, size_t>::iterator it = server_nodes_.lower_bound(partition);//沿环的顺时针找到一个大于等于key的虚拟节点
	if (it == server_nodes_.end()) {		return server_nodes_.begin()->second;	}	return it->second;}

void ConsistentHash::DeleteNode(const int index){	for (int j = 0; j < virtual_node_num_; ++j) {		std::string key = getKeyStr(index, j);		uint32_t partition = murmur3_32(key.c_str(), key.length());		map<uint32_t,size_t>::iterator it = server_nodes_.find(partition);		if (it != server_nodes_.end()) {			server_nodes_.erase(it);		}	}}
void ConsistentHash::AddNewNode(const int index){	for (int j = 0; j < virtual_node_num_; ++j) {		std::string key = getKeyStr(index, j);		uint32_t partition = murmur3_32(key.c_str(), key.length());		server_nodes_.insert(pair<uint32_t, size_t>(partition, index));	}}

int main(int argc, char const *argv[]){	int sample_count = 1000000;		int node_num = 10;	int virtual_num = 150;
	ConsistentHash* consistent_hash = new ConsistentHash(node_num, virtual_num);	consistent_hash->Initialize();	printf("consistent hash initialize success, node_num=%d, virtual_num=%d\n", node_num, virtual_num);		vector<int> result(node_num,0);//节点存放数据数目统计		srand(time(NULL));	for(int i=0; i<sample_count; ++i)	{				int value = i;		stringstream ss;		ss<<value;		const char* key = ss.str().c_str();		size_t index = consistent_hash->GetServerIndex(key);		result[index]++;	}
	int square_sum = 0;	int sum = 0;	for (int i = 0; i < node_num; i++) {		cout << "result[" << i << "]:" << result[i] << endl;		sum += result[i];	}	float average = sum / node_num;	for (int i = 0; i < node_num; i++) {		square_sum += (result[i] - average) * (result[i] - average);	}	square_sum = square_sum / node_num;	cout << "standard deviation:" << sqrt(square_sum) << endl;
	return 0;}