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);
}