当前位置： java hashcode算法-hashcode最简单的算法
一、什么是Hash及其作用
让我举一个例子。 生活在世上的我们每个人都需要一个标志来表明自己的身份，才能参与各种社会活动。 也许你认为你的名字或者身份证就足以代表你，但是这种代表是很脆弱的，因为同名的人很多，身份证也是可以伪造的。 最可靠的方法是记录一个人的所有基因序列来代表那个人，但显然，这是不切实际的。 而指纹似乎是一个不错的选择，虽然一些专业机构仍然可以模拟某人的指纹，但价格太高了。
而对于在互联网世界中传输的文件，如何标识文件的身份同样重要。 例如，当我们下载一个文件时，文件的下载过程会经过很多网络服务器和路由器。 如何保证这个文件就是我们需要的呢？ 我们不可能一一检测到这个文件的每一个字节，也不能简单地利用文件名、文件大小等极易伪装的信息。 这时候我们就需要一个类似指纹的标记来检验文件的可靠性，这种指纹就是我们现在使用的Hash算法（也叫散列算法）。
哈希算法（Hash Algorithm），又称散列算法、散列算法，是一种从任意文件中创建小型数字“指纹”的方法。 与指纹一样，哈希算法是一种使用较短信息来确保文件唯一性的标志。 这个标志与文件的每一个字节都有关系，很难找到反向规则。 因此，当原文件改变时，其标志值也会改变，从而告诉文件使用者，当前文件不再是你需要的文件。
这个标志是什么意思？ 前面的文件下载过程就是一个很好的例子。 事实上，现在大多数网络部署和版本控制工具都使用哈希算法来确保文件的可靠性。 另一方面，我们在使用文件系统同步、备份等工具时，通过哈希算法来标记文件的独特性能，帮助我们降低系统开销。 这在很多云存储服务器中都有应用。
当然，作为指纹，哈希算法最重要的用途是对证书、文件、密码等高安全性内容进行加密保护。 这方面的使用主要是由于哈希算法的不可逆性。 这种不可逆性体现在，你不仅不可能根据哈希算法得到的指纹得到原始文件，也不可能简单地创建一个文件，使其指纹与目标指纹一致。 哈希算法的这种不可逆性支撑了许多安全框架的运行，这将是本文的重点。
2、Hash算法有什么特点
一个优秀的哈希算法将能够实现：
但是在不同的使用场景中，比如数据结构和安全领域，会强调某些特性。
2.1 Hash在管理数据结构中的应用
在使用hash进行管理的数据结构中，速度比较重要，防碰撞也不是很花哨，只要hash分布均匀即可。 比如在hashmap中，hash值（key）的作用是为了加快键值对的查找速度。 key的作用是在每个bucket中适当的放置元素，对防碰撞的要求没有那么高。 也就是说，经过哈希处理的键只需要保证值大致均匀地放在不同的桶中即可。 但是整个算法的集合性能直接关系到哈希值的生成速度，所以此时哈希值的生成速度就显得尤为重要。 以JDK中的String.hashCode()方法为例：
public int hashCode() {
int h = hash;
//hash default value : 0
if (h == 0 && value.length > 0) {
//value : char storage
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
一个非常简单的乘法和加法迭代运算。 在很多hash算法中，都是采用异或+加法进行迭代，速度和前者差不多。
2.1 哈希在密码学中的应用
在密码学中，哈希算法主要用于消息的摘要和签名，换句话说，它主要用于验证整个消息的完整性。 比如我们登录知乎，需要输入密码。 如果知乎把这个密码明文保存，黑客很容易盗取大家的密码登录，特别不安全。 于是知乎想到了一个方法，使用哈希算法生成密码签名，知乎只在后台保存签名值。 由于哈希算法是不可逆的，即使黑客获得了签名，也没有任何用处； 而如果你在网站登录界面输入密码，那么知乎后台会重新计算哈希值，与网站存储的哈希值相同。 比较原始的哈希值，如果相同，则证明你有这个账户的密码，那么你就可以登录了。银行也一样。 银行从来不敢保存用户密码的原文，只保存密码的哈希值。 在这些应用场景中，对防碰撞、防篡改能力的要求极高，对速度的要求是其次的。 一个设计良好的哈希算法具有很高的抗碰撞能力。 以MD5为例，其输出长度为128位，设计预期碰撞概率为 ，这是一个极小的数字——即使MD5被王小云教授破解后，其碰撞概率上限也高达，至少需要一次搜索才能有1/2的概率找到与目标文件相同的hash值。 而对于两个相似的字符串，MD5加密结果如下：
MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8";可以看出，仅仅改变了一位，两者的MD5值就相差很大了 。
ps：其实把哈希算法当成加密算法是不准确的。 我们知道，加密总是相对于解密而言的。 没有解密怎么谈加密呢？ HASH 被设计成不可解的。 而且如果我们不附加一个随机盐值，HASH密码很容易被字典攻击侵入。
3、Hash算法是如何实现的？
随着密码学和信息安全的发展，各种加密算法和哈希算法已经不是三言两语所能解释的了。 这里我们只提供几个简单的概念供大家参考。
作为一种哈希算法，其主要作用是用一种算法将原始的大文件信息用几个字符记录下来，并保证每个字节都会对最终结果产生影响。 那么你可能已经想到，取模的算法可以满足我们的需求。
事实上，模算法作为一种不可逆的计算方法，已经成为整个现代密码学的基础。 只要涉及计算机安全和加密领域，就会有模块化计算。 哈希算法也不例外。 最原始的哈希算法之一就是简单地选择一个数进行取模运算，比如下面的程序。
# 构造散列函数
def hash(a):
return a % 8
# 测试散列函数功能
print(hash(233))
print(hash(234))
print(hash(235))
# 输出结果
- 1
- 2
- 3显然，上面的程序完成了一个哈希算法应该达到的首要目标：用更少的文本来表示很长的内容（取模后的数字必须小于8）。 但是你可能已经注意到，单纯使用取模算法计算出来的结果具有明显的规律性，这会让算法难以保证不可逆性。 所以我们将使用另一种方法，即异或。
让我们再看看下面的程序。 我们在哈希函数中加入一个异或过程。
# 构造散列函数
def hash(a):
return (a % 8) ^ 5
# 测试散列函数功能
print(hash(233))
print(hash(234))
print(hash(235))
# 输出结果
- 4
- 7
- 6显然，在增加了一层异或过程后，计算后结果的规律性就没有那么明显了。
当然，你可能会觉得这样的算法还是很不安全的。 如果用户使用一系列不断变化的文本来与计算结果进行比较，就很有可能发现算法中包含的规律。 但我们还有其他选择。 比如在进行计算之前修改原文，或者增加额外的操作（比如移位），比如下面的程序。
# 构造散列函数
def hash(a):
return (a + 2 + (a << 1)) % 8 ^ 5
# 测试散列函数功能
print(hash(233))
print(hash(234))
print(hash(235))
# 输出结果
- 0
- 5
- 6这样得到的哈希算法很难找到它的内在规律，也就是说，我们不能轻易给一个数，使得上面的哈希函数运算后的结果等于4——除非我们穷举测试。
上面的算法是不是很简单？ 其实下面我们要介绍的常见算法MD5和SHA1，它们的本质算法就是这么简单，只是会增加更多的循环和计算，以加强哈希函数的可靠性。
4、Hash的流行算法有哪些？
目前流行的Hash算法有MD5、SHA-1和SHA-2。
可以看出，上述流行算法最重要的区别在于“抗碰撞性强”。
5、那么，Hash算法的“碰撞”是什么？
你可能已经发现，在实现算法章节的第一个例子中，我们尝试的哈希算法得到的值必须是不大于8的自然数。因此，如果我们随机取9个数来计算，我们肯定会得到在至少有两个相同的值，我们称这种情况为哈希算法的“碰撞”。
这个很好理解，因为作为一个可用的哈希算法，它的位数肯定是有限制的，也就是说它能记录的文件数是有限的——但是文件数是无限的，两个文件指纹碰撞了。的概率永远不会为零。
但这并不代表不能使用hash算法，因为一切都要考虑成本，为了中头奖而去买所有的彩票是没有意义的。 现代哈希算法之所以存在，是因为它的不可逆性能是在一个比较高的概率下实现的，也就是说，发现碰撞的概率很小，而这个碰撞被利用的概率就更小了。
可以找到一组任意的碰撞，只要它们是详尽无遗的。 哈希算法得到的指纹数量是有限的。 比如MD5算法的指纹长度是128位，也就是说我们只要穷举21282128次，肯定会得到一组碰撞。 当然，这个时间成本是难以想象的。 更重要的是，仅仅找到一组碰撞并没有多大意义。 更有意义的是，如果我们已经有了一组指纹，我们是否可以找到一个哈希值等于这组指纹的原始文件。 如果实现这一点，我们就可以很容易地篡改和伪造网络证书和密码等关键信息。
你可能听说过 MD5 被破解的消息——但事实上，即使是 MD5 这种过时的哈希算法，也很难被逆转。 现在我们更多的还是依靠海量词典来尝试，即通过大量已知的文件-指纹对应关系来查找数据库中是否存在某个指纹对应的文件。
5.1 MD5的实际碰撞案例
让我们来看一个真实的碰撞案例。 我们之所以说 MD5 过时了，是因为哈希算法在某些时候很难表现出一些优点——例如，在处理文件的微小修改时，哈希算法得到的指纹结果应该有明显的不同，下面的程序表明 MD5 无法实现这一点。
import hashlib
# 两段HEX字节串，注意它们有细微差别
a = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef")
b = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef")
# 输出MD5，它们的结果一致
print(hashlib.md5(a).hexdigest())
print(hashlib.md5(b).hexdigest())
### a和b输出结果都为：
cee9a457e790cf20d4bdaa6d69f01e41
cee9a457e790cf20d4bdaa6d69f01e41
虽然还有许多其他类似的碰撞案例，但以上只是原始文件中一个相对较小的示例。 事实上，现在我们可以用智能手机在几秒钟内找到 MD5 的碰撞案例。 因此，MD5在几年前还没有被推荐作为应用中的哈希算法方案。 取而代之的是SHA族算法，也就是安全算法。 哈希算法（Secure Hash Algorithm，缩写为SHA）。
5.2 SHA族算法与SHA1冲突
安全哈希算法本质上和MD5算法类似，但是安全性要领先很多——这种领先型更多的体现在碰撞攻击的时间开销上，当然相应的计算时间也会更慢。
SHA家族算法有很多种，包括SHA0、SHA1、SHA256、SHA384等，它们的计算方法和计算速度各不相同。 其中，SHA1是目前使用最广泛的算法。 许多版本控制工具包括GitHub和各种云同步服务都使用SHA1来区分文件，许多安全证书或签名也使用SHA1来保证唯一性。 长期以来，人们认为 SHA1 是非常安全的，至少我们还没有发现任何碰撞案例。
但这一事实在 2017 年 2 月被打破了。CWI 和谷歌的研究人员设法找到了一个 SHA1 冲突的例子，令人惊讶的是，两个真实的、可读的 PDF 文件发生了冲突。 这两个PDF文件的内容不同，但是SHA1值是完全一样的。 （关于此事的范围和讨论，请参考知乎上的讨论：如何评价谷歌2月23日宣布实现SHA-1碰撞？）
因此，对于一些大型商业机构来说，MD5和SHA1不够安全，建议至少使用SHA2-256算法。
6. Hash在Java中的应用 6.1 HashMap的复杂性
在介绍HashMap的实现之前，我们先来了解一下HashMap、ArrayList和LinkedList在数据复杂度上的区别。 下图是他们的性能对比图：
获得
抬头
添加/删除
空间
数组列表
O(1)
O(1)
在）
在）
链表
在）
在）
O(1)
在）
哈希表
O(N/Bucket_size)
O(N/Bucket_size)
O(N/Bucket_size)
在）
可以看出HashMap的整体性能很好，但是不稳定。 它是 O(N/Buckets)。 N是数组中没有发生碰撞的元素，Buckets是碰撞产生的链表。
注意：碰撞其实是非常罕见的，所以N/Bucket_size大约等于1
HashMap 是 Array 和 Link 之间的折衷。 Array和Link可以说是两个速度方向的极端。 Array侧重于数据获取，但是处理修改（增/删）的效率很低； 保留下一个对象的指针，寻找某个数据需要遍历之前所有的数据，所以效率比较低，在修改操作上比较快。
6.2 HashMap的实现
本文分析JDK8的API实现
6.2.1 key的哈希计算
在JDK8中，由于使用了红黑树来处理大链表的开销，hash端可以省力一些，只需要计算hashCode移到低位即可。
static final int hash(Object key) {
int h;
//计算hashCode，并无符号移动到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}例如：363771819^(363771819 >>> 16)
0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)这样做可以获得更均匀的高地位组合。
下面是Java中常用的几种哈希码（hashCode）算法。
Object类的hashCode。 返回对象处理后的内存地址。 由于每个对象的内存地址不同，哈希码也不同。 这是一个native method，依赖于JVM内部的设计，一般是某种C地址的偏移量。
String类的hashCode。 根据String类中包含的字符串内容，按照特殊算法返回哈希码。 只要字符串内容相同，返回的哈希码也相同。
对于Integer等封装类，返回的hash code是Integer对象中包含的整数的值，例如Integer i1=new Integer(100)，i1.hashCode的值为100。可以看出，两个相同大小的整数对象返回相同的哈希码。
int、char等基础类不需要hashCode。 如果需要存储，会自动装箱，计算方法同上。
6.2.2 获取数组索引的位置
哈希算出来了，我们现在要把它插入到数组中
i = (tab.length - 1) & hash；通过位操作，确定当前位置，因为HashMap数组的大小始终为2^n，所以实际操作为(0xfff…ff)&hash，其中tab.length-1相当于一个掩码，用于过滤out 当前长度位的散列，这样每个i都可以插入到数组中。
6.2.3 生成包装类
这个对象是一个包装类，Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node next;
//getter and setter .etc.
} 6.2.4 将包装类插入数组
(1). 如果input当前位置为空，则插入，如图，左边是插入前，右边是插入后
0 0
| |
1 -> null 1 - > null
| |
2 -> null 2 - > null
| |
..-> null ..- > null
| |
i -> null i - > new node
| |
n -> null n - > null
(2). 如果当前位置已经有一个节点，它们发生碰撞，则新的放在前面，旧的放在后面。 这称为链地址法来处理冲突。
0 0
| |
1 -> null 1 - > null
| |
2 -> null 2 - > null
| |
..-> null ..- > null
| |
i -> old i - > new - > old
| |
n -> null n - > null
我们可以发现失败的hashCode算法会导致HashMap的性能从数组下降到链表。 因此，为了避免碰撞，需要提高hashCode结果的一致性。
6.3 扩展
如果75%的表已经被占用，则认为需要扩容
(threshold = capacity * load factor ) < size它主要有两个步骤：
6.3.1 容量翻倍
左移一位就是展开成double，用位运算代替乘法运算
newCap = oldCap << 1;
newThr = oldThr << 1;6.3.2 遍历计算Hash
for (int j = 0; j < oldCap; ++j) {
Node e;
//如果发现当前有Bucket
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果这里没有碰撞
if (e.next == null)
//重新计算Hash，分配位置
newTab[e.hash & (newCap - 1)] = e;
//这个见下面的新特性介绍，如果是树，就填入树
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
//如果是链表，就保留顺序....目前就看懂这点
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
} 由此可见，扩容需要遍历和重新分配，成本非常高java hashcode算法，所以选择一个好的初始容量非常重要。
6.4 扩容如何提升性能？ 6.5 HashMap和HashTable的主要区别
在很多Java基础书籍中已经说过了。 它们的主要区别在于表在全局范围内增加了线程同步保护。
6.6 在 Android 中使用 SparseArray 代替 HashMap
官方推荐使用SparseArray（[spɑ:s][ə'reɪ]java hashcode算法，稀疏数组）或者LongSparseArray，而不是HashMap。 官方总结有以下优点：
总结
《算法设计手册》一书中提到，雅虎的首席科学家Udi Manber曾说过，在雅虎使用的算法中，最重要的三种是：Hash、Hash和Hash。 其实从Hash的应用就可以看出，git使用sha1判断文件变化，密码使用MD5生成摘要然后加盐等等，可见Hash在计算机世界中的重要性。 另一本书还举了一个很有意思的展示例子：
在拍卖中，价格最高的物品获胜。 如果每个人只有一次出价机会，同时提交自己的价格，最后会一起公布，价高者得。 这种形式存在作弊的可能性。 如果竞价者可以黑进后台，然后把自己的价格改成最高价+1，就可以以最低价中标。 如何防止这种作弊行为？
答案很简单，所有参与者都必须提交自己出价的哈希值。 即使有人能黑进后台，也无法得知明文价格。 宣布时，只需将原始出价与哈希值进行比较即可。 是不是很巧妙？
是的，上述做法与上述网站使用MD5值而不是明文存储密码的思路是一样的，殊途同归。
可以看到无论是密码学、数据结构，还是现实生活中的应用，处处都可以看到Hash的影子。 通过本文的介绍，相信您不仅知道它的名字，更能理解它的含义。
参考
上一篇 
