/*____________________________________________________________________________________________________________ 【1】哈希算法描述： 【哈希法】又称【散列法】、杂凑法或关键字地址计算法等，相应的表称为哈希表、散列表、杂凑表等 【基本思想】：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为【哈希函数】 【创建哈希表时】把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数 计算出该元素的存储位置：p=H（k），从而达到按关键字直接存取元素的目的。 【2】哈希法主要包括以下两方面的内容： （1）如何构造哈希函数 （2）如何处理冲突 【3】哈希函数的构造方法 （1）数字分析法 （）平方取中法 （）分段叠加法 （）除留余数法 （）伪随机数发 【4】处理冲突的方法 （1）开放定址法 <1>线性探测再散列 <2>二次探测再散列 <3>伪随机探测再散列 （2）再哈希法 （3）链地址法 _______________________________________________________________________________________________________________*/ #include<iostream> using namespace std;
#define HASH_LENGTH 13 //创建哈希表的长度 #define TABLE_LENGTH 8 //原始数组的长度 int srcData[TABLE_LENGTH]={56,68,92,39,95,62,29,55}; //原始数据 int hashTable[HASH_LENGTH]={0}; //哈希表，初始化为0 /*___________________________________________________________________________________________________________ 模块说明： 将关键字data插入到哈希表中 ____________________________________________________________________________________________________________*/ template<typename ElemType>void HashInseart(ElemType hashTable[],int iMod,ElemType data) { int hashAdd = data%iMod; //计算哈希地址 while(hashTable[hashAdd]) //如果元素的位置已被占用，则利用冲突的解决办法 { hashAdd = (++hashAdd)%iMod; //利用【线性探测再散列】法解决冲突 } hashTable[hashAdd] = data; //找到合适的位置，则将元素进行插入 } /*____________________________________________________________________________________________________________ 模块说明： 创建哈希表 ____________________________________________________________________________________________________________*/ template<typename ElemType>void CreateHashTable(ElemType hashTable[],int iMod,ElemType data[],int Length) { for(int i=0;i<Length;i++) //循环将原始数据插入到哈希表中 { HashInseart<int>(hashTable,iMod,data[i]); //调用哈希表的插入函数 } } /*__________________________________________________________________________________________________________ 模块说明 哈希查找法 ___________________________________________________________________________________________________________*/ template <typename ElemType>ElemType HashSearch(ElemType hashTable[],int iMod,ElemType key) { int iHashAdd=key%HASH_LENGTH; //计算哈希地址 while(hashTable[iHashAdd]&&hashTable[iHashAdd]!=key) //判断地址是否有冲突 { iHashAdd = (++iHashAdd)%iMod; } if(hashTable[iHashAdd]==0) { return -1; } else { return iHashAdd; }
} /*____________________________________________________________________________________________________________ 模块说明 控制台应用程序，我们的函数从这里开始 _____________________________________________________________________________________________________________*/ int main() { CreateHashTable<int>(hashTable,HASH_LENGTH,srcData,TABLE_LENGTH); //调用函数创建哈希表 std::cout<<"【注意：】哈希表中各元素值如下："<<std::endl; for(int i=0;i<HASH_LENGTH;i++) { cout<<hashTable[i]<<" "; } std::cout<<endl; int iPos = HashSearch<int>(hashTable,HASH_LENGTH,92); std::cout<<"查找值的所在位置："<<iPos<<std::endl; if(iPos>0) { std::cout<<"查找成功，该关键字位于数组第"<<iPos<<"位置"<<std::endl; } else { std::cout<<"查找不成功"<<std::endl; }
system("pause"); return 0; }
