散列表分离链结法C++简单实现与vs2015的一个bug

前段时间整理了一下项目代码，恢复了一下系统，发现vs2015的一个bug，以前写的对话框类在vs2015下编译失败，由于对话框需要theme支持，调用了INITCOMMONCONTROLSEX api，不论是否指定sdk里的comctl32.lib，系统始终无法链结上这个函数，这个真的很无语，同样的代码在其它版本或是mingw里完全没有问题。想起win32++项目是支持vs2015的，里面的对话框可以显示系统样式，查看了一下源代码，原来作者使用的是动态dll里直接调用这个函数来规避这个问题，晕。
由于对话框需要一个数据结构来管理窗口对象，所以重新写了一下HashMap散列表数据结构：
采用分离链结法+素数实现，使用特殊表头使内存占用小。自动计算素数以重新散列元素，让元素均匀分布，可使元素查找线性时间进一步缩短。
// itypes.h
#ifndef __INTYPE_HEADER__
#define __INTYPE_HEADER__
#ifdef _MSC_VER
#if _MSC_VER < 1600
typedef unsigned int uint32_t;
typedef unsigned char uint8_t;
typedef unsigned __int64 uint64_t;
typedef __int64 int64_t;
#else
#include <stdint.h>
#endif
#else
#include <stdint.h>
#endif
#endif
#include <stdio.h>
#include "itypes.h"
#include <stdlib.h>
#include <string>
typedef unsigned int size_t;
struct tagPrime
{
// 判断某个数是否是素数
bool isPrime(uint32_t n)
{
if(n < 2) return false;
for(unsigned i = 2; i*i <= n; ++i)
{
if(n % i == 0) return false;
}
return true;
}
// 获取某个数后第一个素数
uint32_t next(uint32_t n)
{
for(++n; !isPrime(n); ++n)
;
return n;
}
}Prime;
// key-value结点
template<typename KeyType, typename ValType>
struct TNode
{
KeyType key;
ValType value;
TNode* next;
};
// 头结点
template<class T>
struct THead
{
THead():next(0){}
T* next;
};
// 散列表，采用分离链结法+素数实现，使用特殊表头使内存占用小。
// 自动计算素数以重新散列元素，让元素均匀分布，可使元素查找线性时间进一步缩短。
template<class Key, class Value>
class HashMap
{
typedef TNode<Key, Value> Node;
typedef THead<Node> Head;
public:
HashMap()
:table(0), tab_size(0), node_size(0)
{
tab_size = Prime.next(4);
table = new Head[tab_size];
}
~HashMap()
{
clear();
delete[] table;
}
unsigned hash(const std::string& key)
{
return hash(key.c_str());
}
// C数据结构一书中提出的一种字符串hash计算公式
uint32_t hash(const char* key)
{
uint32_t hash_val = 0;
while(*key)
hash_val = (hash_val << 5) + *key++;
return hash_val;
}
// 普通整数，没啥可说的，主要是配合程序需要
uint32_t hash(uint32_t key)
{
return key;
}
// 清空hash表元素
void clear()
{
for(size_t i = 0; i < tab_size; ++i)
{
Node * node =table[i].next;
while(node){
Node* tmp = node->next;
delete node;
node = tmp;
}
}
node_size = 0;
}
// 根据关键字添加或修改键值，不用于查找不存在的键。
Value& operator[](const Key& key)
{
size_t index = hash(key) % tab_size;
Node* node = table[index].next;
while(node)
{
if(node->key == key){
return node->value;
}
node = node->next;
}
//没有找到则添加一个新key结点
node = new Node;
node->next = table[index].next;
table[index].next = node;
node->key = key;
++node_size; //增加元素计数
return node->value;
}
// 重新散列原表中的元素（当达到装填因子load_factor时）
void rehash()
{
Head* tmp = table;
size_t tsize = tab_size;
if(!need_load()) return;//没有达到装填因子， 则返回
tab_size = Prime.next(node_size);//计算合适的素数
table = new Head[tab_size];
for(size_t i = 0; i < tsize; ++i)
{
Node* node = tmp[i].next;
while(node){
Node* pn = node->next;
//重新散列到新表
size_t index = hash(node->key) % tab_size;
node->next = table[ index ].next;
table[ index ].next = node;
node = pn;
}
}
delete[] tmp;
}
// 查询键值，不会增加元素
bool find(const Key& key, Value& val)
{
size_t index = hash(key) % tab_size;
Node* node = table[ index ].next;
for(;node; node = node->next)
{
if(node->key == key){
val = node->value;
return true;
}
}
return false;
}
// 删除某个元素
void remove(const Key& key)
{
Node head; //使用临时表头删除无表头链表
size_t index = hash(key) % tab_size;
head.next = table[ index ].next;
Node* prev = &head;
Node* node = prev->next;
while(node)
{
if(node->key == key){
prev->next = node->next;
delete node;
--node_size;
table[ index ].next = head.next;
return;
}
node = node->next;
prev = prev->next;
}
}
// 返回元素总个数
inline size_t size() const
{
return node_size;
}
void test1()
{
if((node_size * 10 / tab_size ) >= 9 )
puts("over load_factor");
else
puts("less load_factor");
}
void test2()
{
for(size_t i = 0; i < tab_size; ++i)
printf("%s ", table[i].next == NULL ? "null" : "node");
putchar('\n');
}
private:
bool need_load()
{
return (node_size * 10 / tab_size) > load_factor;
}
private:
Head* table;
size_t tab_size;
size_tnode_size;
static const int load_factor = 9; //装填因子(1.0 = 10, 0.9 = 9)
};
// 测试代码：
int main()
{
HashMap<std::string, int> map;
printf("size of HashMap:%u\n", sizeof(map));
//添加一些键值
map["C"] = 1;
map["C++"] = 2;
map["C#"] = 3;
map["Java"] = 4;
printf("now map size :%u\n", map.size());
map.test2();
int x;
if(map.find("Java", x))
printf("found key=Java, value=%d\n", x);
else
puts("not found");
//修改键值
map["Java"] = 6;
puts("modify data");
if(map.find("Java", x))
printf("found key=Java, value=%d\n", x);
// 删除键值
map.remove("Java");
printf("now map size :%u\n", map.size());
if(map.find("Java", x))
printf("found key, value=%d\n", x);
else
puts("not found");
}
运行结果：
size of HashMap:12
now map size :4
null null node node node
found key=Java, value=4
modify data
found key=Java, value=6
now map size :3
not found
请按任意键继续. . .
总结：
这个基本上算是内存使用量最少的实现了，链表没有表头，所以删除时，使用一个临时表头的算法来减少代码量。后续思考：模运算很费CPU时间，另一个办法是产生2的N次方个表头，计算hash值的时候就可以不用模运算了，这个数据结构还有很多实现方法，