什么是hash?

chenfei0 2020-07-30

1.什么是hash算法
Hash(散列、杂凑)算法,是把任意长度的输入通过特定的算法变换成固定长度的输出,输出的值就是hash值。这个特定的算法就叫hash算法,hash算法并不是一个固定不变的算法。只要是能达到这个目的的算法都可以说hash算法。例如MD5,SHA,String.hashcode()都是hash算法。另外不同的输入可能会得出相同的hash值,那么这种现象称为hash碰撞,无论是采用那种hash算法,hash碰撞都是不可避免的,我们只能通过改进hash算法,把出现碰撞的概率降低。PS:hash这个词在因为英语中的意思是剁碎的食物,反应在计算机领域的意思大概就是把任意的数据切割打碎,输出固定长度的数据,所以通过hash这个单词也能大概理解hash算法的意思。

2.hash算法的应用
2.1 哈希表
由于用途的不同,hash在数据结构中的含义和密码学中的含义并不相同。所以在这两种不同的领域里,算法的设计侧重点也不同。在数据结构中,我们利用hash值来建立以key-value形式的数据结构——哈希表(散列表),使用哈希表我们可以实现对特定value的快速查找,时间复杂度为O(1);如果是普通的数组或者链表的数据结构,只能通过遍历的方式对特定value值的查找,时间复杂度为O(n);如果数组是有序的,那么可以通过二分查找,或者即使使用平衡二叉树的数据结构,时间复杂度为O(logN),都不如哈希表高效。但如果hash值出现频繁的碰撞,哈希表的查找效率就会降低,最坏的情况就会变成数组或者链表,复杂度降为O(n),因此数据结构中的hash算法应该要能均匀的输出hash值,使key能均匀的分布在不同的桶中。什么是hash?

 2.2 密码学
hash算法也可以理解为一种压缩映射,把任意长度的信息压缩成固定长度,在密码学上把经过hash算法计算压缩后的数据称为信息摘要。
我们可以通过对比信息摘要来检验数据的完整性,防止数据在传输过程中被篡改。例如在http协议中传递参数a=1&b=2&hash=xxx,我们通过计算参数a=1&b=2+privateKey(一个双方都知道的密钥)的hash值,并将这个hash值也一并传递,那么接收方通过重新计算参数的hash值并与传递过来的hash进行对比,如果不一致那么就说明参数在传递过程中被人篡改了。所以密码学中的hash算法要有很强的抗篡改能力,对于一个数据块,哪怕只改动其一个比特位,其hash值的改动也会非常大。

什么是hash?

相关推荐