练习 05-1

用户头像
闷骚程序员
关注
发布于: 2020 年 07 月 05 日





1. 哈希值计算对象:

// 哈希值计算接口
#include <stdint.h>
#include <string>
class IHashCode
{
public:
IHashCode()
{
};
virtual ~IHashCode()
{
};
virtual uint32_t hashCode(const std::string &str) = 0;
private:
};
//.h
// 使用stl哈希函数计算哈希值。
#include "IHashCode.h"
class STLHashCode : public IHashCode
{
public:
STLHashCode();
virtual ~STLHashCode();
virtual uint32_t hashCode(const std::string &str);
private:
};
// .cpp
#include <memory>
#include "STLHashCode.h"
STLHashCode::STLHashCode()
{
}
STLHashCode::~STLHashCode()
{
}
uint32_t STLHashCode::hashCode(const std::string &str)
{
std::hash<std::string> uint_hash;
return uint_hash(str);
}



2. 哈希环对象

// 接口
#include <string>
class ICacheServer;
class IHashCircle
{
public:
IHashCircle()
{
};
virtual ~IHashCircle()
{
};
virtual void addServer(ICacheServer* cacheServer) = 0;
virtual ICacheServer* getServer(const std::string &key) = 0;
private:
};
// 实现
// .h
#include <stdint.h>
#include <string>
#include <map>
#include <iostream>
#include "IHashCircle.h"
#include "ICacheServer.h"
class IHashCode;
class ConsistHashCircle : IHashCircle
{
public:
ConsistHashCircle(IHashCode* hashCode);
virtual ~ConsistHashCircle();
virtual void addServer(ICacheServer* cacheServer);
virtual ICacheServer* getServer(const std::string &key);
void show()
{
for (auto& e : hashCircle) {
std::cout << "hash code: " << e.first << " servName: " << e.second->serverName() << std::endl;
}
}
private:
std::map<uint32_t, ICacheServer*> hashCircle;
int virNodeCount = 150;
IHashCode* hashCode = NULL;
};
// .cpp
#include "ConsistHashCircle.h"
#include "ICacheServer.h"
#include "IHashCode.h"
#include <string>
ConsistHashCircle::ConsistHashCircle(IHashCode* hashCode)
: hashCode(hashCode)
{
}
ConsistHashCircle::~ConsistHashCircle()
{
}
void ConsistHashCircle::addServer(ICacheServer* cacheServer)
{
std::string serverName = cacheServer->serverName();
// 计算节点的哈希值,然后在算出虚拟节点。
hashCircle[hashCode->hashCode(serverName)] = cacheServer;
for (int i = 0; i < virNodeCount; ++i)
{
hashCircle[hashCode->hashCode(serverName + std::to_string(i))] = cacheServer;
}
}
ICacheServer* ConsistHashCircle::getServer(const std::string &key)
{
if (hashCircle.empty())
{
return NULL;
}
// TODO: 计算key的hash值,然后顺时针找到离这个hash最近的节点。
auto iter = hashCircle.upper_bound(hashCode->hashCode(key));
if (iter != hashCircle.end())
{
return iter->second;
}
// 因为是hash环,顺时针就是 0 1 2 3 4 ... 2的32次方,即只要找更大值就可以了,但是如果没找到,就获取第一个即可。
return hashCircle.begin()->second;
}



3. 缓存服务器

// 接口
#include <cstdint>
#include <string>
class ICacheServer
{
public:
ICacheServer()
{
};
virtual ~ICacheServer()
{
};
virtual bool set(const std::string &key, const std::string &val) = 0;
virtual bool get(const std::string &key, std::string &val) = 0;
virtual std::string serverName() = 0;
private:
};
// 实现:本地内存存储。
// .h
#include "IHashCode.h"
#include "ICacheServer.h"
#include <string>
#include <map>
class LocalMemCacheServer : public ICacheServer
{
public:
LocalMemCacheServer(std::string servName);
virtual ~LocalMemCacheServer();
virtual bool set(const std::string &key, const std::string &val);
virtual bool get(const std::string &key, std::string &val);
virtual std::string serverName();
size_t size()const
{
return cache.size();
}
private:
std::string servName;
std::map<std::string, std::string> cache;
};
// .cpp
#include "LocalMemCacheServer.h"
LocalMemCacheServer::LocalMemCacheServer(std::string serverName)
: servName(serverName)
{
}
LocalMemCacheServer::~LocalMemCacheServer()
{
}
bool LocalMemCacheServer::set(const std::string &key, const std::string &val)
{
cache[key] = val;
return true;
}
bool LocalMemCacheServer::get(const std::string &key, std::string &val)
{
auto iter = cache.find(key);
if (iter == cache.end())
{
return false;
}
val = iter->second;
return true;
}
std::string LocalMemCacheServer::serverName()
{
return this->servName;
}



4. 使用

int main(int argc, char** argv)
{
// 初始化对象
std::vector<ICacheServer*> cacheServers;
STLHashCode hashCode;
ConsistHashCircle hashCircle(&hashCode);
for (auto i = 0; i < 10; ++i)
{
ICacheServer* cache = new LocalMemCacheServer(std::to_string(i) + "safadfasdfafsdfasdfsadfs");
hashCircle.addServer(cache);
cacheServers.push_back(cache);
}
// 初始化数据
for (auto i = 0; i < 1000000; ++i)
{
std::string key = std::to_string(i);
std::string val = std::to_string(i);
auto cacheServer = hashCircle.getServer(key);
if (!cacheServer)
{
std::cout << "cacheServer is null" << std::endl;
continue;
}
cacheServer->set(key, val);
}
// 展示存储情况,看数据是否分布均匀
for (auto &e : cacheServers)
{
LocalMemCacheServer* lmcache = (LocalMemCacheServer*) e;
std::cout << "name: " << lmcache->serverName() << " cache size: " << lmcache->size() << std::endl;
}
return 0;



5. 输出



name: 1safadfasdfafsdfasdfsadfs cache size: 101679

name: 2safadfasdfafsdfasdfsadfs cache size: 109582

name: 3safadfasdfafsdfasdfsadfs cache size: 99704

name: 4safadfasdfafsdfasdfsadfs cache size: 96678

name: 5safadfasdfafsdfasdfsadfs cache size: 102025

name: 6safadfasdfafsdfasdfsadfs cache size: 110198

name: 7safadfasdfafsdfasdfsadfs cache size: 92797

name: 8safadfasdfafsdfasdfsadfs cache size: 100276

name: 9safadfasdfafsdfasdfsadfs cache size: 97018



6. 输出结果标准差

标准差: 6114.33113



用户头像

闷骚程序员

关注

还未添加个人签名 2018.11.15 加入

还未添加个人简介

评论

发布
暂无评论
练习 05-1