# 常见hash算法

hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),这样可以快速在数组等条件中里面存取数据.

```#define M  249997
#define M1 1000001
#define M2 0xF0000000

// RS Hash Function
unsigned int RSHash(char*str)
{
unsigned int b=378551 ;
unsigned int a=63689 ;
unsigned int hash=0 ;

while(*str)
{
hash=hash*a+(*str++);
a*=b ;
}

return(hash % M);
}

// JS Hash Function
unsigned int JSHash(char*str)
{
unsigned int hash=1315423911 ;

while(*str)
{
hash^=((hash<<5)+(*str++)+(hash>>2));
}

return(hash % M);
}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char*str)
{
unsigned int BitsInUnignedInt=(unsigned int)(sizeof(unsigned int)*8);
unsigned int ThreeQuarters=(unsigned int)((BitsInUnignedInt*3)/4);
unsigned int OneEighth=(unsigned int)(BitsInUnignedInt/8);
unsigned int HighBits=(unsigned int)(0xFFFFFFFF)<<(BitsInUnignedInt-OneEighth);
unsigned int hash=0 ;
unsigned int test=0 ;

while(*str)
{
hash=(hash<<OneEighth)+(*str++);
if((test=hash&HighBits)!=0)
{
hash=((hash^(test>>ThreeQuarters))&(~HighBits));
}
}

return(hash % M);
}

// ELF Hash Function
unsigned int ELFHash(char*str)
{
unsigned int hash=0 ;
unsigned int x=0 ;

while(*str)
{
hash=(hash<<4)+(*str++);
if((x=hash&0xF0000000L)!=0)
{
hash^=(x>>24);
hash&=~x ;
}
}

return(hash % M);
}

// BKDR Hash Function
unsigned int BKDRHash(char*str)
{
unsigned int seed=131 ;// 31 131 1313 13131 131313 etc..
unsigned int hash=0 ;

while(*str)
{
hash=hash*seed+(*str++);
}

return(hash % M);
}

// SDBM Hash Function
unsigned int SDBMHash(char*str)
{
unsigned int hash=0 ;

while(*str)
{
hash=(*str++)+(hash<<6)+(hash<<16)-hash ;
}

return(hash % M);
}

// DJB Hash Function
unsigned int DJBHash(char*str)
{
unsigned int hash=5381 ;

while(*str)
{
hash+=(hash<<5)+(*str++);
}

return(hash % M);
}

// AP Hash Function
unsigned int APHash(char*str)
{
unsigned int hash=0 ;
int i ;

for(i=0;*str;i++)
{
if((i&1)==0)
{
hash^=((hash<<7)^(*str++)^(hash>>3));
}
else
{
hash^=(~((hash<<11)^(*str++)^(hash>>5)));
}
}

return(hash % M);
}

```

0 条评论

• ### sed 使用正则表达式进行替换

echo "111(222)333" | sed 's/(\(.*\))\(.*\)/\2\2\2/'

• ### 使用消息中间件时，如何保证消息仅仅被消费一次？

原文链接：https://www.toutiao.com/i6803224493616529927/

• ### 使用splice实现高效的代理服务器

很多网络应用场景下， 当原设备与目标设备无法直接建立连接时，这时就需要一台代理服务器进行中转。代理服务器只需要将来自源设备的报文 原封不动的转发给目标设备，而并...

• ### 散列表（一）：散列表概念、 散列函数构造方法、 常见字符串哈希函数（测试冲突）

一、散列表基本概念 1、散列表(hash table) ，也叫哈希表，是根据关键码而直接进行访问的数据结构。也就是说，它通过把关键码映射到表中一个位置 来访问记...

• ### Java - 游戏内存外挂

什么是游戏外挂？ 试想场景，在玩游戏时，没有得到良好的游戏体验，加之玩游戏的这位又是偏激之人，此时心生愤怒，但通过自己的游戏技术，又无法得到发泄。所以很无奈，只...

• ### 每日一题C++版（合唱队）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化...

• ### UESTC 1584 Washi与Sonochi的约定【树状数组裸题+排序】

题目链接：UESTC 1584 Washi与Sonochi的约定 题意：在二维平面上，某个点的ranked被定义为x坐标不大于其x坐标，且y坐标不大于其y坐标的...

• ### codevs 1664 清凉冷水

1664 清凉冷水 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description      ...

• ### 01:数制转换

01:数制转换 总时间限制: 1000ms 内存限制: 65536kB描述 求任意两个不同进制非负整数的转换（2进制～16进制），所给整数在long所能表达...

• ### Android自定义View实现数独游戏

1.在整个横坐标和纵坐标的9个格子上只能填土1-9的数字且不重复 2.在当前3*3 的格子上填入1-9数字且不重复