散列函数（哈希）（转）

[TOC] 本文转自其他人的博客。简化了一下，方便备忘。

概述

Hash一般翻译作散列也有直接音译作“哈希”。就是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。

散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。

哈希函数的应用非常广泛，各种校验、签名、密码，都是哈希函数应用的重要场景。

性质

• 确定性：哈希的散列值不同，那么哈希的原始输入也就不同。
• 不确定性：同一个散列值很有可能对应多个不同的原始输入。称为“哈希碰撞”。

实现

哈希函数的实现分为两部分：构造和解决冲突。

构造

哈希函数的构造应该满足以下准则：

• 散列函数的计算简单，快速。
• 散列函数能将关键字集合K均匀地分布在地址集{0,1，…，m-1}上，使冲突最小。

直接定址法

H(key) = key 或 H(key) = a·key + b 直接定址法，不会有哈希冲突。但实际这样使用的情况较少。

相乘取整法

H(key) = (int) ( m * ( key*A - (int)(key*A) ) ) 其中 0 < A < 1 注意：该方法最大的优点是m的选取比除余法要求更低。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。Knuth建议选取 0.61803……。

平方取中法

取关键字平方后的中间几位为哈希地址。 F(a) = a的中间三位。 H(key) = F(key^2)

除留余数法

H(key) = key MOD p (p ≤ m)

随机数法

H(key) = random (key)

jdk中HashMap的hash构造

    static final int hash(Object var0) {
        int var1;
        return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
    }

哈希冲突的解决

开放地址法

就是在发生冲突后，通过某种探测技术，去依次探查其他单元，直到探查到不冲突为止，将元素添加进去。

假如是在index的位置发生哈希冲突，那么通常有一下几种探测方式：

线性探测法（线性探测再散列）

向后依次探测index+1，index+2…位置，看是否冲突，直到不冲突为止，将元素添加进去。

平方探测法

不探测index的后一个位置，而是探测2i位置，比如探测20位置上时发生冲突，接着探测2^1位置，依此类推，直至冲突解决。

再哈希法：（双散列法）

在发生哈希冲突后，使用另外一个哈希算法产生一个新的地址，直到不发生冲突为止。这个应该很好理解。

再哈希法可以有效的避免堆积现象，但是缺点是不能增加了计算时间和哈希算法的数量，而且不能保证在哈希表未满的情况下，总能找到不冲突的地址。

链地址法（开散列法）

基本思想：

链表法就是在发生冲突的地址处，挂一个单向链表，然后所有在该位置冲突的数据，都插入这个链表中。插入数据的方式有多种，可以从链表的尾部向头部依次插入数据，也可以从头部向尾部依次插入数据，也可以依据某种规则在链表的中间插入数据，总之保证链表中的数据的有序性。Java的HashMap类就是采取链表法的处理方案。

结语

哈希表一旦发生冲突，其性能就会显著下降。因此建立哈希表时必须规避哈希冲突的产生，大多数哈希表的实现都是：第一步，是通过哈希算法将key值转换一个整数以确定数据的存储位置；第二步，检查是否发生哈希冲突，以及确定发生冲突后的处理方案。