哈希表的使用--开地址法解决冲突

这是一个简单的哈希表的使用。创建哈希表是使用除数法。解决冲突是利用开地址法中的线性探测再散列法。

简单的一个例子： 再次证明算法和数据结构是分不开的。

/***********************************************************************
Hash_table的使用
哈希表的创建	key-value
哈希表值显示
开地址法解决冲突问题---线性探测再散列法
*********************************************************************/
#include 
  
   
//数据结构
typedef struct 
{
	int Value;	 // value
	int clitime; //冲突次数
}DataType;

typedef struct
{
	DataType *pdata; //数据域
	int HT_len;		// 哈希表长度
	int valnum;		//值的个数
}HashTable;	

//哈希表的创建 
void CreateHashTable(HashTable *pHT,int HT_len,int a[],int valnum,int p)
{
 //分配hashtable空间
	pHT->pdata=new DataType[HT_len];
	if(NULL== pHT->pdata)
		return ;
//初始化哈希表
	for(int i=0;i
   
    pdata[i].Value=-1; //将数据域全部初始为 -1 pHT->pdata[i].clitime=0; //冲突次数 都为 0 } // 映射哈希表 for(int j=0;j
    
     pdata[index].Value == -1){ pHT->pdata[index].Value=a[j]; pHT->pdata[index].clitime=1; } else { do{ index=(index+1)%p; //pHT->pdata[index].clitime++; //这样会改变原来index下冲突值 sum += 1; }while(pHT->pdata[index].Value != -1); pHT->pdata[index].Value=a[j]; pHT->pdata[index].clitime=sum+1; } } pHT->HT_len=HT_len; pHT->valnum=valnum; } int SearchHashTable(HashTable *pHT,int ifind) { int m=pHT->HT_len; int d,index; d=index = ifind % m ; //初始的 Index while(pHT->pdata[index].Value != -1) { if(pHT->pdata[index].Value == ifind) return index; else index=(index+1) %m; if(d==index ) //如果 相等 说明 index已经绕了一圈了 也就是没有 return 0; } return 0; } void DisaplayHashTable(HashTable *pHT) { int num=pHT->HT_len; printf("哈希表的key为: "); for(int i=0;i
     
      pdata[j].Value); printf("\n"); printf("哈希表的冲突次数:"); for(int j=0;j
      
       pdata[j].clitime); printf("\n"); } double HashAvgLen(HashTable *pHT) //求平均查找长度 { double sum=0; for(int i=0;i
       
        HT_len;i++) sum += pHT->pdata[i].clitime; sum /= pHT->valnum; return sum; } void main() { int a[]={23,35,12,56,123,39,342,90}; HashTable H; int HT_len=11; CreateHashTable(&H,HT_len,a,sizeof(a)/sizeof(int),HT_len); DisaplayHashTable(&H); int ifind=123; int pos = SearchHashTable(&H,ifind); printf("%d在hashtable中索引为%d\n",ifind,pos); printf("平均查找长度%.1f\n",HashAvgLen(&H)); }