13518219792
#includestdio.h
创新互联主要从事网站制作、做网站、网页设计、企业做网站、公司建网站等业务。立足成都服务东台,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
int main(){
char s[256];
char *p;
unsigned long long int h = 0;
scanf("%s", s);
for(p=s; *p; p++){
h = h*31 + *p;
}
printf("%llu", h);
}
#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;}
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 queuestring ；的对象，需要强制转化
template class Key
size_thashKey::operator () (const Key k) const
{
size_tres = 0;
size_tlen = sizeof(Key);
const char* p = reinterpret_castconst char*(k);
while (len--)
{
res = (res1）^*p++;
}
return res;
}
// 偏特化
template
size_thash string ::operator () (const string str) const
{
return hash_str(str.c_str());
}
typedef char* PChar;
template
size_thashPChar::operator () (const PChar s) const
{
return hash_str(s);
}
typedef const char* PCChar;
template
size_thashPCChar::operator () (const PCChar s) const
{
return hash_str(s);
}
template size_t hashchar::operator () (const char x) const { return x; }
template size_t hashunsigned char::operator () (const unsigned char x) const { return x; }
template size_t hashsigned char::operator () (const signed char x) const { return x; }
template size_t hashshort::operator () (const short x) const { return x; }
template size_t hashunsigned short::operator () (const unsigned short x) const { return x; }
template size_t hashint::operator () (const int x) const { return x; }
template size_t hashunsigned int::operator () (const unsigned int x) const { return x; }
template size_t hashlong::operator () (const long x) const { return x; }
template size_t hashunsigned long::operator () (const unsigned long x) const { return x; }
// 使用说明：
//
// ⑴、使用时首先由于是泛型，所以要加上关键字类型。
//
// ⑵、其次要有一个函数对象，可以临时、局部、全局的，只要在作用域就可以。
//
// ⑶、应用函数对象作用于对应类型的对象。
//----------------------- hash函数使用举例 -------------------------
#include iostream
#include vector
#include string
using namespace std;
int main()
{
vectorstring vstr⑵；
vstr[0] = "sjw";
vstr[1] = "suninf";
hashstring strhash; // 局部函数对象
cout " Hash value: " strhash(vstr[0]) endl;
cout " Hash value: " strhash(vstr[1]) endl;
cout " Hash value: " hash vectorstring () (vstr) endl;
cout " Hash value: " hashint() （100） endl; // hashint() 临时函数对象
return 0;
}
有现成的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
}
/#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;
}
#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,
