c语言中的hash函数,c语言hash用法

c语言hash函数有几种

#include stdio.h#include stdlib.h//这里我自己设计一个hash算法来快速查找一堆数字中相等的数字，这也许是最接近原理的算法了//一个整数整除27后的来作为hash函数//定义一个保存实际数据的结构体节点struct data_node{    int num;    int count;    struct data_node *next;};//定义一个结构体时hash表的一部分typedef struct{    int key; //余数    struct data_node *p; //链表的头指针} hash_node;#define HASH_SIZE 27int do_hash(int num) //hash表来求余数，这样就可以了{    return num%HASH_SIZE;}//初始化//添加数字//更新数字//删除数字//查找数字hash_node HashTable[HASH_SIZE]; //这里申明一个hashtable的数组//初始化函数，需要做的事将key复制为null，将p指针指向null,返回一个头指针来指向这个hashtablevoid InitHashTable(hash_node *HashTable)

创新互联专业为企业提供石狮网站建设、石狮做网站、石狮网站设计、石狮网站制作等企业网站建设、网页设计与制作、石狮企业网站模板建站服务，十年石狮做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。

{    //进行参数的校验    for(int i=0;iHASH_SIZE;i++)

{

HashTable[i].key = 0;        HashTable[i].p =NULL;    }

}//保存到这个链表中//如果这个链表是空的话，就作为头指针，如果这个链表不为空，则添加到吧数字添加到末尾int savedata(struct data_node **head,int num)

{    struct data_node *tmp_p = *head;    struct data_node *p = (struct data_node *)malloc(sizeof(struct data_node));    if(p == NULL)        return 0;    if(*head == NULL)

{

*head = p;        p-count = 1;        p-num = num;        p-next = NULL;    }    else //如果不为空，则这个时候应该添加到链表末尾    {        while(tmp_p != NULL)//如果存在，则将这个节点的count加1就可以了        {            if(tmp_p-num == num)

{

free(p);                ++tmp_p-count ;                return 0;            }            if(tmp_p-next == NULL)                break;            tmp_p = tmp_p-next;        }

tmp_p-next = p;        p-count =1;        p-num = num;        p-next = NULL;    }    return 0;}//添加数字//将这个数字经过hash求出结果，然后再保存到相应的链表中//返回真或者假就可以了int add_hash(hash_node *HashTable,int num)

{    int mod = do_hash(num);    return savedata(HashTable[mod].p,num);}int main()

{    int num = 100;    hash_node *H = HashTable;    InitHashTable(H);    add_hash(H,num);    add_hash(H,num);    add_hash(H,3);    add_hash(H,1);    add_hash(H,4);    //在这里我们可以发现一个好的hash函数是多么的重要，如果hash函数不好造成很多冲突的话，效率并不会提高很多的，理想的情况是冲突几乎没有    //这也就是设计hash函数的精髓所在    return 0;}

C语言版数据结构哈希算法题：设m=16,HASH函数为H（key）=key mod 13,现采用再哈希法Hi=RHi(key）处理冲突

应该是这个意思：

第一次冲突就是散列的位置+1，这次发生冲突了就继续第二次

第二次用的是平方取中，55^2= 3025，当然第二次冲突的RH2就是02了，答案(2)

C语言哈希表

/#include "iostream.h"

#include iostream

#include "string.h"

#include "fstream"

#define NULL 0

unsigned int key;

unsigned int key2;

int *p;

struct node //建节点

{

char name[8],address[20];

char num[11];

node * next;

};

typedef node* pnode;

typedef node* mingzi;

node **phone;

node **nam;

node *a;

using namespace std; //使用名称空间

void hash(char num[11]) //哈希函数

{

int i = 3;

key=(int)num[2];

while(num[i]!=NULL)

{

key+=(int)num[i];

i++;

}

key=key%20;

}

void hash2(char name[8]) //哈希函数

{

int i = 1;

key2=(int)name[0];

while(name[i]!=NULL)

{

key2+=(int)name[i];

i++;

}

key2=key2%20;

}

node* input() //输入节点

{

node *temp;

temp = new node;

temp-next=NULL;

cout"输入姓名："endl;

cintemp-name;

cout"输入地址："endl;

cintemp-address;

cout"输入电话："endl;

cintemp-num;

return temp;

}

int apend() //添加节点

{

node *newphone;

node *newname;

newphone=input();

newname=newphone;

newphone-next=NULL;

newname-next=NULL;

hash(newphone-num);

hash2(newname-name);

newphone-next = phone[key]-next;

phone[key]-next=newphone;

newname-next = nam[key2]-next;

nam[key2]-next=newname;

return 0;

}

void create() //新建节点

{

int i;

phone=new pnode[20];

for(i=0;i20;i++)

{

phone[i]=new node;

phone[i]-next=NULL;

}

}

void create2() //新建节点

{

int i;

nam=new mingzi[20];

for(i=0;i20;i++)

{

nam[i]=new node;

nam[i]-next=NULL;

}

}

void list() //显示列表

{

int i;

node *p;

for(i=0;i20;i++)

{

p=phone[i]-next;

while(p)

{

coutp-name'_'p-address'_'p-numendl;

p=p-next;

}

}

}

void list2() //显示列表

{

int i;

node *p;

for(i=0;i20;i++)

{

p=nam[i]-next;

while(p)

{

coutp-name'_'p-address'_'p-numendl;

p=p-next;

}

}

}

void find(char num[11]) //查找用户信息

{

hash(num);

node *q=phone[key]-next;

while(q!= NULL)

{

if(strcmp(num,q-num)==0)

break;

q=q-next;

}

if(q)

coutq-name"_" q-address"_"q-numendl;

else cout"无此记录"endl;

}

void find2(char name[8]) //查找用户信息

{

hash2(name);

node *q=nam[key2]-next;

while(q!= NULL)

{

if(strcmp(name,q-name)==0)

break;

q=q-next;

}

if(q)

coutq-name"_" q-address"_"q-numendl;

else cout"无此记录"endl;

}

void save() //保存用户信息

{

int i;

node *p;

for(i=0;i20;i++)

{

p=phone[i]-next;

while(p)

{

fstream iiout("out.txt", ios::out);

iioutp-name"_"p-address"_"p-numendl;

p=p-next;

}

}

}

void menu() //菜单

{

cout"0.添加记录"endl;

cout"3.查找记录"endl;

cout"2.姓名散列"endl;

cout"4.号码散列"endl;

cout"5.清空记录"endl;

cout"6.保存记录"endl;

cout"7.退出系统"endl;

}

int main()

{

char num[11];

char name[8];

create();

create2() ;

int sel;

while(1)

{

menu();

cinsel;

if(sel==3)

{ cout"9号码查询，8姓名查询"endl;

int b;

cinb;

if(b==9)

{ cout"请输入电话号码:"endl;

cin num;

cout"输出查找的信息:"endl;

find(num);

}

else

{ cout"请输入姓名:"endl;

cin name;

cout"输出查找的信息:"endl;

find2(name);}

}

if(sel==2)

{ cout"姓名散列结果:"endl;

list2();

}

if(sel==0)

{ cout"请输入要添加的内容:"endl;

apend();

}

if(sel==4)

{ cout"号码散列结果:"endl;

list();

}

if(sel==5)

{ cout"列表已清空:"endl;

create();

create2();

}

if(sel==6)

{ cout"通信录已保存:"endl;

save();

}

if(sel==7) return 0;

}

return 0;

}

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,

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

1.选择合适的哈希函数H(key)=key%p(p为小于或等于哈希表长的最大质数)；

2.计算各个关键字的直接哈希函数值；

3.根据处理冲突的方法建立哈希表，并输出；

4.在哈希表中进行查找，输出查找的结果，以及所需和记录关键字比较的次数，并计算和输出在等概率情况下查找成功的平均查找长度。

#includestdlib.h

#includestdio.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/2flag;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;im;i++)

(*HASH)[i].key=NULL; /*初始化哈希为空表(以0表示空)*/

for(i=0;in;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!=0HASH[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 nm(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;im;i++)

printf("%5d",i);

printf("\n");

for(i=0;im;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;in;i++)

{

search(HASH,ST[i].key,m,time);

stime+=time;

}

printf("\nThe Average Search Length is %5.2f",(float)stime/n);

ch=getch();

}

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

有现成的SHA1算法函数

复制过来。

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

#include stdio.h

#include stdlib.h

#include string.h

#include assert.h

#include errno.h

#undef BIG_ENDIAN_HOST

typedef unsigned int u32;

/****************

* Rotate a 32 bit integer by n bytes

*/

#if defined(__GNUC__)  defined(__i386__)

static inline u32

rol( u32 x, int n)

{

__asm__("roll %%cl,%0"

:"=r" (x)

:"0" (x),"c" (n));

return x;

}

#else

#define rol(x,n) ( ((x)  (n)) | ((x)  (32-(n))) )

#endif

typedef struct {

u32  h0,h1,h2,h3,h4;

u32  nblocks;

unsigned char buf[64];

int  count;

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

}

/****************

* Transform the message X which consists of 16 32-bit-words

*/

static void

transform( SHA1_CONTEXT *hd, unsigned char *data )

{

u32 a,b,c,d,e,tm;

u32 x[16];

/* get values from the chaining vars */

a = hd-h0;

b = hd-h1;

c = hd-h2;

d = hd-h3;

e = hd-h4;

#ifdef BIG_ENDIAN_HOST

memcpy( x, data, 64 );

#else

{

int i;

unsigned char *p2;

for(i=0, p2=(unsigned char*)x; i  16; i++, p2 += 4 ) 

{

p2[3] = *data++;

p2[2] = *data++;

p2[1] = *data++;

p2[0] = *data++;

}

}

#endif

#define K1  0x5A827999L

#define K2  0x6ED9EBA1L

#define K3  0x8F1BBCDCL

#define K4  0xCA62C1D6L

#define F1(x,y,z)   ( z ^ ( x  ( y ^ z ) ) )

#define F2(x,y,z)   ( x ^ y ^ z )

#define F3(x,y,z)   ( ( x  y ) | ( z  ( x | y ) ) )

#define F4(x,y,z)   ( x ^ y ^ z )

#define M(i) ( tm =   x[i0x0f] ^ x[(i-14)0x0f] \

^ x[(i-8)0x0f] ^ x[(i-3)0x0f] \

, (x[i0x0f] = rol(tm,1)) )

#define R(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) );

/* Update chaining vars */

hd-h0 += a;

hd-h1 += b;

hd-h2 += c;

hd-h3 += d;

hd-h4 += e;

}

/* Update the message digest with the contents

* of INBUF with length INLEN.

*/

static void

sha1_write( SHA1_CONTEXT *hd, unsigned char *inbuf, size_t inlen)

{

if( hd-count == 64 ) { /* flush the buffer */

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++;

}

/* The routine final terminates the computation and

* returns the digest.

* The handle is prepared for a new cycle, but adding bytes to the

* handle will the destroy the returned buffer.

* Returns: 20 bytes representing the digest.

*/

static void

sha1_final(SHA1_CONTEXT *hd)

{

u32 t, msb, lsb;

unsigned char *p;

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

t = hd-nblocks;

/* multiply by 64 to make a byte count */

lsb = t  6;

msb = t  26;

/* add the count */

t = lsb;

if( (lsb += hd-count)  t )

msb++;

/* multiply by 8 to make a bit count */

t = lsb;

lsb = 3;

msb = 3;

msb |= t  29;

if( hd-count  56 ) { /* enough room */

hd-buf[hd-count++] = 0x80; /* pad */

while( hd-count  56 )

hd-buf[hd-count++] = 0;  /* pad */

}

else { /* need one extra block */

hd-buf[hd-count++] = 0x80; /* pad character */

while( hd-count  64 )

hd-buf[hd-count++] = 0;

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

memset(hd-buf, 0, 56 ); /* fill next block with zeroes */

}

/* append the 64 bit count */

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;

#ifdef BIG_ENDIAN_HOST

#define X(a) do { *(u32*)p = hd-h##a ; p += 4; } while(0)

#else /* little endian */

#define X(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);

#undef X

}