首页 > 代码库 > 改进hash遍历

改进hash遍历

STL中实现的hash_map和MFC中实现的CMap数据结构均为hash。普通的hash在遍历时,效率会比较慢。hash_map与CMap的遍历均顺序访问每一个桶,因此会在空桶上浪费一定的时间。

1. 改进的hash

哈希结点结构如图1-1(a)所示,其中data为存储的数据,next为指向下一个哈希结点的指针。哈希头结点如图1-1(b)所示,其中preBucket为前一个有数据的桶号,nextBucket为后一个有数据的桶号,hashNode为指向第一个数据的指针。

技术分享

图1-1 哈希结点、头结点示意图

由此定义改进的hash如下:

class hash

{

      int first;

      vector<hashHeadNode> hashTable;

};

其中first指向第一个有数据的桶号,vector即一个容器,可当做可扩展数组处理。

2 改进hash操作

2.1 初始化  

hashTable初始化为一个比实际数据大30%的一个素数hash_size,first值为-1表示没有任何元素,任意头结点的hashNode为空,preBucket、nextBucket均为-1表示该桶前后均无数据。

2.2 插入u

(1) keyBucket =u%hash_size;

(2) 创建一个哈希结点HN,令HN.data = http://www.mamicode.com/u,利用头插法插入到hashTable[keyBucket].hashNode上;

(3) 修改first与hashTable[keyBucket]中的preBucket与nextBucket的值。

2.3 删除元素v

(1) keyBucket =v%hash_size;

(2) 遍历hashTable[keyBucket].hashNode,若找到v则删除。

(3) 修改相应的hashTable[keyBucket]中preBucket、nextBucket的值,且first与keyBucket相同时也应做相应的修改。

2.4 查找w

(1) keyBucket =v%hash_size;

(2) 遍历hashTable[keyBucket].hashNode,若找到w则返回true,否则返回false。

2.5 遍历

(1) first为有数据的桶号;

(2) 遍历完成当前桶(currentBucket),利用hashTable[current]中的nextBucket找到下一个有数据的桶,继续遍历。

3 测试

实际测试数据中遍历会比hash_map、CMap快,查询、插入操作也比hash_map、CMap略快。



改进hash遍历