哈希表,12个字符串使用BKDR算法生成的整数再用取余法居然冲突6次!!!!
最近在看hash表,发现网上的BKDR算法都说处理字符串很好,我就试了试,结果发现用取余法,竟然冲突了6次,到底怎么回事,我看到人家帖子里面测试都是100万个字符串才冲突了4000多次,难道是我用的不对吗?贴上代码,高手求教
int CTreeEventDlg::ModMethod(int iKeyNum)
{//取余
int iHashKey=iKeyNum%11;
return iHashKey;
}
int CTreeEventDlg::OpenAddressing(int iHashKeyFailed,int iDi)
{//二次探测法
int iHashKey=0;
iHashKey=(iHashKeyFailed+iDi)%12;
return iHashKey;
}
// BKDR Hash
unsigned int BKDRHash(char *str)
{//网上找的BKDR
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
void CTreeEventDlg::OnButton11()
{
// TODO: Add your control notification handler code here
StaffInfo staffs[12];
staffs[0].phoneNum="www.2013666.com ";
staffs[1].phoneNum="13927156666";
staffs[2].phoneNum="@_fdsa";
staffs[3].phoneNum="gfdgfdsgfdsg";
staffs[4].phoneNum="*___ ";
staffs[5].phoneNum="ewqe23e";
staffs[6].phoneNum="543254328800";
staffs[7].phoneNum="0!!!!!!!!!!";
staffs[8].phoneNum="13725036666";
staffs[9].phoneNum="8800676547654765";
staffs[10].phoneNum="613425386666";
staffs[11].phoneNum=" Hello";
StaffInfo staffsHash[12];
int iCount=sizeof(staffs)/sizeof(*staffs);
for (int iCountLoop=0;iCountLoop<iCount;iCountLoop++)
{
staffsHash[iCountLoop].phoneNum=NULL;
}
for (iCountLoop=0;iCountLoop<iCount;iCountLoop++)
{
unsigned int iBKDRValue=BKDRHash(staffs[iCountLoop].phoneNum);
int iHashIndex=ModMethod(iBKDRValue);
int iPositive=0;
int iLoopNum=0;
while(staffsHash[iHashIndex].phoneNum!=NULL || iHashIndex<0)
{
//进入此处循环表示哈希表的时候遇到了冲突
if (iPositive==0)
{
int iDi=iLoopNum*iLoopNum;
iHashIndex=OpenAddressing(iHashIndex,iDi);
iPositive=-1;
}else if (iPositive==-1)
{
int iDi=-iLoopNum*iLoopNum;
iHashIndex=OpenAddressing(iHashIndex,iDi);
iPositive=0;
}
iLoopNum++;
}
if (staffsHash[iHashIndex].phoneNum==NULL)
{
staffsHash[iHashIndex].phoneNum=staffs[iCountLoop].phoneNum;
}
}
int a=1;
}
