日常编程中肯定经常用到哈希表，可是否还记得哈希表的内部实现机制？是否还记得哈希表按照冲突解决的方式可以分为链式哈希表、溢出哈希表、随机哈希表 ... ？ 溢出hash表设计图 来源：xsdsp [ 点击放大] 介绍溢出哈希表的实现机理，并给出具体实现代码。溢出哈希表是在hash 表填入过程中，将冲突的元素顺序填入到溢出表中，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。 溢出哈希表的设计图，具体实现如下： 首先：哈希表中每个元素被称为Node,Node类必须包含两个函数：GetKey，Hash。GetKey返回每个节点Node的键值key，key值唯一标识节点Node；Hash函数用于生成Node对象Key的对应hash値，下面给出Node的具体定义： class NodeStruct { private: unsigned int key; public: //使用nelement计算NodeStruct对象的hash值 static inline unsigned int Hash (unsigned int nelement) { return key % modulo; } //获得NodeStruct对象的key值 inline unsigned int GetKey () { return key; } } 我将介绍如何在overflow Hash表中查找key值对应node节点。 上一章我们大致描述了overflow Hash表，这一章我们将具体绍如何在overflow Hash表中查找key值对应node节点创建_table，_overflowBits，_allocBits，其中_table是保存哈希表中Node的数组，_allocBits中的第n位标识_table中的第n个Node是否已经创建，1标识_table中的第n个Node已经被创建，0标识_table中第n个Node是否overflow，_overflowBit中的第n位标识_table中的第n个Node是否发生冲突，下面是查询与创建node的具体实现: NodeStruct * OverfolwHash::Lookup (unsigned int key) { //对掩码进行初始化 const uint32_t upperBit = 0x80000000; //计算key对应的hash值 unsigned int entry = NodeStruct::Hash(key, _numElements); //ptr为key对应Node在_table中的起始位置 NODE *ptr = &_table[entry]; NODE *ptrEnd = &_table[_numElements]; //allocPtr为key对应Node在_allocBits中的位置，因为_allocBits数组的类型是uint32_t， //所以需要对entry向右位移5位 uint32_t *allocPtr = &_allocBits[entry >> 5]; // overflowPtr为key对应Node在_ overflowBits中的位置 uint32_t *overflowPtr = &_overflowBits[entry >> 5]; uint32_t mask = upperBit >> (entry & 31); for(;;) { //如果allocPtr没有创建Node，没有占用 if((*allocPtr & mask) == 0) return NULL; //判断ptr指向节点的key值与查询的key值是否相等，如果相等， //则ptr就是查询的Node if(ptr->GetKey() == key) return ptr; //如果对应的溢出位为零，则hash表中没有对应key值的节点，返回； //如果对应的溢出位不为零，则标识hash表对应节点发生冲突，继续在hash表中查找key值对应节点 if((*overflowPtr & mask) == 0) return NULL; //遍历到_table的最末节点ptrEnd，则重新从_table的头部开始查找 if((++ptr) == ptrEnd) { entry = 0; ptr = _table; allocPtr = _allocBits; overflowPtr = _overflowBits; mask = upperBit; } else { mask >>= 1; if(mask == 0) { allocPtr++; overflowPtr++; mask = upperBit; } } } } 下一章我将介绍如何在overflow Hash表中创建key值对应node节点。 本章我将介绍如果在hash表中如果不存在key所对应的node节点，则在hash表中创建key值对应node节点，然后置位_ allocBits对应位。下面是具体实现: //key为查找节点的key值；receiveNode为查找到的节点 bool OverfolwHash::LookupOrAlloc (unsigned int key, NodeStruct **receiveNode) { //对掩码进行初始化 const uint32_t upperBit = 0x80000000; //计算key对应的hash值,其中_numElements为hash表中_table元素的个数 unsigned int entry = NODE::Hash(key, _numElements); //ptr为key对应Node在_table中的起始位置 NodeStruct *ptr = &_table[entry]; NodeStruct *ptrEnd = &_table[_numElements]; //allocPtr为key对应Node在_allocBits中的位置，因为_allocBits数组的类型是uint32_t， //所以需要对entry向右位移5位 uint32_t *allocPtr = &_allocBits[entry >> 5]; uint32_t *overflowPtr = &_overflowBits[entry >> 5]; uint32_t mask = upperBit >> (entry & 31); for(;;) { //如果allocPtr没有创建Node，没有占用 if((*allocPtr & mask) == 0) { 置位_ allocBits对应位 *allocPtr |= mask; *receiveNode = ptr; //创建新节点，则返回false return false; } //找到对应节点 if(ptr->GetKey() == key) { *receiveNode = ptr; return true; } //查询节点在hash表中出现冲突，置位冲突数组overflowPtr对应位 *overflowPtr |= mask; if((++ptr) == ptrEnd) { ptr = _table; allocPtr = _allocBits; overflowPtr = _overflowBits; mask = upperBit; } else { mask >>= 1; if(mask == 0) { allocPtr++; overflowPtr++; mask = upperBit; } } } } }; 下一章，我将介绍如何构造溢出、重置、析构溢出hash表. 本章如何构造溢出、重置、析构溢出hash表 首先介绍如何构造hash表: /* * 参数numElements为hash表中_table元素的数目 * 参数_overflowBits为溢出标识位，标识_table对应节点是否溢出 * 参数_allocBits为分配标识位，标识_table对应节点是否已分配 */ explicit OverfolwHash::FastS_HashOverflow (unsigned int numElements) : _numElements(numElements), _table(new NodeStruct [numElements]), _overflowBits(new uint32_t[(numElements + 31) >> 5]), _allocBits(new uint32_t[(numElements + 31) >> 5]) { //处置_table,_overflowBits,_allocBits Reset(); } 接下来我们来看看重置函数Reset： void OverfolwHash::Reset () { size_t numBytes = sizeof(uint32_t) * ((_numElements + 31) >> 5); //重置_overflowBits，将其每一位置零 memset(_overflowBits, 0, numBytes); //重置_allocBits，将其每一位置零 memset(_allocBits, 0, numBytes); } 最后来看看如何析构溢出hash表： OverfolwHash::~ OverfolwHash () { //删除_table、_overflowBits、_allocBits delete [] _table; delete [] _overflowBits; delete [] _allocBits; } 下一章，我将介绍如果使用这个溢出hash表。 本章将具体讲解如何使用overflowhash: 首先定义hash表中的节点： class NodeStruct { private: unsigned int key; public: //使用nelement计算NodeStruct对象的hash值 static inline unsigned int Hash (unsigned int nelement) { return key % modulo; } //获得NodeStruct对象的key值 inline unsigned int GetKey () { return key; } NodeStruct( pkey ) : key(pkey) { } void PrintKey() { Std::cout<<”the node’s key is ”<<key<<std::endl; }="" <="" blockquote="" style="margin: 0px; padding: 0px; "> 最后，我们代码中首先创建溢出哈希表_table,然后从其中查找或分配key值对应的NodeStruct. void main() { HashOverflow *_table = new HashOverflow(100); NodeStruct **pnode = NULL; for( unsigned int key=0; key<100; ++key ) { If(_table-> LookupOrAlloc(key, pnode)) (*pnode)-> PrintKey(); } } 具体执行结果见下图