字符串哈希算法
经典字符串Hash函数
工作中经常需要用大hash这个强有力的工具，hash表最核心的部分则在于怎么设计一个好的hash函数，以使数据更均匀地分布在若干个桶上。下面来介绍一下我现在用到的一个hash函数，我们来看代码：
unsigned chostcachehash::get_host_key(const string& host)
{
int result = 1;
unsigned i = 0;
for (i = 0; i result = 31 * result + host[i]; return abs(result); } inline unsigned getkey(unsigned key) { return (key % m_capacity); } m_capacity为hash桶的个数 对于一个字符串，我们首先调用get_host_key()来得到一个key，然后再用这个key调用getkey来得到他在hash桶里的位置。这个是我们在工作一直使用的hash函数，效果也还可以。今天忽然心血来潮，在网上搜了一下看还有没有更好的hash函数，被我发现了这篇文章，于是转过来看看。 php中出现的字符串hash函数 static unsigned long hashpjw(char *arkey，unsigned intnkeylength) { unsigned long h = 0，g; char *arend=arkey+nkeylength; while (arkey h = (h << 4) + *arkey++; if ((g = (h & 0xf0000000))) { h = h ^ (g >> 24); h = h ^ g; } } return h; } openssl中出现的字符串hash函数 unsigned long lh_strhash(char *str) { int i，l; unsigned long ret=0; unsigned short *s; if (str == null) return(0); l=(strlen(str)+1)/2; s=(unsigned short *)str; for (i=0; i %有点看不懂 ret^=(s[i]<<(i&0x0f)); return(ret); } */ /* the following hash seems to work very well on normal text strings * no collisions on /usr/dict/words and it distributes on %2^n quite * well，not as good as md5，but still good. */ unsigned long lh_strhash(const char *c) { unsigned long ret=0; long n; unsigned long v; int r; if ((c == null) || (*c == "{post.abstract}")) return(ret); /* unsigned char b[16]; md5(c，strlen(c)，b); return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24)); */ n=0x100; while (*c) { v=n|(*c); n+=0x100; r= (int)((v>>2)^v)&0x0f; ret=(ret<>(32-r)); ret&=0xffffffffl; ret^=v*v; c++; } return((ret>>16)^ret); } mysql中出现的字符串hash函数 #ifndefnew_hash_function /* calchashvalue for a key */ static uintcalc_hashnr(const byte *key，uint length) { register uint nr=1，nr2=4; while (length--) { nr^= (((nr & 63)+nr2)*((uint) (uchar) *key++))+ (nr << 8); nr2+=3; } return((uint) nr); } /* calchashvalue for a key，case indepenently */ static uintcalc_hashnr_caseup(const byte *key，uint length) { register uint nr=1，nr2=4; while (length--) { nr^= (((nr & 63)+nr2)*((uint) (uchar) toupper(*key++)))+ (nr << 8); nr2+=3; } return((uint) nr); } #else /* * fowler/noll/vo hash * * the basis of the hash algorithm was taken from an idea sent by email to the * ieeeposix p1003.2 mailing list from phongvo (kpv@https://www.wendangku.net/doc/2b4687796.html,) and * glenn fowler (gsf@https://www.wendangku.net/doc/2b4687796.html,). landon curt noll (chongo@https://www.wendangku.net/doc/2b4687796.html,) * later improved on their algorithm. * * the magic is in the interesting relationship between the special prime * 16777619 (2^24 + 403) and 2^32 and 2^8. * * this hash produces the fewest collisions of any function that we"ve seen so * far，and works well on both numbers and strings. */ uintcalc_hashnr(const byte *key，uintlen) { const byte *end=key+len; uint hash; for (hash = 0; key < end; key++) { hash *= 16777619; hash ^= (uint) *(uchar*) key; } return (hash); } uintcalc_hashnr_caseup(const byte *key，uintlen) { const byte *end=key+len; uint hash; for (hash = 0; key < end; key++) { hash *= 16777619; hash ^= (uint) (uchar) toupper(*key); } return (hash); } #endif 从上表可以看出，这些经典软件虽然构造字符串Hash函数的方法不同，但是它们的效率都是不错的，相互之间差距很小，读者可以参考实际情况从其中借鉴使用。 暴雪公司有个经典的字符串的hash公式 先提一个简单的问题，假如有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？ 有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了。 最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法 unsigned long HashString(char *lpszFileName, unsigned long dwHashType) { unsigned char *key = (unsigned char *)lpszFileName; unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE; intch; while(*key != 0) { ch = toupper(*key ); seed1 = cryptTable[(dwHashType<< 8) ch] ^ (seed1 seed2); seed2 = ch seed1 seed2 (seed2 << 5) 3; } return seed1; } Blizzard的这个算法是非常高效的，被称为"One-Way Hash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。 是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表(Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算(mod)对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置又没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)，现在仔细看看这个算法吧 intGetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, intnTableSize) { intnHash = HashString(lpszString), nHashPos = nHash % nTableSize; if (lpTable[nHashPos].bExists&& !strcmp(lpTable[nHashPos].pString, lpszString)) returnnHashPos; else return -1; //Error value } 看到此，我想大家都在想一个很严重的问题："假如两个字符串在哈希表中对应的位置相同怎么办？",究竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我碰到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。 事情到此似乎有了完美的结局，假如是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。 中国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，假如说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的22.3次方分之一，对一个游戏程序来说足够安全了。 现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延"的方式来解决问题，看看这个算法： intGetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, intnTableSize) { constint HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2; intnHash = HashString(lpszString, HASH_OFFSET); intnHashA = HashString(lpszString, HASH_A); intnHashB = HashString(lpszString, HASH_B); intnHashStart = nHash % nTableSize, nHashPos = nHashStart; while (lpTable[nHashPos].bExists) { if (lpTable[nHashPos].nHashA == nHashA&&lpTable[nHashPos].nHashB == nHashB) returnnHashPos; else nHashPos = (nHashPos 1) % nTableSize; if (nHashPos == nHashStart) break; } return -1; //Error value } 1. 计算出字符串的三个哈希值（一个用来确定位置，另外两个用来校验) 2. 察看哈希表中的这个位置 3. 哈希表中这个位置为空吗？假如为空，则肯定该字符串不存在，返回 4. 假如存在，则检查其他两个哈希值是否也匹配，假如匹配，则表示找到了该字符串，返回 5. 移到下一个位置，假如已经越界，则表示没有找到，返回 6. 看看是不是又回到了原来的位置，假如是，则返回没找到 7. 回到3 怎么样，很简单的算法吧，但确实是天才的idea, 其实最优秀的算法往往是简单有效的算法。 计算机算法领域 基本知识 Hash，一般翻译做“散列”，也有直接音译为”哈希“的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系 基本概念 * 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。 * 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。 常用的构造散列函数的方法 散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位ǐ 1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数） 2. 数字分析法 3. 平方取中法 4. 折叠法 5. 随机数法 6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。 处理冲突的方法 1. 开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法： 1. di=1,2,3,…, m-1，称线性探测再散列； 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列; 一致性哈希算法的应用及其优化 一．简单哈希算法 哈希（Hash）就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，使得散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。哈希算法是一种消息摘要算法，虽然哈希算法不是一种加密算法，但由于其单向运算，具有一定的不可逆性使其成为加密算法中的一个重要构成部分。 二．分布式缓存问题 哈希算法除了在数据加密中的运用外，也可以用在常见的数据分布式技术中。哈希计算是通过求模运算来计算哈希值的，然后根据哈希值将数据映射到存储空间中。设有由N 个存储节点组成的存储空间，采用简单哈希计算将一个数据对象object 映射到存储空间上的公式为：Hash（object）% N。 现在假设有一个网站，最近发现随着流量增加，服务器压力越来越大，之前直接读写数据库的方式已经不能满足用户的访问，于是想引入Memcached作为缓存机制。现在一共有三台机器可以作为Memcached服务器，如下图1所示。 图1.三台memcached服务器 可以用简单哈希计算：h = Hash(key) % 3 ，其中Hash是一个从字符串到正整数的哈希映射函数，这样能够保证对相同key的访问会被发送到相同的服务器。现在如果我们将Memcached Server分别编号为0、1、2，那么就可以根据上式和key计算出服务器编号h，然后去访问。 但是，由于这样做只是采用了简单的求模运算，使得简单哈希计算存在很多不足： 1）增删节点时，更新效率低。当系统中存储节点数量发生增加或减少时，映射公式将发生变化为Hash(object)%(N±1)，这将使得所有object 的映射位置发生变化，整个系统数据对象的映射位置都需要重新进行计算，系统无法对外界访问进行正常响应，将导致系统处于崩溃状态。 2）平衡性差，未考虑节点性能差异。由于硬件性能的提升，新添加的节点具有更好的承载能力，如何对算法进行改进，使节点性能可以得到较好利用，也是亟待解决的一个问题。 3）单调性不足。衡量数据分布技术的一项重要指标是单调性，单调性是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中，当又有新的缓冲加入到系统中时，哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 由上述分析可知，简单地采用模运算来计算object 的Hash值的算法显得过于简单，存在节点冲突，且难以满足单调性要求。 哈希算法介绍 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】 哈希算法简介 目录 1哈希算法概念 ...................................................... 2哈希函数 .......................................................... 3冲突的解决方法 .................................................... 4哈希算法应用 ...................................................... 关键词： 算法、哈希、c语言 摘要： 哈希算法在软件开发和Linux内核中多次被使用，由此可以见哈希算法的实用性和重要性。本文介绍了哈希算法的原理和应用，并给出了简略的代码实现，以便读者理解。 1哈希算法概念 哈希(hash 散列，音译为哈希)算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。 哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希算法都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。 哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上，并以关键字在地址区间中的项作为记录在表中的存储位置，这种表称为哈希表，所得存储位置称为哈希地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。 查找一般是对项的摸个部分（及数据成员）进行，这部分称为键（key）。例如，项可以由字符串作为键，附带一些数据成员。 理想的哈希表数据结构只不过是一个包含一些项的具有固定大小的数组。 通常的习惯是让项从0到 TableSize-1之间变化。 将每个键映射到0到TableSize-1 这个范围中的某个 数，并且将其放到适当的单元中，这个映射就称为散列函数 （hash funciton）。 如右图，john被散列到3，phil被散列到4，dave 被散列 到6，mary被散列到7. 这是哈希的基本思想。剩下的问题则是要选择一个函数， 决定当两个键散列到同一个值的时候（称为冲突），应该做 什么。 数据结构与算法-基础算法篇-哈希算法 1. 哈希算法 如何防止数据库中的用户信息被脱库？ 你会如何存储用户密码这么重要的数据吗？仅仅 MD5 加密一下存储就够了吗？ 在实际开发中，我们应该如何用哈希算法解决问题？ 1. 什么是哈希算法？ 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 2. 如何设计一个优秀的哈希算法？ 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈 希值。 2. 哈希算法的常见应用有哪些？ 7个常见应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 1. 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 2. 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 3. 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 4. 散列函数 1.如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？ 计算与数据结构篇 - 哈希算法 (Hash) 计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 构成哈希算法的条件： 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同； 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小； 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。 哈希算法的应用(上篇) 安全加密 说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。 除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。 前面我讲到的哈希算法四点要求，对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。 不过，即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像 MD5，有 2^128 个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于 1-2^128。 如果我们拿到一个 MD5 哈希值，希望通过毫无规律的穷举的方法，找到跟这个 MD5 值相同的另一个数据，那耗费的时间应该是个天文数字。所以，即便哈希算法存在冲突，但是在有限的时间和资-源下，哈希算法还是被很难破解的。 对于加密知识点的补充，md5这个算法固然安全可靠，但网络上也有针对MD5中出现的彩虹表，最常见的思路是在密码后面添加一组盐码(salt), 比如可以使用md5(1234567.'2019@STARK-%$#-idje-789'),2019@STARK-%$#-idje-789 作为盐码起到了一定的保护和安全的作用。 唯一标识(uuid) 我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。 经典字符串Hash函数 工作中经常需要用大hash这个强有力的工具，hash表最核心的部分则在于怎么设计一个好的hash函数，以使数据更均匀地分布在若干个桶上。下面来介绍一下我现在用到的一个hash函数，我们来看代码： unsigned chostcachehash::get_host_key(const string& host) { int result = 1; unsigned i = 0; for (i = 0; i 哈希算法乱谈（摘自知乎） 最近【现场实战追-女孩教-学】初步了解了Hash算法的相关知识，一些人的见解让我能够迅速的了解相对不熟悉的知识，故想摘录下来，【QQ】供以后温故而知新。 HASH【⒈】算法是密码学的基础，比较常用的有MD5和SHA，最重要的两【О】条性质，就是不可逆和无冲突。 所谓不【１】可逆，就是当你知道x的HASH值，无法求出x； 所谓无【б】冲突，就是当你知道x，无法求出一个y，使x与y的HA【９】SH值相同。 这两条性【⒌】质在数学上都是不成立的。因为一个函数必然可逆，且【２】由于HASH函数的值域有限，理论上会有无穷多个不同的原始值【６】，它们的hash值都相同。MD5和SHA做到的，是求逆和求冲突在计算上不可能，也就是正向计算很容易，而反向计算即使穷尽人类所有的计算资-源都做不到。 顺便说一下，王小云教授曾经成功制造出MD5的碰撞，即md5(a) = md5(b)。这样的碰撞只能随机生成，并不能根据一个已知的a求出b（即并没有破坏MD5的无冲突特性）。但这已经让他声名大噪了。 HASH算法的另外一个很广泛的用途，就是很多程序员都会使用的在数据库中保存用户密码的算法，通常不会直接保存用户密码（这样DBA就能看到用户密码啦，好危险啊），而是保存密码的HASH值，验 证的时候，用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致，从而完成验证。由于用户的密码的一样的可能性是很高的，防止DBA猜测用户密码，我们还会用一种俗称“撒盐”的过程，就是计算密码的HASH值之前，把密码和另外一个会比较发散的数据拼接，通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的，会很发散。最后，作为一个老程序员，我会把用户的HASH值保存好，然后把我自己密码的HASH值保存到数据库里面，然后用我自己的密码和其他用户的用户名去登录，然后再改回来解决我看不到用户密码而又要“偷窥”用户的需要。最大的好处是，数据库泄露后，得到用户数据库的黑客看着一大堆HASH值会翻白眼。 哈希算法又称为摘要算法，它可以将任意数据通过一个函数转换成长度固定的数据串（通常用16进制的字符串表示），函数与数据串之间形成一一映射的关系。 举个粒子，我写了一篇小说，摘要是一个string:'关于甲状腺精灵的奇妙冒险'，并附上这篇文章的摘要是'2d73d4f15c0db7f5ecb321b6a65e5d6d'。如果有人篡改了我的文章，并发表为'关于JOJO的奇妙冒险'，我可以立即发现我的文章被篡改过，因为根据'关于JOJO的奇妙冒险'计算出的摘要不同于原始文章的摘要。 可见，摘要算法就是通过摘要函数f()对任意长度的数据data计算出固定长度的摘要digest，目的是为了发现原始数据是否被人篡 哈希算法简介 目录 1哈希算法概念 (2) 2哈希函数 (3) 3冲突的解决方法 (3) 4哈希算法应用 (4) 关键词： 算法、哈希、c语言 摘要： 哈希算法在软件开发和Linux内核中多次被使用，由此可以见哈希算法的实用性和重要性。本文介绍了哈希算法的原理和应用，并给出了简略的代码实现，以便读者理解。 1哈希算法概念 哈希(hash 散列，音译为哈希) 算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。 哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希算法都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。 哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上，并以关键字在地址区间中的项作为记录在表中的存储位置，这种表称为哈希表，所得存储位置称为哈希地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。 查找一般是对项的摸个部分（及数据成员）进行，这部分称为键（key ）。例如，项可以由字符串作为键，附带一些数据成员。 理想的哈希表数据结构只不过是一个包含一些项的具有固定大小的数组。 通常的习惯是让项从0到 TableSize-1之间变化。 将每个键映射到0到TableSize-1 这个范围中的某个数 ，并且将其放到适当的单元中，这个映射就称为散列函数（hash funciton ）。 如右图，john 被散列到3，phil 被散列到4，dave 被散列到6，mary 被散列到7. 这是哈希的基本思想。剩下的问题则是要选择一个函数，决定当两个键散列到同一个值的时候（称为冲突），应该做什么。 SHA-1（安全哈希算法实现） 如题，不知道sha-1的自己百度吧。 1 #include 常见的Hash算法 1.简介 哈希函数按照定义可以实现一个伪随机数生成器(PRNG)，从这个角度可以得到一个公认的结论：哈希函数之间性能的比较可以通过比较其在伪随机生成方面的比较来衡量。 一些常用的分析技术，例如泊松分布可用于分析不同的哈希函数对不同的数据的碰撞率(collision rate)。一般来说，对任意一类的数据存在一个理论上完美的哈希函数。这个完美的哈希函数定义是没有发生任何碰撞，这意味着没有出现重复的散列值。在现实中它很难找到一个完美的哈希散列函数，而且这种完美函数的趋近变种在实际应用中的作用是相当有限的。在实践中人们普遍认识到，一个完美哈希函数的哈希函数，就是在一个特定的数据集上产生的的碰撞最少哈希的函数。 现在的问题是有各种类型的数据，有一些是高度随机的，有一些有包含高纬度的图形结构，这些都使得找到一个通用的哈希函数变得十分困难，即使是某一特定类型的数据，找到一个比较好的哈希函数也不是意见容易的事。我们所能做的就是通过试错方法来找到满足我们要求的哈希函数。可以从下面两个角度来选择哈希函数： 1.数据分布 一个衡量的措施是考虑一个哈希函数是否能将一组数据的哈希值进行很好的分布。要进行这种分析，需要知道碰撞的哈希值的个数，如果用链表来处理碰撞，则可以分析链表的平均长度，也可以分析散列值的分组数目。 2.哈希函数的效率 另个一个衡量的标准是哈希函数得到哈希值的效率。通常，包含哈希函数的算法的算法复杂度都假设为O(1)，这就是为什么在哈希表中搜索数据的时间复杂度会被认为是"平均为O(1)的复杂度"，而在另外一些常用的数据结构，比如图(通常被实现为红黑树)，则被认为是O(logn)的复杂度。 一个好的哈希函数必修在理论上非常的快、稳定并且是可确定的。通常哈希函数不可能达到O(1)的复杂度，但是哈希函数在字符串哈希的线性的搜索中确实是非常快的，并且通常哈希函数的对象是较小的主键标识符，这样整个过程应该是非常快的，并且在某种程度上是稳定的。 在这篇文章中介绍的哈希函数被称为简单的哈希函数。它们通常用于散列（哈希字符串）数据。它们被用来产生一种在诸如哈希表的关联容器使用的key。这些哈希函数不是密码安全的，很容易通过颠倒和组合不同数据的方式产生完全相同的哈希值。 2.哈希方法学 哈希函数通常是由他们产生哈希值的方法来定义的，有两种主要的方法： 1.基于加法和乘法的散列 这种方式是通过遍历数据中的元素然后每次对某个初始值进行加操作，其中加的值和这个数据的一个元素相关。通常这对某个元素值的计算要乘以一个素数。 Python算法系列-哈希算法 哈希算法一、常见数据查找算法简介二、什么是哈希三、实例：两个数字的和1.问题描述2.双指针办法解决3.哈希算法求解四、总结哈希算法又称散列函数算法，是一种查找算法。就是把一些复杂的数据通过某种映射关系。映射成更容易查找的方式，但这种映射关系可能会发生多个关键字映射到同一地址的现象，我们称之为冲突。在这种情况下，我们需要对关键字进行二次或更多次处理。出这种情况外，哈希算法可以实现在常数时间内存储和查找这些关键字。 一、常见数据查找算法简介 常见的数据查找算法： 顺序查找：是最简单的查找方法。需要对数据集中的逐个匹配。所以效率相对较低，不太适合大量数据的查找问题。 二分法查找：效率很高，但是要求数据必须有序。面对数据排序通常需要更多的时间。 深度优先和广度优先算法：对于大量的数据查找问题，效率并不高。这个我们后面专门讲解。 阿希查找算法：查找速度快，查询插入，删除操作简单等原因获得广泛的应用。 二、什么是哈希 哈希查找的原理：根据数量预先设一个长度为M的数组。使用一个哈希函数F并以数据的关键字作为自变量得到唯一的返回值，返回值的范围 是0~M-1。这样就可以利用哈希函数F将数据元素映射到一个数组的某一位下标，并把数据存放在对应位置，查找时利用哈希函数F计算，该数据应存放在哪里，在相应的存储位置取出查找的数据。 这里就有一个问题： 关键字的取值在一个很大的范围，数据在通过哈希函数进行映射时。很难找到一个哈希函数，使得这些关键字都能映射到唯一的值。就会出现多个关键字映射到同一个值的现象，这种现象我们称之为冲突。 哈西算法冲突的解决方案有很多：链地址法，二次再散列法。线性探测再散列建立一个公共溢出区 注意：链地址法本质是数组+链表的数据结构 链地址法存储数据过程： 首先建立一个数组哈希存储所有链表的头指针。由数组的关键字key 通过对应的哈希函数计算出哈希地址。找到相应的桶号之后，建立新的节点存储该数据。并把节点放到桶内的链表的最后面或者最前面。 链地址法查找数据：由数据关键字通过哈希。函数计算关键字对应的哈希地址之后顺序比较同类不节点。是否与所查到的关键字一样，直到找到数据为止，如果全部节点都不和关键字一样，则书名哈系表里没有该数据。解决了哈希函数的冲突。 用链地址法构造的散列表插入和删除节点操作易于实现，所以构造链表的时间开销很低。但是指针需要开辟额外的地址空间，当数据量很大时会扩大哈希表规模，内存空间要求较大。 三、实例：两个数字的和 实验二哈希算法MD5 1、目的 使学生认识理解数据哈希算法：了解其基本原理，掌握MD5算法过程。 2、环境 PC 1 台、软件VC60、 3、方法和步骤 （1）请根据算法的描述和你对算法过程的理解，选用一种编程语言C，C++，Java,Pascal来实现MD5和MAC算法，//以姓名小写全拼为消息，求消息的Md5指纹值 如图1填充： 图2：4轮线性调用 图3：第i轮指纹参数变到第i+1轮指纹参数。 4、注意 实验报告画出MD5的流程图； 对MD5照指导书进行详细描述。 记录64次线性过程所变的局部32位指纹的值，及变量名；第一个参数被更新，循环右移一个参数后作为下次的4参数。 如： 1：a: D6D117B4 2:d: 344A8432 3:c: 2F6FBD72 4:b: 7AD956F2 … 64 b: C08226B3 以计算器为工具，手工验证，第1次和16,32,48,64次执行的a,b,c,d的计算过程。验证过程与比对过程写于报告之上。 思考题： 如果以姓名消息，以8位学号为密钥求MD5的HMAC值，共要做几次哈希，每次哈希分别调用了次”round”? 5、预备知识 1．理解MD5过程 Step 1： Padding M0 → M1 |M1| ≡ 448 mod 512 填充到512位的整数倍差64位。或者64字节整数倍差8个字节。 –Padding内容: 100 0 Step 2: Append 64-bit length 填充前长度（单位：bits）。 –若|M0| > 2^64,则仅取低64位。即|M|%2^64 –数据格式：低字节在前(little-endian)小端格式。 –|M2|为512的倍数: Y1,…,YL-1(L个分组) Step 3: 实始化指纹值（小端格式） (little-endian) ←CV0←IV ，I=1。， （ABCD） A = 01 23 45 67 (左边是内存状况，值形式：0x67452301) B = 89 AB CD EF (0xEFCDAB89) C = FE DC BA 98 (0x98BADCFE) D = 76 54 32 10 (0x10325476) =IV, CVi= HMD5(CVi-1,Pi) Step 4: MD5：压缩;CV 4-1 (a=A,b=B,c=C,d=D) 4-2：从消息左边选出第三1个512位的分组，将其分16个整数x[ 0-15]。连同a,b,c,d 指纹整数，移位数组s，常数数组ac，进行16位FF非线性变换。 F(x, y, z)=(((x) & (y)) | ((~x) & (z))) FF(a, b, c, d, x, s, ac) { (a)+= F ((b), (c), (d)) + (x) + (UINT4)(ac); (a)= ROTATE_LEFT ((a), (s)); (a)+= (b); } //第1轮S盒 #define S11 7 #define S12 12 #define S13 17 #define S14 22 任务一 MD5算法111111********* 一．哈希函数简介 信息安全的核心技术是应用密码技术。密码技术的应用远不止局限于提供机密性服务,密码技术也提供数据完整性服务。密码学上的散列函数(Hash Functions)就是能提供数据完整性保障的一个重要工具。Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与消息一起传输给接收者。即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。 散列函数是一个函数，它以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。散列函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。鉴别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。 二．哈希函数特点 密码学哈希函数（cryptography hash function，简称为哈希函数）在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证。哈希函数的基本思想是对数据进行运算得到一个摘要，运算过程满足： z压缩性：任意长度的数据，算出的摘要长度都固定。 z容易计算：从原数据容易算出摘要。 z抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的摘要都有很大区别。 z弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），在计算上是困难的。 十一、从头到尾彻底解析Hash表算法 作者：July、wuliming、pkuoliver 出处：https://www.wendangku.net/doc/2b4687796.html,/v_JULY_v。 说明：本文分为三部分内容， 第一部分为一道百度面试题Top K算法的详解；第二部分为关于Hash表算法的详细阐述；第三部分为打造一个最快的Hash表算法。 ------------------------------------ 第一部分：Top K算法详解 问题描述 百度面试题： 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。 假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。 必备知识： 什么是哈希表？ 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。 而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位（文章第二、三部分，会针对Hash表详细阐述）。 问题解析： 要统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top10。所以我们可以基于这个思路分两步来设计该算法。 即，此问题的解决分为以下俩个步骤： 哈希查找算法的源代码 c语言 【问题描述】 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 [基本要求] 假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。 [测试数据] 读取熟悉的30个人的姓名。 #include 哈希及哈希算法的介绍 聊到区块链的时候也少不了会听到“哈希”、“哈希函数”、“哈希算法”，是不是听得一头雾水？别急，这一讲我们来讲讲什么是哈希算法。 1 哈希是一种加密算法 哈希函数（Hash Function），也称为散列函数或杂凑函数。哈希函数是一个公开函数，可以将任意长度的消息M映射成为一个长度较短且长度固定的值H（M），称H（M）为哈希值、散列值（Hash Value）、杂凑值或者消息摘要（Message Digest）。它是一种单向密码体制，即一个从明文到密文的不可逆映射，只有加密过程，没有解密过程。 它的函数表达式为：h=H（m） 无论输入是什么数字格式、文件有多大，输出都是固定长度的比特串。以比特币使用的Sh256算法为例，无论输入是什么数据文件，输出就是256bit。 每个bit就是一位0或者1，256bit就是256个0或者1二进制数字串，用16进制数字表示的话，就是多少位呢？ 16等于2的4次方，所以每一位16进制数字可以代表4位bit。那么，256位bit用16进制数字表示，当然是256除以4等于64位。 于是你通常看到的哈希值，就是这样的了： 00740f40257a13bf03b40f54a9fe398c79a664bb21cfa2870ab07888b21eeba8。 这是从btc上随便拷贝的一个哈希值，不放心的话你可以数一下，是不是64位~ 2 Hash函数的特点 Hash函数具有如下特点。 易压缩：对于任意大小的输入x，Hash值的长度很小，在实际应用中，函数H产生的Hash 值其长度是固定的。 易计算：对于任意给定的消息，计算其Hash值比较容易。 哈希算法SHA-512的基本概念及特性解析 这是为了让您对哈希算法执行过程中实际发生的事情有一个基本的了解。我使用SHA-512算法是为了帮助解释哈希函数的内部工作。 SHA-512是一种哈希算法，它对给定的数据执行哈希函数。 哈希算法被广泛应用于网络安全、数字证书甚至区块链等领域。由于哈希算法在数字安全和密码学中扮演着如此重要的角色，对于称为SHA-512的哈希算法来说，这是一个易于理解的演练，包括一些基本和简单的数学知识以及一些图表。它是一组称为SHA-2的哈希算法的一部分，其中包括SHA-256，也用于比特币区块链的哈希算法。 在开始解释SHA-512之前，我认为有一个关于哈希值函数的特性的基本概念是很有用的。 哈希函数 哈希函数将一些数据作为输入，并为输入数据生成固定长度的输出（称为哈希摘要）。然而，这个输出应该满足一些有用的条件。 1. 均匀分布：由于输出哈希摘要的长度是固定的，输入大小可能会有所不同，因此很明显，对于不同的输入值，将会得到一些输出值。即使是这样，哈希函数也应该是这样的：对于任何输入值，每个可能的输出值都应该是等可能的。也就是说，对于任何给定的输入值，每个可能的输出都有相同的可能性产生。 2. 固定长度：这应该是不言自明的。输出值都应该是固定长度的。例如，哈希函数的输出大小可以是20个字符，也可以是12个字符，等等。SHA-512的输出大小可以是512位。 3. 意见冲突：简单地说，这意味着不存在任何不可能找到两个不同的输入哈希函数，导致相同的输出（哈希摘要）。 这是关于哈希函数的简单介绍。现在让我们看看SHA-512。 哈希算法- SHA-512 所以SHA-512分几个阶段工作。这些阶段如下： ·输入格式 常见的hash算法有哪些及其原理是什么 Hash，一般翻译做散列，也有直接音译为哈希的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 哈希表是根据设定的哈希函数H（key）和处理冲突方法将一组关键字映射到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。 通过将单向数学函数（有时称为哈希算法）应用到任意数量的数据所得到的固定大小的结果。如果输入数据中有变化，则哈希也会发生变化。哈希可用于许多操作，包括身份验证和数字签名。也称为消息摘要。 简单解释：哈希（Hash）算法，即散列函数。它是一种单向密码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。 常用hash算法的介绍：（1）MD4 MD4（RFC 1320）是MIT 的Ronald L. Rivest在1990 年设计的，MD 是Message Digest （消息摘要）的缩写。它适用在32位字长的处理器上用高速软件实现它是基于32位操作数的位操作来实现的。 （2）MD5 MD5（RFC 1321）是Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与MD4 相同。MD5比MD4来得复杂，并且速度较之要 数据结构与算法分析：（十三）哈希算法 前面我们花了两篇把散列表搞清楚了。详情请戳： 数据结构与算法分析：（十一）散列表（上） 数据结构与算法分析：（十二）散列表（下） 可见散列表的重要性！那讲哈希算法为啥把前两篇的散列表的文章贴出了呢？难道它们有什么关系？没错，有关系，而且关系还很大。我们经常听到有人把散列表叫作哈希表或者Hash 表，把哈希算法叫作Hash 算法或者散列算法。那到底什么是哈希算法呢？我们接下来就来进入正题。 一、什么是哈希算法？ 哈希算法书上和各种其他平台上说的好复杂，让初学者一脸懵逼。其实哈希算法的原理非常简单：将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 有点抽象哈，我们拿MD5这种哈希算法来举下例： 我们分别对Riemann和Riemann的博客两个文本计算MD5哈希值，得到两串看起来毫无规律的字符串（MD5 的哈希值是 128 位的 Bit 长度，为了方便表示，我把它们转化成了 16 进制编码）。可以看出来，无论要哈希的文本有多长、多短，通过 MD5 哈希之后，得到的哈希值的长度都是相同的，而且得到的哈希值看起来像一堆随机数，完全没有规律。 MD5("Riemann") = bb4767201ad42c74e650c1b6c03d78fa MD5("Riemann的博客") = cd611a31ea969b908932d44d126d195b 我们再来看下两个非常相似的文本，Riemann和riemann,这两个文本只有首字母大小写不同，但你会发现这两个的哈希值完全不同。 MD5("Riemann") = bb4767201ad42c74e650c1b6c03d78fa MD5("riemann") = a1fb91ac128e6aa37fe42c663971ac3d 而且从哈希值不能反向推导出原始数据，比如上面的哈希值bb4767201ad42c74e650c1b6c03d78fa很难反推对应的文本Riemann。 哈希算法的应用非常非常多，这里选用了常见的七个，分别是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 二、哈希算法的应用 1、安全加密 说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。 这里严格意义上来说，MD5 是一个摘要算法，用于生成字符串的摘要信息以及签名校验信息，可以理解为数字签名。因为加密算法的话要有加、解密，而 MD5 是不可逆的，因此不能真正算加密算法。这里考虑 MD5 有加密功能，这里把它归进来哈，杠精勿杠。 除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。 对于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。哈希算法散列
一致性哈希算法应用及优化(最简洁明了的教程)
哈希算法介绍
哈 希 常 见 算 法 及 原 理
哈 希 常 见 算 法 及 原 理
字符串哈希算法
哈 希 常 见 算 法 及 原 理 ( 2 0 2 0 )
哈希算法介绍
SHA-1(安全哈希算法实现)
常见的Hash算法
哈 希 常 见 算 法 及 原 理
哈希算法MD5
Hash算法实验原理及哈希函数简介
从头到尾彻底解析Hash 表算法
哈希查找算法的源代码c语言
哈希及哈希算法的介绍
哈希算法SHA-512的基本概念及特性解析
常见的hash算法有哪些及其原理是什么
哈 希 常 见 算 法 及 原 理