哈希表 我的初中 博客分类： 数据结构 数据结构哈希表冲突
前些天胡哥给讲哈希表，悔恨自己没提前看下书，导致后来小伙伴们登台讨论的热火朝天时自己只能充当观众，那酸爽，唉...
当天回家恶补数据结构，发现哈希表其实还是挺容易理解的，就是在实现上面会感觉无从下手，因为自己还没有真正处理过大数据（虽然最近在研究大数据~~），只好自己敲个小程序cos下。
当天在胡哥课上除了哈希表基本思想外，印象最深的就是哈希表的冲突问题，当时听的时候感觉挺高大上，不理解冲突是个什么东东，为什么会发生？后来想了下，我去，不就是初中学过的抽屉原理吗，忘记了的小伙伴请回校复读，哈哈。
额，顺便插一句，推荐大家看一下下面这个视频http://v.163.com/movie/2010/12/R/E/M6UTT5U0I_M6V2TG4RE.html，
麻省理工关于哈希算法的公开课，那光头讲的很细致，通俗易懂吧，楼主耐着性子看完后觉得这4664秒还是挺值得的，想感受下的同学不妨看下。
<!--EndFragment-->好了，言归正传，下面主要说一下自己堆哈希表理解最深的构造方法与解决冲突法方法。
<!--EndFragment--> 哈希表的基本构造方法
构造哈希表的方法是：设要存储的数据元素个数为n，设置一个长度为m（m≥n）的连续内存单元（即数组），分别以每个数据元素的关键字Ki（0≤i≤n-1）为自变量，以哈希函数h(Ki)值为该数据元素在数组中的下标值存储该数据元素。
把构造哈希表时Ki≠Kj（i≠j）,但h(Ki)=h(Kj)的现象称作哈希冲突。
哈希表的构造方法百科上介绍了许多，比如：数字分析，平方取中，伪随机，折叠啊，取余啊。
这里说一下楼主理解最深的折叠法与平方取中法。
折叠法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。
例如：key=123 603 247 112 020 65,哈希表长度为1000，则应把关键字分成3位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为907。
1 2 3
3 0 6
2 4 7
2 1 1
+）0 2 0
——————
9 0 7
平方取中
如果是以字符串形式出现该怎么办呢？
例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址。
|
关键字 |
内部编码 |
内部编码的平方值 |
H(k)关键字的哈希地址 |
|
KEYA |
11050201 |
122157778355001 |
778 |
|
KYAB |
11250102 |
126564795010404 |
795 |
|
AKEY |
01110525 |
001233265775625 |
265 |
|
BKEY |
02110525 |
004454315775625 |
315 |
<!--EndFragment-->
冲突问题
通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免，因此解决冲突是哈希表的另一个关键问题。常用的解决办法有；开放地址法，再哈希法，链地址法以及建立公共溢出区。
开放地址法的基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=（H（key）+di）% m i=1，2，…，n
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。
这里说一下线性探测再散列：（后文代码中会体现）
dii=1，2，3，…，m-1
特点：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
再哈希法（Rehash）是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。比较费时。
关于布隆过滤器，像了解的同学可以到下面网址学习，楼主也只是简单了解下，就不再啰嗦
http://www.cnblogs.com/dolphin0520/archive/2012/11/10/2755089.html
下面是关于哈希表的简单代码
#include<iostream>
using namespace std;
typedef int KeyType; //设关键字域为整形,需要修改类型时，只需修改这里就可以
const int NULLKEY=0; //NULLKEY表示该位置无值
int c=0; //用来统计冲突次数
struct Elemtype //数据元素类型
{
KeyType key;
int ord;
};
int hashsize[]={11,19,29,37,47}; //hash表容量递增表
int Hash_length=0;//hash表表长
class HashTable
{
private:
Elemtype *elem; //数据元素数组,动态申请
int count;// 当前数据元素个数
int size; //决定hash表的容量为第几个,hashsize[size]为当前hash容量
public:
int Init_HashTable() //初始化哈希表
{
int i;
count=0;
size=0; //初始化容量为hashsize[0]=11
Hash_length=hashsize[0];
elem=new Elemtype[Hash_length];
if(!elem)
{
cout<<"内存申请失败"<<endl;
exit(0);
}
for(i=0;i<Hash_length;i++)
elem[i].key=NULLKEY;
return 1;
}
void Destroy_HashTable()
{
delete[]elem;
elem=NULL;
count=0;
size=0;
}
unsigned Hash(KeyType k) //hash函数的一种(取模法)
{
return k%Hash_length;
}
void Collision(int &p,int d) //解决冲突
{
p=(p+d)%Hash_length; //采用开放地址法里的线性探测
}
bool Search_Hash(KeyType k,int &p) //查找
{
//在开放地址hash表中查找关键字等于k的元素
//若找到用p表示待查数据,查找不成功时，p指向的是可插入地址
c=0;
p=Hash(k); //求hash地址
while(elem[p].key!=NULLKEY && elem[p].key!=k)
{
c++;
if(c<Hash_length)
Collision(p,c);
else
return 0; //表示查找不成功
}
if(elem[p].key==k)
return 1;
else
return 0;
}
int Insert_Hash(Elemtype e) //插入
{
//在查找不成功的情况下将k插入到hash表中
int p;
if(Search_Hash(e.key,p))
return -1; //表示该元素已在hash表中
else if(c<hashsize[size]/2) //冲突次数未达到上限
{
//插入e
elem[p]=e;
count++;
return 1;
}
else
ReCreate_HashTable(); // 重建hash表
return 0; //插入失败
}
void ReCreate_HashTable() //重建hash表
{
int i,count2=count;
Elemtype *p,*elem2=new Elemtype[count];
p=elem2;
cout<<"____重建hash表_____"<<endl;
for(i=0;i<Hash_length;i++) //将原有元素暂存到elem2中
if(elem[i].key!=NULLKEY)
*p++=*(elem+i);
count=0;
size++; //hash容量增大
Hash_length=hashsize[size];
p=new Elemtype[Hash_length];
if(!p)
{
cout<<"空间申请失败"<<endl;
exit(0);
}
elem=p;
for(i=0;i<Hash_length;i++)
elem[i].key=NULLKEY;
for(p=elem2;p<elem2+count2;p++) //将原有元素放回新表
Insert_Hash(*p);
}
void Traverse_HashTable()
{
cout<<"哈希地址0->"<<Hash_length-1<<endl;
for(int i=0;i<Hash_length;i++)
if(elem[i].key!=NULLKEY)
cout<<"元素的关键字值和它的标志分别是："<<elem[i].key<<" "<<elem[i].ord<<endl;
}
void Get_Data(int p)
{
cout<<"元素的关键字值和它的标志分别是："<<elem[p].key<<" "<<elem[p].ord<<endl;
}
};
int main()
{
Elemtype r[12]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{5,9},{6,10},{7,11},{8,12}};
HashTable H;
int i,p,j;
KeyType k;
H.Init_HashTable();
for(i=0;i<11;i++) //插入前11个记录
{
j=H.Insert_Hash(r[i]);
if(j==-1)
cout<<"表中已有关键字为"<<r[i].key<<" "<<r[i].ord<<"的记录"<<endl;
}
cout<<"按哈希地址顺序遍历哈希表"<<endl;
H.Traverse_HashTable();
cout<<endl;
cout<<"输入要查找的记录的关键字：";
cin>>k;
j=H.Search_Hash(k,p);
if(j==1)
H.Get_Data(p);
else
cout<<"无此记录"<<endl;
j=H.Insert_Hash(r[11]); //插入最后一个元素
if(j==0)
{
cout<<"插入失败"<<endl;
cout<<"需要重建哈希表才可以插入"<<endl;
cout<<"____重建哈希表____"<<endl;
H.Insert_Hash(r[i]); //重建后重新插入
}
cout<<"遍历重建后的哈希表"<<endl;
H.Traverse_HashTable();
cout<<endl;
cout<<"输入要查找的记录的关键字：";
cin>>k;
j=H.Search_Hash(k,p);
if(j==1)
H.Get_Data(p);
else
cout<<"该记录不存在"<<endl;
cout<<"____销毁哈希表____"<<endl;
H.Destroy_HashTable();
return 0;
}
<!--EndFragment--><!--EndFragment--><!--EndFragment--><!--EndFragment--><!--EndFragment-->