仿照标准库做了个hashmap!不容易啊。
发布日期:2021-07-14 20:03:21 浏览次数:5 分类:技术文章

本文共 3811 字,大约阅读时间需要 12 分钟。

// ConsoleTest.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include 
#include
const int primes[] = {2009,3009,4009,5009,6009,7009,8009,16009};template
int hash(T t){return t.hashCode();}template
struct MyPair{ typedef KeyT TypeKey; typedef ValT TypeVal; KeyT key; ValT value;};template
struct BucketNode{ typedef Pair DataType; Pair PairValue; BucketNode* pNext;};template
struct Bucket{ typedef DataType Pair ; typedef BucketNode
NodeType; BucketNode
* pHead;};template
class HashMap{public: typedef typename Bucket::Pair MapPairType; typedef typename MapPairType::TypeKey KeyT; typedef typename MapPairType::TypeVal ValT; HashMap(); const typename MapPairType* GetValue(KeyT key); void insert(MapPairType data); void rehash(); unsigned int HashValue(unsigned int hashCode); float fHashFacil; int nContOfContent; int indexCapbility; Bucket** pContent;};template
const typename HashMap
::MapPairType* HashMap
::GetValue(KeyT key){ int indexOfFind = HashValue(hash(key)); Bucket::NodeType* pNode = pContent[indexOfFind]->pHead; while (pNode != NULL) { if (pNode->PairValue.key == key) { return &(pNode->PairValue); } else { pNode = pNode->pNext; } } return NULL;}template
void HashMap
::rehash(){ Bucket** oldContent = pContent; int oldIndexCapbility = indexCapbility; if (indexCapbility >= sizeof(primes)/sizeof(primes[0]) - 1) { return; } while ((int)(fHashFacil*primes[indexCapbility]) < nContOfContent) { if (indexCapbility >= sizeof(primes)/sizeof(primes[0]) - 1) { break; } indexCapbility ++; } // //Rehash the table. // //Reset the Count to zero. nContOfContent = 0; //Insert old data to new table; pContent = new Bucket* [primes[indexCapbility]]; memset(pContent, 0, primes[indexCapbility]*sizeof(Bucket*)); for (int i = 0; i
pHead; while (pNode) { insert(pNode->PairValue); Bucket::NodeType* oldNode = pNode; pNode = pNode->pNext; delete oldNode; } } } delete[] oldContent;}template
void HashMap
::insert(MapPairType data){ if ((int)(fHashFacil*primes[indexCapbility]) < nContOfContent) { //std::cout<<"The current conten is "<
<
pHead = new Bucket::NodeType; pBucket->pHead->PairValue = data; pBucket->pHead->pNext = NULL; pContent[hashVal] = pBucket; //delete pBucket; } else { Bucket::NodeType* pNode = pContent[hashVal]->pHead; while (pNode->pNext!= NULL) { pNode = pNode->pNext; } Bucket* pBucket = new Bucket; pNode->pNext = new Bucket::NodeType; pNode->pNext->pNext = NULL; pNode->pNext->PairValue = data; } nContOfContent ++;}template
HashMap
::HashMap(){ fHashFacil = 0.75; indexCapbility = 0; nContOfContent = 0; pContent = NULL; pContent = new Bucket* [primes[indexCapbility]]; memset(pContent, 0, primes[indexCapbility]*sizeof(Bucket*));}template
unsigned int HashMap
::HashValue(unsigned int hashCode){ return hashCode%(primes[indexCapbility]);}//下面是测试程序。//作为hashmap的(key,value)对中key必须定义==操作符和HashCode方法。class HashString{ friend bool operator== (const HashString& keyLeft, const HashString& keyRight);public: HashString(const std::string& strValue) { m_strValue = strValue; } HashString() { m_strValue = (""); } operator std::string() { return m_strValue; } int hashCode() { register unsigned int h; register unsigned char *p; for(h=0, p = (unsigned char *)m_strValue.data(); *p ; p++) h = 31 * h + *p; return h; } std::string m_strValue;};bool operator== (const HashString& keyLeft, const HashString& keyRight){ return keyLeft.m_strValue == keyRight.m_strValue;}int _tmain(int argc, _TCHAR* argv[]){ HashMap
>> mapHash; for(int i = 0; i< 1000; i++) { MyPair
pairValue1; std::string strValue("XiongBei"); char buffer[33]; _itoa_s(i,buffer,33,10); pairValue1.key = strValue.append(buffer); pairValue1.value = i; mapHash.insert(pairValue1); } //std::cout<<"The current conten is "<
<
 

转载地址:https://blog.csdn.net/daojin505/article/details/76812043 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:关于BeginPaint和WM_ERASEBKGND
下一篇:MFC多线程编程

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月18日 23时15分21秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

西门子stl语言编写教程_21天学通C++语言 视频教程 (第6六版) 编程入门基础 (共69讲)... 2019-04-21
ip设计包括什么_如何选择动漫设计培训学校?课程大纲包括什么专业? 2019-04-21
db2查询字段备注_MacOS上的数据库查询工具哪个好用? 2019-04-21
.net如何获取方法返回的类型_如何获取蜂群?如何养殖?老蜂农:3种方法获取,2种方法养殖... 2019-04-21
x光肺部分割数据集_分享一个二次元插画的区域分割数据集 2019-04-21
isset php 二维数组_2020最新PHP面试题(附带答案) 2019-04-21
cpri带宽不足的解决方法_自动门电磁锁(磁力锁)吸力不足或毫无吸力解决方法... 2019-04-21
菜鸟驿站是什么快递_又是菜鸟驿站!再获快递新业态许可证 2019-04-21
android attrs获取_Android自定义View,敢说都知道吗? 2019-04-21
rust办宏G什么意思_双频路由器是什么意思 2.4G和5G用哪个好 双频路由器使用攻略!... 2019-04-21
调音台docker教程_Docker Hello World | 菜鸟教程 2019-04-21
linux下c语言绘图库_使用c语言实现linux数据库的操作 2019-04-21
超微服务器电源短接启动图解_服务器电源怎么短接 2021-06-24
python直角三角形的两个直角边、求斜边_Python实现“已知三角形两个直角边,求斜边”... 2021-06-24
一加7t人脸识别_10月换新推荐:一加7T/荣耀20青春版领衔好手机 2021-06-24
python调用rest接口 源码_python 调用RESTFul接口 2021-06-24
angular货币过滤_删除AngularJS货币过滤器小数/分 2021-06-24
ccs断点不停止_锅炉MFT后,汽机不跳闸,处理。 2021-06-24
java代码游戏_用Java开发简单又好玩的——雷霆战机小游戏,几行代码就搞定 2021-06-24
linux mysql打开文件_在Linux命令行上直接运行MySQL文件 2021-06-24