Hash算法及相关应用

2020-11-30

加密传输技术

有 N 人看过

本文主要简单介绍Hash算法的原理，种类和一些应用举例

一、什么是Hash算法

Hash算法又称散列算法，特点是把任意长度的输入，通过散列算法变成固定长度的输出，这个输出即散列值（即是某种映射关系），
由于散列值得空间远小于输入空间，因此存在不同输入得到相同的散列值，这种现象称为碰撞。
特性：同一散列算法，散列值不同，输入肯定不同，反之则不一定成立。

二、常见的Hash函数（算法）

基本算法

目前业界有很多Hash算法，其算法核心基本可以归纳下面几种算法的组合

// 由于篇幅原因，主要介绍碰撞解决方案的基本原理，详细请自行查阅
1.直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址
2.数字分析法：提取关键字中取值比较均匀的数字作为哈希地址
3.除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址
4.分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址
5.平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址
6.伪随机数法：采用一个伪随机数当作哈希函数

衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及解决方案，任何Hash函数都无法避免碰撞，以下是常见的一些碰撞的解决方法：

// 由于篇幅原因，主要介绍碰撞解决方案的基本原理，详细请自行查阅
1.开放地址法：开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入
2.链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部
3.再哈希法：当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止
4.建立公共溢出区：将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中

举例说明

哈希算法为了提高效率并且减少其碰撞的概率，不断改进，诞生了很多哈希算法。下面列举了部分应用较为广泛的哈希算法：

三、Hash函数的应用

1. HashMap

Java中有两种常见的数据结构数组和链表

数组:寻址容易，插入和删除困难

链表:寻址困难，插入和删除容易

上面提到哈希算法的其中一种解决冲突的方式——链地址法，就是将这两种数据结构相结合，发挥各自的优势(可以简单理解为链表数组)

可以很清楚地看到，左边是数组，其中每个成员均由链表组成。我们通过某种方式计算元素的特征值，也就是获取数组的下标，从而找到了正确的链表，再从链表中找到正确的元素。这个计算特征值的方法就是哈希算法。

final int hash(Object k) {
    ...
}

在JDK1.7中，HashMap的源码正是采用了这种方法来存储对象。HashMap中有一个hash(key)方法，它的作用就是根据key来定位这个元素在链表数组的下标，该方法返回的是个int类型的数值，那应该怎么计算这个int值并且尽可能的不重复呢？

我们都知道，Object类都会有一个hashCode方法。

public class Object {

    ...

    public native int hashCode();

    ...
}

这个方法会将对象进行哈希运算，得到该对象的“标签”，这个标签有一定程度的唯一性，因此可以用hashCode方法来计算HashMap中hash方法的返回。事实上，HashMap也是这样实现的，不过，还对key的hashCode做了一些扰动处理，降低了”碰撞”的概率。

虽然得到一个int数据了，但数组是有长度的，要怎样做才能把数值较为均匀地处理在数组长度范围内呢？

static int indexFor(int h, int length) {
    ...
}

是的，我们很容易想到——取模。在HashMap中，还提供了一个方法indexFor (代码如上)，就是做了这样的事情，该方法传入hash方法返回的int值和数组长度(HashMap大小),计算得到key在链表数组的真实下标。
总结一下

hash: 该方法主要是将object对象转换成一个整型
indexFor: 该方法主要是将hash生成的整型转换成链表数组的下标

源码分析

流程大概说完了，接下来我们看看源码

为了方便理解，先看看取模的方法——indexFor

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

可能有人会好奇，为什么取模是用的&而不是%呢。其实在java中，之所以用位运算(&)代替取模运算(%)，主要就是考虑的效率。位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

为什么&可以替代%呢？这里摘抄了一段网上的解释

X % 2^n = X & (2^n – 1)
2^n表示2的n次方，也就是说，一个数对2^n取模 == 一个数和(2^n – 1)做按位与运算 。
假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 = 7 ，即0111。
此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。
从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商。
而被移掉的部分(后三位)，则是X % 8，也就是余数。

当然，这样替换是有前提条件的，这里从注释可以看出数组的length必须是2的倍数（事实上，在初始化HashMap时，如果不是2的倍数，也会调用inflateTable方法将length变成2的倍数，这里不再赘述）。

接下来看看计算hash值的方法——hash

final int hash(Object k) {
    // 这两步主要是涉及到HashMap的随机种子，主要目的也是为了哈希冲突更难查找，默认是0
    // 不是这次分析的重点略过
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

前面提到过，哈希算法会产生碰撞，而位运算(&)是很容易产生相同的结果，也就是冲突。来看个例子:

 1101 1011 1110 1101 1101 1100 1101 1001          0011 1100 1001 0010 1111 1011 0011 1001
&
 0000 0000 0000 0000 0000 0000 0000 1111          0000 0000 0000 0000 0000 0000 0000 1111
=
 0000 0000 0000 0000 0000 0000 0000 1001          0000 0000 0000 0000 0000 0000 0000 1001

可以看到不同的两个键值，高位不同，低位相同，按位与运算得到了相同的结果。为了防止这种冲突的情况，HashMap对hash进行了扰动计算——主要原理是结合高位和低位的特征，使得微小的变动，也能让结果完全不一样，降低冲突的概率。代码实现如下:

// ^按位异或运算,同位置，相同为0,不同为1
1. h ^= k.hashCode();
// >>>无符号位右移，高位以0填充
2. h ^= (h >>> 20) ^ (h >>> 12);
3. return h ^ (h >>> 7) ^ (h >>> 4);

知道了算法，那我们把冲突的两个键值做一下扰动计算:

h          1101 1011 1110 1101 1101 1100 1101 1001      0011 1100 1001 0010 1111 1011 0011 1001

h>>>20     0000 0000 0000 0000 0000 1101 1011 1110      0000 0000 0000 0000 0000 0011 1100 1001

h>>>12     0000 0000 0000 1101 1011 1110 1101 1101      0000 0000 0000 0011 1100 1001 0010 1111

step 2     1101 1011 1110 0000 0110 1111 1011 1010      0011 1100 1001 0001 0011 0001 1101 1111

h>>>7      0000 0001 1011 0111 1100 0000 1101 1111      0000 0000 0111 1001 0010 0010 0110 0011

h>>>4      0000 1101 1011 1110 0000 0110 1111 1011      0000 0011 1100 1001 0001 0011 0001 1101

step3      1101 0111 1110 1001 1010 1001 1001 1110      0011 1111 0010 0001 0000 0000 1010 0001

&15        0000 0000 0000 0000 0000 0000 0000 1110      0000 0000 0000 0000 0000 0000 0000 0001

通过上面一系列的扰动计算可以看出，成功解决了两个原本冲突的键值。

总结下

JDK版本: 1.7
类: HashMap
涉及方法：hash,indexFor
核心思路:：HashMap以链表数组的数据结构存储数据，通过计算key的hash值并且取模得到链表数组的下标。
注意：
1. 用按位与运算代替取模运算的好处除了提高效率，还有一点是保证结果为正数
2. 数组内存的是链表的头指针
3. 使用链表数组的好处是结合数组和链表的优点，无冲突时直接计算hash值拿到对应链表的第一个节点，复杂度为o(1);有冲突时，拿到该链表后，遍历链表取值,复杂度最高为o(n)
4. HashMap的大小默认是16,且一定是2的n次方

未完待续~

参考文章: hash算法详解