Hash算法

@wanqiuz 2018-06-03 14:00:59发表于 wanqiuz/blog-articles

Q: 如何衡量一个hash算法的好坏?

A: 一个优秀的 hash 算法,将能实现:
正向快速:给定明文和 hash 算法,在有限时间和有限资源内能计算出 hash 值。
逆向困难:给定(若干) hash 值,在有限时间内很难(基本不可能)逆推出明文。
输入敏感:原始输入信息修改一点信息,产生的 hash 值看起来应该都有很大不同。
冲突避免:很难找到两段内容不同的明文,使得它们的 hash 值一致(发生冲突)。即对于任意两个不同的数据块,其hash值相同的可能性极小;对于一个给定的数据块,找到和它hash值相同的数据块极为困难。

Q: 你知道的常用hash算法有哪些?

A: 目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

Q: java中String类的hashCode()的实现?

A:

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Q: 为什么选择31

A: 第一,31是一个不大不小的质数,是作为 hashCode 乘子的优选质数之一。另外一些相近的质数,比如37、41、43等等,也都是不错的选择。那么为啥偏偏选中了31呢?请看第二个原因。
第二、31可以被 JVM 优化,31 * i = (i << 5) - i。

Q: ConcurrentHashMap能完全替代HashTable吗?