c语言哈希数

1. C语言实现哈希表的相关运算算法 编写程序实现哈希表的构造过程。

#define MaxSize 100 //定义最大哈希表长度
#define NULLKEY -1 //定义空关键字值
#define DELKEY -2 //定义被删关键字值
typedef int KeyType; //关键字类型
typedef char * InfoType; //其他数据类型
typedef struct
{
KeyType key; //关键字域
InfoType data; //其他数据域
int count; //探查次数域
} HashData;

typedef HashData HashTable[MaxSize]; //哈希表类型

void InsertHT(HashTable ha,int &n,KeyType k,int p) //将关键字k插入到哈希表中
{
int i,adr;
adr=k % p;
if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]可以直接放在哈希表中
{
ha[adr].key=k;
ha[adr].count=1;
}
else //发生冲突时采用线性探查法解决冲突
{
i=1; //i记录x[j]发生冲突的次数
do
{
adr=(adr+1) % p;
i++;
}
while (ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);
ha[adr].key=k;
ha[adr].count=i;
}
n++;
}
void CreateHT(HashTable ha,KeyType x[],int n,

2. 谁能帮忙写一个C语言的哈希排序小女感激不尽~~

1.选择合适的哈希函数H(key)=key%p(p为小于或等于哈希表长的最大质数)；
2.计算各个关键字的直接哈希函数值；
3.根据处理冲突的方法建立哈希表，并输出；
4.在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。

#include<stdlib.h>
#include<stdio.h>
#define NULL 0
typedef int KeyType;
typedef struct
{
KeyType key;
} ElemType;
int haxi(KeyType key,int m) /*根据哈希表长m，构造除留余数法的哈希函数haxi*/
{
int i,p,flag;
for(p=m;p>=2;p--) /*p为不超过m的最大素数*/
{
for(i=2,flag=1;i<=p/2&&flag;i++)
if(p%i==0)
flag=0;
if(flag==1)
break;
}
return key%p; /*哈希函数*/
}
void inputdata(ElemType **ST,int n) /*从键盘输入n个数据，存入数据表ST(采用动态分配的数组空间)*/
{
KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf("\nPlease input %d data:",n);
for(i=1;i<=n;i++)
scanf("%d",&((*ST)[i].key));
}
void createhaxi(ElemType **HASH,ElemType *ST,int n,int m) /*由数据表ST构造哈希表HASH，n、m分别为数据集合ST和哈希表的长度*/
{
int i,j;
(*HASH)=(ElemType *)malloc(m*sizeof(ElemType));
for(i=0;i<m;i++)
(*HASH)[i].key=NULL; /*初始化哈希为空表(以0表示空)*/
for(i=0;i<n;i++)
{
j=haxi(ST[i].key,m); /*获得直接哈希地址*/
while((*HASH)[j].key!=NULL)
j=(j+1)%m; /*用线性探测再散列技术确定存放位置*/
(*HASH)[j].key=ST[i].key; /*将元素存入哈希表的相应位置*/
}
}
int search(ElemType *HASH,KeyType key,int m,int *time) /*在表长为m的哈希表中查找关键字等于key的元素，并用time记录比较次数，若查找成功，函数返回值为其在哈希表中的位置，否则返回-1*/
{
int i;
*time=1;
i=haxi(key,m);
while(HASH[i].key!=0&&HASH[i].key!=key)
{
i++;
++*time;
}
if(HASH[i].key==0)
return -1;
else
return i;
}
main()
{
ElemType *ST,*HASH;
KeyType key;
int i,n,m,stime,time;
char ch;
printf("\nPlease input n&&m(n<=m)"); /*输入关键字集合元素个数和哈希表长*/
scanf("%d%d",&n,&m);
inputdata(&ST,n); /*输入n个数据*/
createhaxi(&HASH,ST,n,m); /*创建哈希表*/
printf("\nThe haxi Table is\n"); /*输出已建立的哈希表*/
for(i=0;i<m;i++)
printf("%5d",i);
printf("\n");
for(i=0;i<m;i++)
printf("%5d",HASH[i].key);
do /*哈希表的查找，可进行多次查找*/
{
printf("\nInput the key you want to search:");
scanf("%d",&key);
i=search(HASH,key,m,&time);
if(i!=-1) /*查找成功*/
{
printf("\nSuccess,the position is %d",i);
printf("\nThe time of compare is %d",time);
}
else /*查找失败*/
{
printf("\nUnsuccess");
printf("\nThe time of compare is %d",time);
}
printf("\nContiue(y/n):\n"); /*是否继续查找yes or no*/
ch=getch();
}
while(ch=='y'||ch=='Y'); /*计算表在等概率情况下的平均查找长度，并输出*/
for(stime=0,i=0;i<n;i++)
{
search(HASH,ST[i].key,m,&time);
stime+=time;
}
printf("\nThe Average Search Length is %5.2f",(float)stime/n);
ch=getch();
}

3. 这段C语言代码如何转换成Python语言（关于哈希表）

将以上 C 语言代码转换为 Python 语言可能需要对哈希表和其他数据结构进行重新实现。但是可以提供一个类似的实现方式
def search_hash(hash_table, name):
collisions = 0 # to keep track of number of collisions
index = hash_function(name)
while hash_table[index] is not None and hash_table[index]['name'] != name:
collisions += 1
index = collision_resolution(index)
if hash_table[index] is not None:
print("Search successful! Number of collisions:", collisions)
print("Name: ", hash_table[index]['name'])
print("ID: ", hash_table[index]['id'])
print("Phone: ", hash_table[index]['phone'])
else:
print("Search unsuccessful.")
这个例子使用了字典来存储联系人的信息，其中 'name'，'id' 和 'phone' 是字典的键。hash_function() 和 collision_resolution() 函数可以用 Python 中的内置函数来实现，或者自己实现。
注意，这只是一种类似的实现方式，并不能完全替代原来的代码，还需要根据实际需求进行修改。
另外,在 Python 中可以使用字典或字典组成的列表来存肆指储哈希表,可以使用字典中的 get() 方法或者列表中的 in 关键字来查找一个元素是否在字典或列表中，如果要实现类似 C 语言中的冲突解决方式明察，可以在字典中使用链表或线性探测法来实现激雹茄。
这里只是给出了一种可能的实现方式，具体实现还需要根据具体需求进行调整。

4. 如何使用C语言获取文件的SHA1哈希值

有现成的SHA1算法函数

复制过来。

然后打开文件， 读数据， 调用SHA1函数即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<errno.h>

#undefBIG_ENDIAN_HOST
typedefunsignedintu32;

/****************
*Rotatea32bitintegerbynbytes
*/
#ifdefined(__GNUC__)&&defined(__i386__)
staticinlineu32
	rol(u32x,intn)
{
	__asm__("roll%%cl,%0"
		:"=r"(x)
		:"0"(x),"c"(n));
	returnx;
}
#else
#definerol(x,n)(((x)<<(n))|((x)>>(32-(n))))
#endif


typedefstruct{
	u32h0,h1,h2,h3,h4;
	u32nblocks;
	unsignedcharbuf[64];
	intcount;
}SHA1_CONTEXT;void
	sha1_init(SHA1_CONTEXT*hd)
{
	hd->h0=0x67452301;
	hd->h1=0xefcdab89;
	hd->h2=0x98badcfe;
	hd->h3=0x10325476;
	hd->h4=0xc3d2e1f0;
	hd->nblocks=0;
	hd->count=0;
}


/****************
*-bit-words
*/
staticvoid
	transform(SHA1_CONTEXT*hd,unsignedchar*data)
{
	u32a,b,c,d,e,tm;
	u32x[16];

	/*getvaluesfromthechainingvars*/
	a=hd->h0;
	b=hd->h1;
	c=hd->h2;
	d=hd->h3;
	e=hd->h4;

#ifdefBIG_ENDIAN_HOST
	memcpy(x,data,64);
#else
	{
		inti;
		unsignedchar*p2;
		for(i=0,p2=(unsignedchar*)x;i<16;i++,p2+=4)
		{
			p2[3]=*data++;
			p2[2]=*data++;
			p2[1]=*data++;
			p2[0]=*data++;
		}
	}
#endif


#defineK10x5A827999L
#defineK20x6ED9EBA1L
#defineK30x8F1BBCDCL
#defineK40xCA62C1D6L
#defineF1(x,y,z)(z^(x&(y^z)))
#defineF2(x,y,z)(x^y^z)
#defineF3(x,y,z)((x&y)|(z&(x|y)))
#defineF4(x,y,z)(x^y^z)


#defineM(i)(tm=x[i&0x0f]^x[(i-14)&0x0f]
	^x[(i-8)&0x0f]^x[(i-3)&0x0f]
	,(x[i&0x0f]=rol(tm,1)))

#defineR(a,b,c,d,e,f,k,m)do{e+=rol(a,5)
	+f(b,c,d)
	+k	
	+m;	
	b=rol(b,30);
	}while(0)
	R(a,b,c,d,e,F1,K1,x[0]);
	R(e,a,b,c,d,F1,K1,x[1]);
	R(d,e,a,b,c,F1,K1,x[2]);
	R(c,d,e,a,b,F1,K1,x[3]);
	R(b,c,d,e,a,F1,K1,x[4]);
	R(a,b,c,d,e,F1,K1,x[5]);
	R(e,a,b,c,d,F1,K1,x[6]);
	R(d,e,a,b,c,F1,K1,x[7]);
	R(c,d,e,a,b,F1,K1,x[8]);
	R(b,c,d,e,a,F1,K1,x[9]);
	R(a,b,c,d,e,F1,K1,x[10]);
	R(e,a,b,c,d,F1,K1,x[11]);
	R(d,e,a,b,c,F1,K1,x[12]);
	R(c,d,e,a,b,F1,K1,x[13]);
	R(b,c,d,e,a,F1,K1,x[14]);
	R(a,b,c,d,e,F1,K1,x[15]);
	R(e,a,b,c,d,F1,K1,M(16));
	R(d,e,a,b,c,F1,K1,M(17));
	R(c,d,e,a,b,F1,K1,M(18));
	R(b,c,d,e,a,F1,K1,M(19));
	R(a,b,c,d,e,F2,K2,M(20));
	R(e,a,b,c,d,F2,K2,M(21));
	R(d,e,a,b,c,F2,K2,M(22));
	R(c,d,e,a,b,F2,K2,M(23));
	R(b,c,d,e,a,F2,K2,M(24));
	R(a,b,c,d,e,F2,K2,M(25));
	R(e,a,b,c,d,F2,K2,M(26));
	R(d,e,a,b,c,F2,K2,M(27));
	R(c,d,e,a,b,F2,K2,M(28));
	R(b,c,d,e,a,F2,K2,M(29));
	R(a,b,c,d,e,F2,K2,M(30));
	R(e,a,b,c,d,F2,K2,M(31));
	R(d,e,a,b,c,F2,K2,M(32));
	R(c,d,e,a,b,F2,K2,M(33));
	R(b,c,d,e,a,F2,K2,M(34));
	R(a,b,c,d,e,F2,K2,M(35));
	R(e,a,b,c,d,F2,K2,M(36));
	R(d,e,a,b,c,F2,K2,M(37));
	R(c,d,e,a,b,F2,K2,M(38));
	R(b,c,d,e,a,F2,K2,M(39));
	R(a,b,c,d,e,F3,K3,M(40));
	R(e,a,b,c,d,F3,K3,M(41));
	R(d,e,a,b,c,F3,K3,M(42));
	R(c,d,e,a,b,F3,K3,M(43));
	R(b,c,d,e,a,F3,K3,M(44));
	R(a,b,c,d,e,F3,K3,M(45));
	R(e,a,b,c,d,F3,K3,M(46));
	R(d,e,a,b,c,F3,K3,M(47));
	R(c,d,e,a,b,F3,K3,M(48));
	R(b,c,d,e,a,F3,K3,M(49));
	R(a,b,c,d,e,F3,K3,M(50));
	R(e,a,b,c,d,F3,K3,M(51));
	R(d,e,a,b,c,F3,K3,M(52));
	R(c,d,e,a,b,F3,K3,M(53));
	R(b,c,d,e,a,F3,K3,M(54));
	R(a,b,c,d,e,F3,K3,M(55));
	R(e,a,b,c,d,F3,K3,M(56));
	R(d,e,a,b,c,F3,K3,M(57));
	R(c,d,e,a,b,F3,K3,M(58));
	R(b,c,d,e,a,F3,K3,M(59));
	R(a,b,c,d,e,F4,K4,M(60));
	R(e,a,b,c,d,F4,K4,M(61));
	R(d,e,a,b,c,F4,K4,M(62));
	R(c,d,e,a,b,F4,K4,M(63));
	R(b,c,d,e,a,F4,K4,M(64));
	R(a,b,c,d,e,F4,K4,M(65));
	R(e,a,b,c,d,F4,K4,M(66));
	R(d,e,a,b,c,F4,K4,M(67));
	R(c,d,e,a,b,F4,K4,M(68));
	R(b,c,d,e,a,F4,K4,M(69));
	R(a,b,c,d,e,F4,K4,M(70));
	R(e,a,b,c,d,F4,K4,M(71));
	R(d,e,a,b,c,F4,K4,M(72));
	R(c,d,e,a,b,F4,K4,M(73));
	R(b,c,d,e,a,F4,K4,M(74));
	R(a,b,c,d,e,F4,K4,M(75));
	R(e,a,b,c,d,F4,K4,M(76));
	R(d,e,a,b,c,F4,K4,M(77));
	R(c,d,e,a,b,F4,K4,M(78));
	R(b,c,d,e,a,F4,K4,M(79));

	/*Updatechainingvars*/
	hd->h0+=a;
	hd->h1+=b;
	hd->h2+=c;
	hd->h3+=d;
	hd->h4+=e;
}


/*
*ofINBUFwithlengthINLEN.
*/
staticvoid
	sha1_write(SHA1_CONTEXT*hd,unsignedchar*inbuf,size_tinlen)
{
	if(hd->count==64){/*flushthebuffer*/
		transform(hd,hd->buf);
		hd->count=0;
		hd->nblocks++;
	}
	if(!inbuf)
		return;
	if(hd->count){
		for(;inlen&&hd->count<64;inlen--)
			hd->buf[hd->count++]=*inbuf++;
		sha1_write(hd,NULL,0);
		if(!inlen)
			return;
	}

	while(inlen>=64){
		transform(hd,inbuf);
		hd->count=0;
		hd->nblocks++;
		inlen-=64;
		inbuf+=64;
	}
	for(;inlen&&hd->count<64;inlen--)
		hd->buf[hd->count++]=*inbuf++;
}


/*
*returnsthedigest.
*,butaddingbytestothe
*.
*Returns:20bytesrepresentingthedigest.
*/

staticvoid
	sha1_final(SHA1_CONTEXT*hd)
{
	u32t,msb,lsb;
	unsignedchar*p;

	sha1_write(hd,NULL,0);/*flush*/;

	t=hd->nblocks;
	/*multiplyby64tomakeabytecount*/
	lsb=t<<6;
	msb=t>>26;
	/*addthecount*/
	t=lsb;
	if((lsb+=hd->count)<t)
		msb++;
	/*multiplyby8tomakeabitcount*/
	t=lsb;
	lsb<<=3;
	msb<<=3;
	msb|=t>>29;

	if(hd->count<56){/*enoughroom*/
		hd->buf[hd->count++]=0x80;/*pad*/
		while(hd->count<56)
			hd->buf[hd->count++]=0;/*pad*/
	}
	else{/*needoneextrablock*/
		hd->buf[hd->count++]=0x80;/*padcharacter*/
		while(hd->count<64)
			hd->buf[hd->count++]=0;
		sha1_write(hd,NULL,0);/*flush*/;
		memset(hd->buf,0,56);/*fillnextblockwithzeroes*/
	}
	/*appendthe64bitcount*/
	hd->buf[56]=msb>>24;
	hd->buf[57]=msb>>16;
	hd->buf[58]=msb>>8;
	hd->buf[59]=msb	;
	hd->buf[60]=lsb>>24;
	hd->buf[61]=lsb>>16;
	hd->buf[62]=lsb>>8;
	hd->buf[63]=lsb	;
	transform(hd,hd->buf);

	p=hd->buf;
#ifdefBIG_ENDIAN_HOST
#defineX(a)do{*(u32*)p=hd->h##a;p+=4;}while(0)
#else/*littleendian*/
#defineX(a)do{*p++=hd->h##a>>24;*p++=hd->h##a>>16;	
	*p++=hd->h##a>>8;*p++=hd->h##a;}while(0)
#endif
	X(0);
	X(1);
	X(2);
	X(3);
	X(4);
#undefX
}

5. C语言中的hash函数

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码里，叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。Hash算法在信息安全方面的应用主要体现在以下的3个方面：文件校验、数字签名、鉴权协议
程程序实现
// 说明：Hash函数（即散列函数）在程序设计中的应用目标 ------ 把一个对象通过某种转换机制对应到一个
//size_t类型（即unsigned long）的整型值。
// 而应用Hash函数的领域主要是 hash表（应用非常广）、密码等领域。
// 实现说明：
// ⑴、这里使用了函数对象以及泛型技术，使得对所有类型的对象（关键字）都适用。
// ⑵、常用类型有对应的偏特化，比如string、char*、各种整形等。
// ⑶、版本可扩展，如果你对某种类型有特殊的需要，可以在后面实现专门化。
// ⑷、以下实现一般放在头文件中，任何包含它的都可使用hash函数对象。
//------------------------------------实现------------------------------------------------
#include <string>
using std::string;
inlinesize_thash_str(const char* s)
{
unsigned long res = 0;
for (; *s; ++s)
res = 5 * res + *s;
returnsize_t(res);
}
template <class Key>
struct hash
{
size_toperator () (const Key& k) const;
};
// 一般的对象，比如：vector< queue<string> >；的对象，需要强制转化
template < class Key >
size_thash<Key>::operator () (const Key& k) const
{
size_tres = 0;
size_tlen = sizeof(Key);
const char* p = reinterpret_cast<const char*>(&k);
while (len--)
{
res = (res<<1）^*p++;
}
return res;
}
// 偏特化
template<>
size_thash< string >::operator () (const string& str) const
{
return hash_str(str.c_str());
}
typedef char* PChar;
template<>
size_thash<PChar>::operator () (const PChar& s) const
{
return hash_str(s);
}
typedef const char* PCChar;
template<>
size_thash<PCChar>::operator () (const PCChar& s) const
{
return hash_str(s);
}
template<> size_t hash<char>::operator () (const char& x) const { return x; }
template<> size_t hash<unsigned char>::operator () (const unsigned char& x) const { return x; }
template<> size_t hash<signed char>::operator () (const signed char& x) const { return x; }
template<> size_t hash<short>::operator () (const short& x) const { return x; }
template<> size_t hash<unsigned short>::operator () (const unsigned short& x) const { return x; }
template<> size_t hash<int>::operator () (const int& x) const { return x; }
template<> size_t hash<unsigned int>::operator () (const unsigned int& x) const { return x; }
template<> size_t hash<long>::operator () (const long& x) const { return x; }
template<> size_t hash<unsigned long>::operator () (const unsigned long& x) const { return x; }
// 使用说明：
//
// ⑴、使用时首先由于是泛型，所以要加上关键字类型。
//
// ⑵、其次要有一个函数对象，可以临时、局部、全局的，只要在作用域就可以。
//
// ⑶、应用函数对象作用于对应类型的对象。
//----------------------- hash函数使用举例 -------------------------
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
vector<string> vstr⑵；
vstr[0] = "sjw";
vstr[1] = "suninf";
hash<string> strhash; // 局部函数对象
cout << " Hash value: " << strhash(vstr[0]) << endl;
cout << " Hash value: " << strhash(vstr[1]) << endl;
cout << " Hash value: " << hash< vector<string> >() (vstr) << endl;
cout << " Hash value: " << hash<int>() （100） << endl; // hash<int>() 临时函数对象
return 0;
}

6. C语言 数据结构中解决冲突的方法是什么

可以参考如下方法：

1 基本原理
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接寻址"与"解决冲突"是哈希表的两大特点。

2 函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a) 除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
b) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。

3 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。

4 支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ，A 为存储的数组。
初始化比较容易，例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procere makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
//素存储的单元，要么表已经满了
locate:=(orig+i) mod S;
end;
插入元素
procere insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误，当然这是可以避免的
end;
查找元素是否已经在表中
procere member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
这些就是建立在哈希表上的常用基本运算。

4.1 应用的简单原则
什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问："某个元素是否在已知集合中？"，也就是需要高效的数据存储和查找，则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意的是什么呢？
哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标就是尽力避免冲突。前面提到，在使用"除余法"的时候，h(k)=k mod p ，p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢？假设 p=1000 ，则哈希函数分类的标准实际上就变成了按照末三位数分类，这样最多1000类，冲突会很多。一般地说，如果 p 的约数越多，那么冲突的几率就越大。
简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 则有 q mod p= q - p* [q div p] =q - p*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0，b] 的正整数。也就是说， [b div a] 的值只有 b+1 种可能，而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样，虽然mod 运算之后的余数仍然在 [0，p-1] 内，但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住"素数是我们的得力助手"。
另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。
综上所述，设计一个好的哈希函数是很关键的。而"好"的标准，就是较低的冲突率和易于实现。

7. C语言怎么实现有重复元素的全排列

整体思路就是利用回溯的思想，也可认为是深度优先搜索

从字符串第一位idx=0开始，每次递归都从s[idx]之后选择一个字符与s[idx]交换

因为可能有重复字符，可使用哈希数组标记当前循环每个字符是否被选择

因为字符范围不超过ASCII码，所以使用128空间的数组足够用来标记了

选择好当前字符s[i]并与s[idx]交换之后，递归调用继续排列下一位s[idx+1]

注意这里要进行回溯，即不选s[i]而选择之后的某个字符交换到s[idx]

所以要将之前的s[i]与s[idx]交换过来，恢复原状，才能循环判断下一个选择

具体代码截图如下：

结果正确，望采纳~

附源码：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAXN 1000000 // 排列总数可能很多

int num = 0; // 记录排列总数

char *res[MAXN] = {NULL}; // 指针数组保存排列结果

void swap(char *x, char *y) { // 交换两个字符变量的内容

char ch = *x;

*x = *y;

*y = ch;

}

void perm(char *s, int n, int idx) { // 回溯产生字符串全排列

if (idx == n) { // 已排列到字符串结尾

res[num] = (char *)malloc(sizeof(char) * (n + 1));

//printf("%s ", s); // 输出当前排列

strcpy(res[num], s); // 保存当前排列

num++; // 排列总数加1

return;

}

int i, hash[128] = {0}; // 哈希数组，标记每个字符是否被选择

for (i = idx; i < n; i++) {

if (hash[s[i]] == 1)

continue; // 跳过已被标记过的重复字符

hash[s[i]] = 1; // 选过的话在数组中标记为1

swap(&s[idx], &s[i]); // 选择s[i]交换到s[idx]

perm(s, n, idx + 1); // 递归，继续s[idx+1]的选择

swap(&s[idx], &s[i]); // 回溯，当前不选择s[i]，而选择其他字符

}

}

int main() {

int n, i;

scanf("%d", &n);

char *s = (char *)malloc(sizeof(char) * (n + 1));

scanf("%s", s);

perm(s, n, 0);

printf("一共有%d种排列: ", num); // 输出排列总数

for (i = 0; i < num; i++) { // 输出所有排列

printf("%s ", res[i]);

free(res[i]); // 释放内存空间

}

free(s);

return 0;

}

8. C语言编程，求字符串的hash值（散列值）

#include<stdio.h>

intmain(){
chars[256];
	char*p;
	unsignedlonglonginth=0;
	
	scanf("%s",s);
	for(p=s;*p;p++){
		h=h*31+*p;
	}
	printf("%llu",h);
}