
- 外文名
- Hash
- 音 译
- 哈希
- 特 点
- 很难找到逆向规律
- 释 义
- 把任意长度的输入通过散列算法变换成固定长度的输出
- 中文名
- 散列、杂凑
- 属 性
- 压缩映射
-
Hash
2011-08-18 18:00:27public class HashAlgorithms { /**//** * 加法hash * @param key 字符串 * @param prime 一个质数 * @return hash结果 */ public static int additiveHapublic class HashAlgorithms
{
/**//**
* 加法hash
* @param key 字符串
* @param prime 一个质数
* @return hash结果
*/
public static int additiveHash(String key, int prime)
{
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % prime);
}/**//**
* 旋转hash
* @param key 输入字符串
* @param prime 质数
* @return hash值
*/
public static int rotatingHash(String key, int prime)
{
int hash, i;
for (hash=key.length(), i=0; i<key.length(); ++i)
hash = (hash<<4)^(hash>>28)^key.charAt(i);
return (hash % prime);
// return (hash ^ (hash>>10) ^ (hash>>20));
}// 替代:
// 使用:hash = (hash ^ (hash>>10) ^ (hash>>20)) & mask;
// 替代:hash %= prime;
/**//**
* MASK值,随便找一个值,最好是质数
*/
static int M_MASK = 0x8765fed1;
/**//**
* 一次一个hash
* @param key 输入字符串
* @return 输出hash值
*/
public static int oneByOneHash(String key)
{
int hash, i;
for (hash=0, i=0; i<key.length(); ++i)
{
hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
// return (hash & M_MASK);
return hash;
}/**//**
* Bernstein's hash
* @param key 输入字节数组
* @param level 初始hash常量
* @return 结果hash
*/
public static int bernstein(String key)
{
int hash = 0;
int i;
for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);
return hash;
}//
/**/ Pearson's Hash
// char pearson(char[]key, ub4 len, char tab[256])
// {
// char hash;
// ub4 i;
// for (hash=len, i=0; i<len; ++i)
// hash=tab[hash^key[i]];
// return (hash);
// }/**/ CRC Hashing,计算crc,具体代码见其他
// ub4 crc(char *key, ub4 len, ub4 mask, ub4 tab[256])
// {
// ub4 hash, i;
// for (hash=len, i=0; i<len; ++i)
// hash = (hash >> 8) ^ tab[(hash & 0xff) ^ key[i]];
// return (hash & mask);
// }/**//**
* Universal Hashing
*/
public static int universal(char[]key, int mask, int[] tab)
{
int hash = key.length, i, len = key.length;
for (i=0; i<(len<<3); i+=8)
{
char k = key[i>>3];
if ((k&0x01) == 0) hash ^= tab[i+0];
if ((k&0x02) == 0) hash ^= tab[i+1];
if ((k&0x04) == 0) hash ^= tab[i+2];
if ((k&0x08) == 0) hash ^= tab[i+3];
if ((k&0x10) == 0) hash ^= tab[i+4];
if ((k&0x20) == 0) hash ^= tab[i+5];
if ((k&0x40) == 0) hash ^= tab[i+6];
if ((k&0x80) == 0) hash ^= tab[i+7];
}
return (hash & mask);
}/**//**
* Zobrist Hashing
*/
public static int zobrist( char[] key,int mask, int[][] tab)
{
int hash, i;
for (hash=key.length, i=0; i<key.length; ++i)
hash ^= tab[i][key[i]];
return (hash & mask);
}// LOOKUP3
// 见Bob Jenkins(3).c文件// 32位FNV算法
static int M_SHIFT = 0;
/**//**
* 32位的FNV算法
* @param data 数组
* @return int值
*/
public static int FNVHash(byte[] data)
{
int hash = (int)2166136261L;
for(byte b : data)
hash = (hash * 16777619) ^ b;
if (M_SHIFT == 0)
return hash;
return (hash ^ (hash >> M_SHIFT)) & M_MASK;
}
/**//**
* 改进的32位FNV算法1
* @param data 数组
* @return int值
*/
public static int FNVHash1(byte[] data)
{
final int p = 16777619;
int hash = (int)2166136261L;
for(byte b:data)
hash = (hash ^ b) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
/**//**
* 改进的32位FNV算法1
* @param data 字符串
* @return int值
*/
public static int FNVHash1(String data)
{
final int p = 16777619;
int hash = (int)2166136261L;
for(int i=0;i<data.length();i++)
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}/**//**
* Thomas Wang的算法,整数hash
*/
public static int intHash(int key)
{
key += ~(key << 15);
key ^= (key >>> 10);
key += (key << 3);
key ^= (key >>> 6);
key += ~(key << 11);
key ^= (key >>> 16);
return key;
}
/**//**
* RS算法hash
* @param str 字符串
*/
public static int RSHash(String str)
{
int b = 378551;
int a = 63689;
int hash = 0;for(int i = 0; i < str.length(); i++)
{
hash = hash * a + str.charAt(i);
a = a * b;
}return (hash & 0x7FFFFFFF);
}
/**//* End Of RS Hash Function *//**//**
* JS算法
*/
public static int JSHash(String str)
{
int hash = 1315423911;for(int i = 0; i < str.length(); i++)
{
hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
}return (hash & 0x7FFFFFFF);
}
/**//* End Of JS Hash Function *//**//**
* PJW算法
*/
public static int PJWHash(String str)
{
int BitsInUnsignedInt = 32;
int ThreeQuarters = (BitsInUnsignedInt * 3) / 4;
int OneEighth = BitsInUnsignedInt / 8;
int HighBits = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth);
int hash = 0;
int test = 0;for(int i = 0; i < str.length();i++)
{
hash = (hash << OneEighth) + str.charAt(i);if((test = hash & HighBits) != 0)
{
hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}return (hash & 0x7FFFFFFF);
}
/**//* End Of P. J. Weinberger Hash Function *//**//**
* ELF算法
*/
public static int ELFHash(String str)
{
int hash = 0;
int x = 0;for(int i = 0; i < str.length(); i++)
{
hash = (hash << 4) + str.charAt(i);
if((x = (int)(hash & 0xF0000000L)) != 0)
{
hash ^= (x >> 24);
hash &= ~x;
}
}return (hash & 0x7FFFFFFF);
}
/**//* End Of ELF Hash Function *//**//**
* BKDR算法
*/
public static int BKDRHash(String str)
{
int seed = 131; // 31 131 1313 13131 131313 etc..
int hash = 0;for(int i = 0; i < str.length(); i++)
{
hash = (hash * seed) + str.charAt(i);
}return (hash & 0x7FFFFFFF);
}
/**//* End Of BKDR Hash Function *//**//**
* SDBM算法
*/
public static int SDBMHash(String str)
{
int hash = 0;for(int i = 0; i < str.length(); i++)
{
hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
}return (hash & 0x7FFFFFFF);
}
/**//* End Of SDBM Hash Function *//**//**
* DJB算法
*/
public static int DJBHash(String str)
{
int hash = 5381;for(int i = 0; i < str.length(); i++)
{
hash = ((hash << 5) + hash) + str.charAt(i);
}return (hash & 0x7FFFFFFF);
}
/**//* End Of DJB Hash Function *//**//**
* DEK算法
*/
public static int DEKHash(String str)
{
int hash = str.length();for(int i = 0; i < str.length(); i++)
{
hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
}return (hash & 0x7FFFFFFF);
}
/**//* End Of DEK Hash Function *//**//**
* AP算法
*/
public static int APHash(String str)
{
int hash = 0;for(int i = 0; i < str.length(); i++)
{
hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ str.charAt(i) ^ (hash >> 3)) :
(~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
}// return (hash & 0x7FFFFFFF);
return hash;
}
/**//* End Of AP Hash Function */
/**//**
* JAVA自己带的算法
*/
public static int java(String str)
{
int h = 0;
int off = 0;
int len = str.length();
for (int i = 0; i < len; i++)
{
h = 31 * h + str.charAt(off++);
}
return h;
}
/**//**
* 混合hash算法,输出64位的值
*/
public static long mixHash(String str)
{
long hash = str.hashCode();
hash <<= 32;
hash |= FNVHash1(str);
return hash;
}
}
-
数据结构 Hash表(哈希表)
2018-05-20 01:23:34什么是Hash表 要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么...参考链接:数据结构(严蔚敏)
一、什么是Hash表
要想知道什么是哈希表,那得先了解哈希函数
哈希函数对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种函数H,根据这个函数和查找关键字key,可以直接确定查找值所在位置,而不需要一个个比较。这样就**“预先知道”**key所在的位置,直接找到数据,提升效率。
即
地址index=H(key)
说白了,hash函数就是根据key计算出应该存储地址的位置,而哈希表是基于哈希函数建立的一种查找表二、哈希函数的构造方法
根据前人经验,统计出如下几种常用hash函数的构造方法:
直接定制法
哈希函数为关键字的线性函数如 H(key)=a*key+b
这种构造方法比较简便,均匀,但是有很大限制,仅限于地址大小=关键字集合的情况
使用举例:
假设需要统计中国人口的年龄分布,以10为最小单元。今年是2018年,那么10岁以内的分布在2008-2018,20岁以内的分布在1998-2008……假设2018代表2018-2008直接的数据,那么关键字应该是2018,2008,1998……
那么可以构造哈希函数H(key)=(2018-key)/10=201-key/10
那么hash表建立如下index key 年龄 人数(假设数据) 0 2018 0-10 200W 1 2008 10-20 250W 2 1998 20-30 253W 3 1988 30-40 300W …… 数字分析法
假设关键字集合中的每个关键字key都是由s位数字组成(),分析key中的全体数据,并从中提取分布均匀的若干位或他们的组合构成全体使用举例
我们知道身份证号是有规律的,现在我们要存储一个班级学生的身份证号码,假设这个班级的学生都出生在同一个地区,同一年,那么他们的身份证的前面数位都是相同的,那么我们可以截取后面不同的几位存储,假设有5位不同,那么就用这五位代表地址。
H(key)=key%100000
此种方法通常用于数字位数较长的情况,必须数字存在一定规律,其必须知道数字的分布情况,比如上面的例子,我们事先知道这个班级的学生出生在同一年,同一个地区。
平方取中法
如果关键字的每一位都有某些数字重复出现频率很高的现象,可以先求关键字的平方值,通过平方扩大差异,而后取中间数位作为最终存储地址。
使用举例
比如key=1234 1234^2=1522756 取227作hash地址
比如key=4321 4321^2=18671041 取671作hash地址
这种方法适合事先不知道数据并且数据长度较小的情况
折叠法
如果数字的位数很多,可以将数字分割为几个部分,取他们的叠加和作为hash地址
使用举例
比如key=123 456 789
我们可以存储在61524,取末三位,存在524的位置
该方法适用于数字位数较多且事先不知道数据分布的情况
除留余数法用的较多
H(key)=key MOD p (p<=m m为表长)
很明显,如何选取p是个关键问题。使用举例
比如我们存储3 6 9,那么p就不能取3
因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
p应为不大于m的质数或是不含20以下的质因子的合数,这样可以减少地址的重复(冲突)比如key = 7,39,18,24,33,21时取表长m为9 p为7 那么存储如下
index 0 1 2 3 4 5 6 7 8 key 7 21(冲突后移) 24 4 18(冲突后移) 33冲突后移) hash函数设计的考虑因素
1.计算散列地址所需要的时间(即hash函数本身不要太复杂)
2.关键字的长度
3.表长
4.关键字分布是否均匀,是否有规律可循
5.设计的hash函数在满足以上条件的情况下尽量减少冲突三、哈希冲突
即不同key值产生相同的地址,H(key1)=H(key2)
比如我们上面说的存储3 6 9,p取3是
3 MOD 3 == 6 MOD 3 == 9 MOD 3
此时3 6 9都发生了hash冲突哈希冲突的解决方案
不管hash函数设计的如何巧妙,总会有特殊的key导致hash冲突,特别是对动态查找表来说。
hash函数解决冲突的方法有以下几个常用的方法
1.开放定制法
2.链地址法
3.公共溢出区法
建立一个特殊存储空间,专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
4.再散列法
准备若干个hash函数,如果使用第一个hash函数发生了冲突,就使用第二个hash函数,第二个也冲突,使用第三个……
重点了解一下开放定制法和链地址法开放定制法
首先有一个H(key)的哈希函数
如果H(key1)=H(keyi)
那么keyi存储位置m为表长
有三种取法
1)线性探测再散列
2)平方探测再散列
……
3)随机探测在散列(双探测再散列)
是一组伪随机数列
注意
增量di应该具有以下特点(完备性):产生的Hi(地址)均不相同,且所产生的s(m-1)个Hi能覆盖hash表中的所有地址- 平方探测时表长m必须为4j+3的质数(平方探测表长有限制)
- 随机探测时m和di没有公因子(随机探测di有限制)
三种开放定址法解决冲突方案的例子
废话不多说,上例子就明白了
有一组数据
19 01 23 14 55 68 11 86 37要存储在表长11的数组中,其中H(key)=key MOD 11
那么按照上面三种解决冲突的方法,存储过程如下:
(表格解释:从前向后插入数据,如果插入位置已经占用,发生冲突,冲突的另起一行,计算地址,直到地址可用,后面冲突的继续向下另起一行。最终结果取最上面的数据(因为是最“占座”的数据))
线性探测再散列
我们取di=1,即冲突后存储在冲突后一个位置,如果仍然冲突继续向后index 0 1 2 3 4 5 6 7 8 9 10 key 55 1 14 19 86 23冲突 23 68冲突 68冲突 68 11冲突 11冲突 11冲突 11冲突 11冲突 11 37冲突 37冲突 37 最终存储结果 55 1 23 14 68 11 37 19 86 index 0 1 2 3 4 5 6 7 8 9 10 key 55 1 14 37 19 86 23冲突 H(23)+1 H(68)-1冲突 68冲突 H(68)+1冲突 H(68)+4 11冲突 H(11)+1冲突 H(11)-1 最终存储结果 55 1 23 14 37 68 19 86 11 index 0 1 2 3 4 5 6 7 8 9 10 key 55 1 68 14 19 86 23冲突 H(23)+3+1 11冲突 H(11)+1+1冲突 H(11)+1+1+1+1 (H(37)+8)模11冲突 37冲突 (H(37)+8+8+8)模11 (H(37)+8+8)模11冲突 最终存储结果 55 1 68 14 23 11 37 19 86 链地址法
产生hash冲突后在存储数据后面加一个指针,指向后面冲突的数据
上面的例子,用链地址法则是下面这样:
四、hash表的查找查找过程和造表过程一致,假设采用开放定址法处理冲突,则查找过程为:
对于给定的key,计算hash地址index = H(key)
如果数组arr【index】的值为空 则查找不成功
如果数组arr【index】== key 则查找成功
否则 使用冲突解决方法求下一个地址,直到arr【index】== key或者 arr【index】==nullhash表的查找效率
决定hash表查找的ASL因素:
1)选用的hash函数
2)选用的处理冲突的方法
3)hash表的饱和度,装载因子 α=n/m(n表示实际装载数据长度 m为表长)
一般情况,假设hash函数是均匀的,则在讨论ASL时可以不考虑它的因素
hash表的ASL是处理冲突方法和装载因子的函数
前人已经证明,查找成功时如下结果:
可以看到无论哪个函数,装载因子越大,平均查找长度越大,那么装载因子α越小越好?也不是,就像100的表长只存一个数据,α是小了,但是空间利用率不高啊,这里就是时间空间的取舍问题了。通常情况下,认为α=0.75是时间空间综合利用效率最高的情况。上面的这个表可是特别有用的。假设我现在有10个数据,想使用链地址法解决冲突,并要求平均查找长度<2
那么有1+α/2 <2
α<2
即 n/m<2 (n=10)
m>10/2
m>5 即采用链地址法,使得平均查找长度< 2 那么m>5之前我的博客讨论过各种树的平均查找长度,他们都是基于存储数据n的函数,而hash表不同,他是基于装载因子的函数,也就是说,当数据n增加时,我可以通过增加表长m,以维持装载因子不变,确保ASL不变。
那么hash表的构造应该是这样的:
五、hash表的删除首先链地址法是可以直接删除元素的,但是开放定址法是不行的,拿前面的双探测再散列来说,假如我们删除了元素1,将其位置置空,那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据,比如-1
-
findmyhash--HASH破解工具
2012-07-23 17:29:24findmyhash是一个批量查询国外开放的HASH库来获取查询解密的小工具,是除去CMD5外有一选择(穷人啊 只能用免费的了) -
Hash详解
2018-07-23 10:00:22Hash(哈希) Hash :散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()...Hash(哈希)
Hash :散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()即请求对象的哈希值。
Hash的优点
先分类再查找,通过计算缩小范围,加快查找速度。
例:
集合:{13,19,25,27,17}
若是采用数组或链表结构:
访问其中的一个元素(如18),需要遍历整个集合的元素,时间复杂度为O(n).
而采用哈希表时:
假如散列函数为H[key] = key % 5;则集合元素对应的hash值分别为{3,4,0,2,2}。 访问元素(18)只需要在Hash值为2的集合中寻找即可. 如果访问没有哈希冲突的元素,例如访问(25),可以直接访问哈希值为(0)的值。 故hash时间复杂度最差才为O(n),最优情况下只需要O(1);
由上面的例子,我们可以想象,如果由大量的数据,采用数组或是链表存储时,访问需要遍历,耗费的时间非常多,而Hash表通过哈希计算,可以直接定位到数据所在位置(发生哈希冲突时,哈希值相同,可以定位到较小范围)大大加快了 查找的速度,节省了大量时间。
散列函数(Hash函数)
Hash通过Hash函数,将Key值映射为地址,Address = F[key];
常见的几种Hash函数:直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法
-
直接定址法:取Key或者Key的某个线性函数值为散列地址。Hash(k) = k,或者Hash(k) = a*k + b, (a\b均为常数).
如下例所示:a = 1/100,b = -5.
Key Hash(Key) 1005200 10047 3009800 30093 1506400 15059 7604300 76038 -
数字分析法:需要知道Key的集合,并且Key的位数比地址位数多,选择Key数字分布均匀的位。如下:
Hash(Key) 取六位:
列数 : 1 (2) 3 (4) 5 (6) (7) 8 (9) 10 11 12 (13)
key1: 5 2 4 2 7 5 8 5 3 6 5 1 3
key2: 5 4 4 8 7 7 7 5 4 8 9 5 1
key3: 3 1 5 3 7 8 5 4 6 3 5 5 2
key4: 5 3 6 4 3 2 5 4 5 3 2 6 4
其中(2、4、6、7、9、13) 这6列数字无重复,分布较均匀,取此六列作为Hash(Key)的值。
Hash(Key1) :225833
Hash(Key2):487741
Hash(Key3):138562
Hash(Key4):342554
-
平方取中法:取Key平方值的中间几位作为Hash地址。因为在设置散列函数时不一定知道所有关键字,选取哪几位不确定。一个数的平方的中间几位和数本身的每一位都有关,这样可以使随机分布的Key,得到的散列地址也是随机分布的 。如下:
Key Key值平方 Hash地址(5位) 111112113 12345901655324769 01655 010111101 00102234363432201 34363 210222134 44193345623513956 45623 -
折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。 当Key的位数较多的时候数字分布均匀适合采用这种方案.
具体的叠加方法有两种,移位法和折叠法:
例子:若Key为下列数串,地址位数为7,两种方法的Hash(key)分别如下:
Key:7982374 | 1861215 | 9892154 | 56923
移位折叠法: 折叠折叠法: 第一段 7982374 d1-dr 7982374 d1-dr 第二段 1861215 d(r+1)-d(2r) 5121681 d(2r)-d(r+1) 第三段 9892154 d(2r+1)-d(3r) 4512989 d(3r)-d(2r+1) 第四段 + 56923 d(3r+1)-d(end) + 32965 d(end)-d(3r+1) 结果: 19792666 17650009 Hash(key): 9792666 7650009 -
随机数法:伪随机探测再散列
具体实现:建立一个伪随机数发生器,Hash(Key) = random(Key). 以此伪随机数作为哈希地址。
-
除留余数法:取关键字被某个除数 p 求余,得到的作为散列地址。
即 H(Key) = Key % p;
例子如下:
Key P Hash(Key) (4位) 11076302 1000 6302 13635279 1000 5279 41076553 1000 6553 76553027 1000 3027
以上就是6种构造哈希函数的方法,选择时要本着尽量减少产生冲突的原则,根据Key值的位数,分布情况,范围大小做出更优的选择。
哈希冲突
不管选用何种散列函数,不可避免的都会产生不同Key值对应同一个Hash地址的情况,这种情况叫做哈希冲突。
哈希冲突的处理
当冲突发生时,我们需要想办法解决冲突,一般常用的方法有:开放定址法、单独链表法、双散列法、再散列法以及建业公共溢出取等方法。
-
开放定址法:
当冲突发生时,探测其他位置是否有空地址 (按一定的增量逐个的寻找空的地址),将数据存入。根据探测时使用的增量的取法,分为:线性探测、平方探测、伪随机探测等。
新的Hash地址函数为 Hash_new (Key) = (Hash(Key) + d i) mod m;i = 1,2...k (k<= m-1).m表示集合的元素数,i表示已经探测的次数。
-
线性探测(Linear Probing)
d i = a * i + b; a\b为常数。
相当于逐个探测地址列表,直到找到一个空置的,将数据放入。
-
平方探测(Quadratic Probing)
d i = a * i 2 (i <= m/2) m是Key集合的总数。a是常数。
探测间隔 i2 个单元的位置是否为空,如果为空,将地址存放进去。
-
伪随机探测
d i = random(Key);
探测间隔为一个伪随机数。
例子:
Key集合为(15,36,25,46,75),采用除留余数法,模10 ,冲突时采用线性探测法d i = i;
如图,15和36放入时无冲突发生,分别对应地址 5 和6 。
但是当25放入时,Hash(25) = 25%10 = 5,和Key= 15发生冲突,则令d 1 = 1,Hash(25) = (25 + 1) %10 = 6.
此时已然与Key = 36发生冲突,令d 2 = 2,Hash(25) = (25+2) %10 = 7,无冲突,放入。
此后46,75也发生冲突,解决方法同上。
-
-
链表法
将散列到同一个位置的所有元素依次存储在单链表中,或者也有存储在栈中。具体实现根据实际情况决定这些元素的数据存储结构。
如下图所示:
首页Hash地址为 i 的结点,均插入到以 T[i] 为头指针的单链表中。T 中各分量的初值均应为空指针。
在拉链法中,装填因子 α 可以大于 1,但一般均取 α ≤ 1。
装填因子(载荷因子)
散列表的载荷因子定义为:
α = 填入表中的元素个数 / 散列表的长度.
α 是散列表装满程度的标志因子。由于表长是定值,α 与“填入表中的元素个数”成正比,所以,α 越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之,α 越小,标明填入表中的元素越少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是载荷因子α 的函数,只是不同处理冲突的方法有不同的函数。
对于开放定址法,荷载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了荷载因子为0.75,超过此值将resize散列表。
-
-
hash和一致性hash
2019-07-25 09:19:45hash;简单的hash取余 优点: 计算简单,快速定位 缺点: 容错和扩展差,任何的增加机器或减少机器,都会伴随着重新set值 比如原来有五台机器做缓存,现在加一台,那么余5就变成余6,那么所有值都变了 操作不当的话...hash;简单的hash取余
优点:
计算简单,快速定位
缺点:
容错和扩展差,任何的增加机器或减少机器,都会伴随着重新set值
比如原来有五台机器做缓存,现在加一台,那么余5就变成余6,那么所有值都变了
操作不当的话短时间可能会造成缓存雪崩(一般只能成倍扩展)一致性hash:hash环
想象一个环,共有2^32-1 个节点,如果有五台机器缓存,那么就将这五台的ip分别hash后对2^32-1取余,得到的结果肯定在这个环上,我们叫这个结果为落在某一个节点上
顺时针数,每个节点到前一个节点直接的值,将属于这个节点。
举个例子:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针行走,第一台遇到的服务器就是其应该定位到的服务器。
优点:
增加机器和减少机器,对整体影响不大,尤其是机器特别多的情况下,影响更小
缺点:
如果几个ip计算出来的节点不均匀,可能会出现缓存倾斜,比如一个机器上的缓存特别多,另一个机器上的缓存特别少
但是,针对这种问题,有成熟的解决方案,例如用虚拟节点。
比如现在有两个机器a,b,那么基本上肯定会出现缓存倾斜,那么我们就做出几个虚拟节点,a_1,a_2,a_3,b_1,b_2,b_3
用这些再做计算,基本上就可以做到相对平均了,
一般生产过程中,一个机器都会做出32个虚拟节点,来防止缓存倾斜总结
简单常见用hash就行,重要场景考虑一致性hash
-
Java计算文件的hash值
2017-12-21 14:04:02当然是用比较文件hash值的方法,文件hash又叫文件签名,文件中哪怕一个bit位被改变了,文件hash就会不同。 比较常用的文件hash算法有MD5和SHA-1。 我用的是MD5算法,java中,计算MD5可以用MessageDigest这个类。 ... -
面试必备:什么是一致性Hash算法?
2018-03-14 00:00:00最近有小伙伴跑过来问什么是Hash一致性算法,说面试的时候被问到了,因为不了解,所以就没有回答上,问我有没有相应的学习资料推荐,当时上班,没时间回复,晚上回去了就忘了这件事,今天突然看到这个,加班为大家... -
c开源hash项目 uthash的用法总结
2019-07-14 21:22:48uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论... -
Redis系列之Hash
2020-05-28 12:02:11上节我们介绍了Redis的String类型,今天我们聊聊Hash类型,从上节的学习我们知道要存储一个值对应的属性特别方便,但是如果要像Mysql数据库那样存储一条数据就比较麻烦了,或者说像Java的Model一样存储一个实体对象... -
哈希hash
2017-05-07 17:19:51今天,我来介绍三种在工程中比较实用的Hash,它们分别是一致性哈希、局部敏感哈希和GeoHash。 1. 一致性哈希 一致性哈希算法是在1997年由麻省理工学院提出,设计的目标是为了解决因特网的... -
HASH值
2018-06-13 23:38:471.UUID也是hash值(1)获取UUID(2)获取UUID的长度和UUID(3)hash值一般是32位,uuid是hash的特例它给hash值做特定操作了所以是36位 -
Hash类型
2018-08-20 16:05:43Hash类型是String类型的field和value的映射表,或者说一个String集合。它特别适合存储对象,相比较而言,将一个对象类型存储在Hash类型里比存储在String类型里占用更少的内存空间,并方便存取整个对象。 (场景:... -
Hash学习
2017-07-01 15:53:27Hash表的出现主要是为了对内存中数据的快速、随机的访问。它主要有三个关键点:Hash表的大小、Hash函数、冲突的解决。(hash表的实现)1、Hash表的大小 Hash表的大小一般是定长的,如果太大,则浪费空间,如果太小... -
Hash取模与一致性Hash
2017-04-19 16:08:36直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如Java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。 但 -
Redis数据类型Hash
2020-10-27 21:44:19文章目录Hash类型介绍hash 类型数据的基本操作hash 类型数据操作的注意事项Hash和String类型的区别 有时候我们往往不是在缓存中存一个值,而是选择存一个对象,比如一个购物车消息,我们就需要使用到hash了 Hash类型... -
Hash冲突
2018-03-28 15:20:34hash : 翻译为“散列”,就是把任意长度的输入,通过散列算法,变成固定长度的输出,该输出就是散列值。 这种转换是一种压缩映射,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不... -
字符串Hash
2020-09-16 18:03:59字符串Hash原理,将字符串映射成一个值,是一个单向加密的过程。比较简单和常用的是进制哈希,我们把字符串看成是p进制数,然后使用unsigned long long的自然溢出(相当于是对264−12^{64}-1264−1取模),如果两个... -
HASH链表
2019-04-19 10:18:06一,HASH链表与逻辑读 oracle要从高速缓冲区中拿到5号文件1234号块buffer的信息,就需要使用到HASH算法。 Buffer Cache:高速缓冲区中包含多个buffer,每一个buffer就记录一个数据块对应的缓冲信息。 Buffer Header:... -
使用Jhash替换传统hash有效降低hash冲突提供查找效率
2017-03-22 21:20:16“`includeincludeinclude”jhash.h”//常规算法的黄金分隔define VOICE_HASH_GOLDEN_INTERER 0x9e370001//hash桶的大小为2的11次方,即2047+1define HASH_SIZE 2048//常用的黄金分隔的hash算法define VOICE_HASH_... -
Hash破解神器-hashcat详细使用
2018-08-23 14:53:35Hashcat系列软件是比较牛逼的密码破解软件,...其区别为Hashcat只支持cpu破解;oclHashcat和oclGausscrack则支持gpu加速。oclHashcat则分为AMD版和NIVDA版。 安装 wget https://hashcat.net/files_legacy/hashca... -
常见的hash算法及其原理
2018-07-30 15:47:13Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间... -
Hash Compared & ELFHash 详解
2016-05-08 09:11:26部分转载自here 常用HASH算法 代码 & 比较 常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。... 常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHas -
数据分布算法:hash+一致性hash+redis cluster的hash slot
2019-04-09 10:08:411.最原始的hash算法 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 ... -
Hash算法总结
2017-04-18 11:07:21Hash是什么,它的作用先举个例子。我们每个活在世上的人,为了能够参与各种社会活动,都需要一个用于识别自己的标志。也许你觉得名字或是身份证就足以代表你这个人,但是这种代表性非常脆弱,因为重名的人很多,... -
C开源hash代码uthash的用法总结
2019-08-16 00:08:13uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论... -
CRC32 Hash PK Murmur Hash
2017-01-07 07:03:22硬件指令实现的CRC32运算在多款主流CPU上性能超越Murmurhash,碰撞性能基本一致,多数场景可以使用CRC32硬件指令优化HASH算法提升性能 -
【01笔记】Hash和一致性Hash
2020-02-17 08:31:41利用Hash的方式对图片分库存储, hash(a.png)%4 缺点:当机器数量变化时,所有缓存失效,需重新缓存。 3、一致性Hash 对2^32取模,将整个哈希空间组成一个虚拟的环。 将机器IP或主机名为关键字进行哈希,并映射到... -
浅显理解 hashcode 和 hash 算法
2017-12-30 23:06:07HashMap 的 hash 算法的实现原理(为什么右移 16 位,为什么要使用 ^ 位异或) HashMap 为什么使用 & 与运算代替模运算? HashMap 的容量为什么建议是 2的幂次方? 我们自定义 HashMap 容量最好是多少? 前 -
uthash
2015-09-25 10:46:24在软件开发中,不可不免的会使用到hash表,hash表的优点这里就不说了,以下介绍一个hash表的C实现, uthash是用宏实现的,使用的时候非常方便,只用包含uthash.h即可。 Uthash的三个数据结构: 1. typedef struct... -
普通hash和一致性hash的区别
2019-05-10 15:42:48普通hash 定义 Hash函数:一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。 碰撞(冲突):如果两个关键字通过hash函数...