1 标准库的映射字典

C++ STL的映射字典使用红黑树做为底层的数据结构，红黑树的访问的时间复杂度为：O(logn)。哈希的时间复杂度虽然是O(1)，但其是无序的，而红黑树却是有序的。

#include <iostream> #include <map> // 红黑树映射，映射也叫字典，不是哈希映射 #include <string> using namespace std; int main() { map<string,int> m; m["bill"] = 98; m["Tom"] = 67; m["Mary"] = 100; // …… cout<< m["Tom"] <<endl; system("pause"); return 0; }

2 自定义线性映射

线性映射自然不能随机访问，需要线性查找，其时间复杂度为O(n)，此实例只是为了对比后述的哈希映射。

#include <iostream> #include <vector> #include <string> using namespace std; template<typename Key, typename Value> class LinearMap { public: LinearMap(int size=101) : arr(size) { currentSize = 0; } void Put(const Key& k, const Value& v) { arr[currentSize] = DataEntry(k,v); ++currentSize; } Value Get(const Key& k) // 线性查找和访问 { for(size_t i=0; i<currentSize; ++i) { if(arr[i].key == k) return arr[i].value; } return Value(); } private: struct DataEntry{ Key key; Value value; DataEntry(const Key& k = Key(), const Value& v = Value()): key(k),value(v){} }; std::vector<DataEntry> arr; int currentSize; }; int main() { LinearMap<string, int> lm; lm.Put("Bill",99); lm.Put("Tom",88); lm.Put("Mary",77); cout<<lm.Get("Tom")<<endl; system("pause"); return 0; }

3 自定义哈希映射（没有处理碰撞冲突）

使用Hash的查询算法分为两步：

① 用Hash函数将被查找的键转化为数组的一个索引。
理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。
② 处理碰撞冲突的过程。

以下小实例只是演示了如何将键转化为一个数组的下标索引，并没有考虑处理碰撞冲突的情况：

#include <iostream> #include <vector> #include <string> using namespace std; template<typename Key, typename Value> class HashMap // 将字符串通过哈希函数映射为数据下标 { public: HashMap(int size=101) : arr(size) { currentSize = 0; } void Put(const Key& k, const Value& v) { int pos = myhash(k); arr[pos] = DataEntry(k,v); ++currentSize; } Value Get(const Key& k) { int pos = myhash(k); if(arr[pos].key == k) return arr[pos].value; else return Value(); } unsigned hash(const Key& k) const { unsigned int hashVal = 0; //const char* keyp = reinterpret_cast<const char*>(&k); for(size_t i=0; i<sizeof(k); i++) hashVal = 37 * hashVal + k[i]; return hashVal; } int myhash(const Key& k) const { unsigned hashVal = hash(k); hashVal %= arr.size(); return hashVal; } private: struct DataEntry{ Key key; Value value; DataEntry(const Key& k = Key(), const Value& v = Value()): key(k),value(v){} }; vector<DataEntry> arr; int currentSize; }; int main() { HashMap<string, int> hm; cout<<hm.hash("wwu")<<endl; cout<<hm.myhash("wwu")<<endl; hm.Put("Bill",99); hm.Put("Tom",88); hm.Put("wwu",66); hm.Put("Mary",77); cout<<hm.Get("wwu")<<endl; system("pause"); return 0; }

哈希函数实现方法：

(1) 余数法：先估计整个哈希表中的表项目数目大小。然后用这个估计值作为除数去除每个原始值，得到商和余数。用余数作为哈希值。因为这种方法产生冲突的可能性相当大，因此任何搜索算法都应该能够判断冲突是否发生并提出取代算法。

(2) 折叠法：这种方法是针对原始值为数字时使用，将原始值分为若干部分，然后将各部分叠加，得到的最后四个数字(或者取其他位数的数字都可以)来作为哈希值。

(3) 基数转换法：当原始值是数字时，可以将原始值的数制基数转为一个不同的数字。例如，可以将十进制的原始值转为十六进制的哈希值。为了使哈希值的长度相同，可以省略高位数字。

(4) 数据重排法：这种方法只是简单的将原始值中的数据打乱排序。比如可以将第三位到第六位的数字逆序排列，然后利用重排后的数字作为哈希值。

哈希函数并不通用，比如在数据库中用能够获得很好效果的哈希函数，用在密码学或错误校验方面就未必可行。在密码学领域有几个著名的哈希函数。这些函数包括MD2、MD4以及MD5，利用散列法将数字签名转换成的哈希值称为信息摘要(message-digest)，另外还有安全散列算法(SHA)，这是一种标准算法，能够生成更大的(60bit)的信息摘要，有点儿类似于MD4算法。

常见的两种解决碰撞的方法：

① 拉链法（separate chaining）

一个Hash函数能够将键转换为数组索引，Hash算法的第二步是碰撞处理，也就是处理两个或多个键的Hash值相同的情况。一种直接的办法是将大小为 M 的数组中的每个素指向一条链表，链表中的每个结点都存储了Hash值为该素的索引的键值对。这种方法被称为“拉链法”，因此发生冲突的素都被存储在一个链表中。

这种方法的基本思想就是选择足够大的M，使得所有链表都尽可能短以保证高效的查找。查找分两步：首先根据Hash值找到对应的链表，然后沿着链表顺序查找对应的键。当你能够预知所需要的符号表的大小时，该方法能够得到不错的性能。一种更可靠的方案是动态调整链表数组的大小，这样无论在符号表中有多少键值对都能保证链表较短。

② 线性探测法（linear probing）

实现哈希表的另一种方式就是用大小为 M 的数组保存 N 个键值对，其中 M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表。

线性探测法（“开放地址”哈希表的一种实现方式）：
开放地址哈希表中最简单的方法叫做“线性探测”法：当碰撞发生时（当一个键的Hash值已经被另一个不同的键占用），我们直接检测哈希表中的下一个位置（将索引值加 1）。这样的线性探测可能会产生三种结果：
a）命中，该位置的键和被查找的键相同；
b）未命中，键为空（该位置没有键）
c）继续查找，该位置的键和被查找的键不同。我们用Hash函数找到键在数组中的索引，检查其中的键和被查找的键是否相同。如果不同则继续查找（将索引增大，到达数组结尾时折回数组的开头），直到找到该键或者遇到一个空素。
我们习惯将检查一个数组位置是否含有被查找的键的操作称作探测。在这里它可以等价于我们一直使用的比较，不过有些探测实际上是在测试键是否为空。
“开放地址”哈希表的核心思想是与其将内存用于链表，不如将它们作为哈希表的空素。这些空素可以作为查找结束的标志。

4 自定义哈希映射（有处理碰撞冲突）

// 1.用数组形式建立哈希表 // 2.使用链式方法解决冲突 // 3.平方取中法通过字符串Hash函数求hash值（还有很多种其他的hash函数） #include <iostream> #include <string> #include <cstring> #include <stdlib.h> #include <time.h> using namespace std; typedef unsigned long(*GetKeyValue)(const string& ); //该类用来处理冲突的节点 template<class TypeA,class TypeB> struct HashNode{ TypeA key; TypeB value; HashNode *next; HashNode(TypeA key,TypeB value){ HashNode::key = key; HashNode::value = value; next = NULL; } HashNode& operator=(const HashNode& node){ key = node.key; value = node.key; next = node.next; return *this; } }; //该类是HashMap用来存放hash表 template<class TypeA,class TypeB,class FuncType> class HashMap{ HashNode<TypeA,TypeB> table; unsigned long capacity; FuncType GetKeyValue; const TypeB TYPEB_NULL; public: HashMap(FuncType func,const TypeB& _null); ~HashMap(); TypeB Put(const HashNode<TypeA,TypeB>& hashNode); //插入一个HashNode 返回该节点的value值 TypeB GetValue(const TypeA& key); // 查找某个hashNode 其key为“key”的素 TypeB Delete(const TypeA& key); // 删除某个hashNode 其key为“key”的素 }; template<class TypeA,class TypeB,class FuncType> //在调用的时候指定函数 HashMap<TypeA,TypeB,FuncType>::HashMap(FuncType func,const TypeB& _null) : TYPEB_NULL(_null){ capacity = ; GetKeyValue = func; table = new HashNode<TypeA,TypeB>*[capacity]; for(unsigned i = 0;i < capacity;i++) table[i] = NULL; } template<class TypeA,class TypeB,class FuncType> HashMap<TypeA,TypeB,FuncType>::~HashMap(){ for(unsigned i = 0;i < capacity;i++) { HashNode<TypeA,TypeB> *currentNode = table[i]; while(currentNode){ HashNode<TypeA,TypeB> *temp = currentNode; currentNode = currentNode->next; delete temp; } } delete table; } //新增节点操作，用鏈式法解決衝突 template<class TypeA,class TypeB,class FuncType> TypeB HashMap<TypeA,TypeB,FuncType>::Put(const HashNode<TypeA,TypeB>& hashNode){ HashNode<TypeA,TypeB> *newNode = NULL; unsigned long index = GetKeyValue(hashNode.key); if(table[index] == NULL){ table[index] = new HashNode<TypeA,TypeB>(hashNode.key,hashNode.value); newNode = table[index]; } else{ newNode = table[index]; while(newNode->next){ newNode = newNode->next; } newNode->next = new HashNode<TypeA,TypeB>(hashNode.key,hashNode.value); newNode = newNode->next; } return newNode->value; } //由键值获得value template<class TypeA,class TypeB,class FuncType> TypeB HashMap<TypeA,TypeB,FuncType>::GetValue(const TypeA& key){ unsigned long index = GetKeyValue(key); if(table[index] == NULL) return TYPEB_NULL; else{ HashNode<TypeA,TypeB> *currentNode = table[index]; while(currentNode){ if(currentNode->key == key) return currentNode->value; currentNode = currentNode->next; } } return TYPEB_NULL; } //由键值查找后，删除该节点，返回该删除的节点的value template<class TypeA,class TypeB,class FuncType> TypeB HashMap<TypeA,TypeB,FuncType>::Delete(const TypeA& key){ TypeB deletedNodeValue = TYPEB_NULL; unsigned long index = GetKeyValue(key); if(table[index] == NULL) return deletedNodeValue; else{ HashNode<TypeA,TypeB> *currentNode = table[index]; if(currentNode->key == key){ table[index] = currentNode->next; deletedNodeValue = currentNode->value; delete currentNode; return deletedNodeValue; } while(currentNode){ if(currentNode->next->key == key){ HashNode<TypeA,TypeB> *temp = currentNode->next; currentNode->next = currentNode->next->next; deletedNodeValue = temp->value; delete temp; return deletedNodeValue;; } currentNode = currentNode->next; } } return deletedNodeValue; } //平方取中法 //实现，取字符串中间3个字母，不足3个用0补足 unsigned long GetKeyValue_1(const string& key){ unsigned long keyValue = 0; int strSize = key.size(); string tempStr(key); for(int i = strSize;i < 3;i++) tempStr = "0" + tempStr; //如果大于3就取中间3位 if(strSize >= 3){ tempStr[0] = key[strSize / 2 - 1]; tempStr[1] = key[strSize / 2]; tempStr[2] = key[strSize / 2 + 1]; } tempStr = tempStr.substr(0,3); unsigned long num = 10000 * (unsigned long)(48); num += 100 * (unsigned long)(tempStr[1]); num += (unsigned long)(tempStr[2]); num *= num; char *numStr = new char[15]; numStr = itoa(num,numStr,10) ; int strLen = strlen(numStr); tempStr = "000000"; for(i = -2;i < 4;i++) tempStr[2 + i] = numStr[strLen / 2 + i]; keyValue = atoi(tempStr.c_str()); delete []numStr; return keyValue; } int main(){ clock_t start = clock(); //传入一个求哈希散列值的方法GetKeyValue_1 HashMap<string,string,GetKeyValue> hashMap(GetKeyValue_1,"NULL"); for(int i = 0;i < ;i++) { char *ckey = new char[20]; char *cvalue = new char[20]; ckey = itoa(i,ckey,10); cvalue = itoa(i,cvalue,10); string key(ckey); string value(cvalue); if(i == 67){ key = "67"; value = "hello hash No.67"; } HashNode<string,string> node1(key,value); //插入该节点 hashMap.Put(node1); // cout << "index: " <<GetKeyValue_1(key) << " nodeValue: " // << hashMap.Put(node1) << endl; } clock_t end = clock(); cout << "Test Result: \n"; //调用了time.h文件的CLOCKS_PER_SEC，表示每过千分之一秒，clock()函数返回值加1 cout << "插入条数据耗时： " << double(end - start) / CLOCKS_PER_SEC << " 秒" << endl; cout << "hashMap.GetValue(\"67\"): " << hashMap.GetValue("67") << endl; cout << "hashMap.Delete(\"67\"): " << hashMap.Delete("67") << endl; cout << "hashMap.GetValue(\"67\"): " << hashMap.GetValue("67") << endl; getchar(); return 0; } /* 输出： Test Result: 插入条数据耗时： 5.881 秒 hashMap.GetValue("67"): hello hash No.67 hashMap.Delete("67"): hello hash No.67 hashMap.GetValue("67"): NULL */

－End－

getprivateprofilestruct