class SimHash
{
Node**map;//地址链数组
size_t hash(int key)//hash函数，除留取余法
{
return key%SIZE;
}
public:
SimHash()
{
map=new Node*[SIZE];
for(size_t i=0;i<SIZE;i++)map[i]=NULL;//初始化数组为空
}
~SimHash()
{
for(size_t i=0;i<SIZE;i++)//清除所有节点
{
Node*p;
while(p=map[i])
{
map[i]=p->next;
delete p;
}
}
delete[] map;//清除数组
}
void insert(int key,int value)
{
Node*f=find(key);//插入前查询
if(f)
{
f->value=value;//存在键则覆盖
return;
}
Node*p=map[hash(key)];//确定地址链索引
Node*q=new Node(key,value);//创建节点
while(p&&p->next)p=p->next;//索引到地址链末端
if(p)p->next=q;//添加节点
else map[hash(key)]=q;//地址链的第一个节点
}
void remove(int key)
{
Node*p=map[hash(key)];//确定地址链索引
Node*q=NULL;//前驱指针
while(p)
{
if(p->key==key)//找到键
{
if(q)q->next=p->next;//删除节点
else map[hash(key)]=p->next;//删除地址链的最后一个节点
delete p;
break;
}
q=p;
p=p->next;
}
}
Node* find(int key)
{
Node*p=map[hash(key)];//确定地址链索引
while(p)
{
if(p->key==key)break;//查询成功
p=p->next;
}
return p;
}
};
首先，我们需要一个Node**类型的指针map记录地址链数组的地址，至于数组大小，我们给一个较大的值（这里设置为100），为了简化问题，不需要考虑插入时表满等情况。在构造函数和析构函数内对map内存分配和撤销。另外，节点的内存是动态增加的，因此析构时需要单独处理每个地址链表。
对于数据结构，最关键的便是插入、删除、检索操作，为此定义操作insert、remove、find。
检索操作实现时，首先通过hash函数定位地址链表的索引，然后在地址链表上检索键是否存在即可。
插入操作实现时，首先会检索键是否存在，如果存在则仅仅更新对应节点的数据即可，否则创建新的节点，插入到链表的结尾。对于空链表需要做特殊处理。
删除操作实现时，需要使用两个指针记录节点的位置信息，当遇到满足键的节点时，就将该节点从链表内删除即可。如果删除链表的第一个节点，需要做特殊处理。
以上，便是一个较简单的hash_map的实现了，代码行约80行左右，当然这肯定不是最简单的，如果你有兴趣可以再做进一步的简化。
如果考虑哈希表的键值类型、特殊键类型的hash映射（字符串类型键如何映射为数值）、特殊键类型的比较处理（怎么比较两个自定义类型键是否相等）、索引运算重载这些问题的话，hash_map的实现就变得复杂了。不过这些在STL内实现的比较完整，若你感兴趣可以多做了解。这里我给出自己的一个考虑以上问题的简单hash_map实现。
{
size_t operator()(const char* str)const
{
size_t ret=0;
while(*str)ret=(ret<<5)+*str++;
return ret;
}
};
struct str_cmp
{
bool operator()(const char* str1,const char* str2)const
{
while(*str1&&*str2)
{
if(*str1++!=*str2++)return false;
}
return !*str1&&!*str2;
}
};
template<class K,class T>
class Hashnode
{
public:
Hashnode(K k,T d):key(k),data(d),next(NULL)
{}
K key;
T data;
Hashnode*next;
};
template<class K,class T,class H,class C>
class Hashmap
{
Hashnode<K,T>**map;//hash链表数组
size_t div;//数组大小
size_t hash(K key)//hash函数，获取桶号——除留余数法
{
return h(key)%div;
}
H h;
C c;
Hashnode<K,T>* _find(K key)
{
size_t pos=hash(key);//获取桶号
for(Hashnode<K,T>*p=map[pos];p;p=p->next)
{
if(c(p->key,key))//找到了key
{
return p;
}
}
return NULL;
}
public:
size_t size;//hash表容量
size_t count;//元素个数
Hashmap(size_t sz=6):size(6),div(2),count(0)
{
if(sz>6)
{
size=sz;
div=size/3;
}
map=new Hashnode<K,T>*[div];
for(size_t i=0;i<div;i++)map[i]=NULL;
}
~Hashmap()
{
for(size_t i=0;i<div;i++)
{
while(true)
{
Hashnode<K,T>*p=map[i];
if(p)
{
map[i]=p->next;
delete p;
}
else break;
}
}
delete[] map;
}
void insert(K key,T data)
{
if(count>=size)//表满，增加空间
{
Hashnode<K,T>**oldmap=map;
size_t olddiv=div;
size*=2;
div=size/3;
map=new Hashnode<K,T>*[div];
for(size_t i=0;i<div;i++)map[i]=NULL;
for(size_t i=0;i<olddiv;i++)
{
for(Hashnode<K,T>*p=oldmap[i],*t;p;p=t)
{
t=p->next;
p->next=NULL;//消除后继信息
size_t pos=hash(p->key);//重新映射
Hashnode<K,T>*q;
for(q=map[pos];q&&q->next;q=q->next);
if(!q)map[pos]=p;
else q->next=p;
}
}
delete oldmap;
}
Hashnode<K,T>*p=_find(key);//已经存在，替换数据
if(p)p->data=data;
else
{
size_t pos=hash(key);//获取桶号
Hashnode<K,T>*p;
for(p=map[pos];p&&p->next;p=p->next);//索引到最后位置
Hashnode<K,T>*q=new Hashnode<K,T>(key,data);
if(!p)map[pos]=q;//插入数据节点
else p->next=q;
count++;
}
}
void remove(K key)
{
if(count<=size/2)//元素少于一半
{
Hashnode<K,T>**oldmap=map;
size_t olddiv=div;
size/=2;
div=size/3;
map=new Hashnode<K,T>*[div];
for(size_t i=0;i<div;i++)map[i]=NULL;
for(size_t i=0;i<olddiv;i++)
{
for(Hashnode<K,T>*p=oldmap[i],*t;p;p=t)
{
t=p->next;
p->next=NULL;//消除后继信息
size_t pos=hash(p->key);//重新映射
Hashnode<K,T>*q;
for(q=map[pos];q&&q->next;q=q->next);
if(!q)map[pos]=p;
else q->next=p;
}
}
delete oldmap;
}
size_t pos=hash(key);//获取桶号
for(Hashnode<K,T>*p=map[pos],*q=NULL;p;p=p->next)
{
if(c(p->key,key))//找到了key
{
if(q)q->next=p->next;
else map[pos]=p->next;
delete p;
count--;
break;
}
q=p;
}
}
T& get(K key)
{
Hashnode<K,T>*p=_find(key);
if(p)return p->data;
//没有key，插入map[key]=0
insert(key,0);
return get(key);
}
T& operator[](K key)
{
return get(key);
}
bool find(K key)
{
return !!_find(key);
}
};
int main()
{
Hashmap<char*,int,str_hash,str_cmp> hashmap;
hashmap["A"]=1;
hashmap["B"]=2;
hashmap["C"]=3;
hashmap["D"]=4;
hashmap["E"]=5;
hashmap["F"]=6;
hashmap["G"]=7;
hashmap["H"]=8;
cout<<hashmap["A"]<<" "<<hashmap["B"]<<endl;
cout<<hashmap["C"]<<" "<<hashmap["D"]<<endl;
cout<<hashmap["E"]<<" "<<hashmap["F"]<<endl;
cout<<hashmap["G"]<<" "<<hashmap["H"]<<endl;
cout<<hashmap.size<<endl;
hashmap.remove("A");
hashmap.remove("B");
hashmap.remove("C");
hashmap.remove("D");
hashmap.remove("E");
cout<<hashmap.size<<endl;
cout<<hashmap["A"]<<" "<<hashmap["B"]<<endl;
cout<<hashmap["C"]<<" "<<hashmap["D"]<<endl;
cout<<hashmap["E"]<<" "<<hashmap["F"]<<endl;
cout<<hashmap["G"]<<" "<<hashmap["H"]<<endl;
cout<<hashmap.size<<endl;
return 0;
}