如何判斷一個哈希函數的好壞

哈希函數

在計算機中，函數是一個有輸入輸出的黑匣子，而哈希函數是其中一類函數。我們通常會接觸兩類哈希函數。

用于哈希表的哈希函數。比如布隆過濾裡的哈希函數， HashMap 的哈希函數。
用于加密和簽名的哈希函數。比如，MD5，SHA-256。

哈希函數通常具有以下特征。

長度固定。任意的輸入一定得到相同的輸出長度。
确定性。相同的輸入一定得到相同的輸出。
單向性。通過輸入得到輸出，但是不能通過輸出反推輸入。

哈希函數品質

哈希函數作用是将一堆資料資訊映射到一個簡短資料，這個簡短資料代表了整個資料資訊。比如身份證号。

如何衡量一個哈希函數品質，主要從考量以下方面

哈希值是否分布均勻，呈現出随機性，有利于哈希表空間使用率提升，增加哈希的破解難度；
哈希碰撞的機率很低，碰撞機率應該控制在一定範圍；
是否計算得更快，一個哈希函數計算時間越短效率越高。

碰撞機率

什麼是碰撞？

當同一個哈希值映射了不同資料時，即産生了碰撞。

碰撞不可避免，隻能盡可能減小碰撞機率，而碰撞機率由哈希長度和算法決定。

碰撞機率如何評估。機率學中有個經典問題生日問題，數學規律揭示，23人中存在兩人生日相同的機率會大于50%，100人中存在兩人生日相同的機率超過99%。這違反直覺經驗，是以也叫生日悖論。

生日問題是碰撞機率的理論指導。密碼學中，攻擊者根據此理論隻需要 \({\textstyle {\sqrt {2^{n}}}=2^{n/2}}\) 次就能找哈希函數碰撞。

下面是不同位哈希的碰撞參考表：

另外根據維基上的推導，我們還可以得到以下公式。

指定已有哈希值數量 \(n\)，估算碰撞機率 \(p (n)\)

\[p (n)\approx 1- e^{-\frac{n(n-1)}{2N}}

指定碰撞機率 \(p\) 和哈希範圍最大值 \(d\)，估算達到碰撞機率時需要的哈希數量 \(n\)

\[n (p)\approx \sqrt{2\cdot d\ln\left({1 \over 1-p}\right)}+{1 \over 2}

指定碰撞機率 \(p\) 和哈希範圍最大值 \(d\)，估算碰撞數量 \(rn\)

\[{\displaystyle rn=n-d+d\left({\frac {d-1}{d}}\right)^{n }}

估算理論碰撞機率

public static double collisionProb(double n, double d) {
	return 1 - Math.exp(-0.5 * (n * (n - 1)) / d);
}

估算達到碰撞機率時需要的哈希數量

public static long collisionN(double p, double d) {
	return Math.round(Math.sqrt(2 * d * Math.log(1 / (1 - p))) + 0.5);
}

估算碰撞哈希數量

public static double collisionRN(double n, double d) {
 	return n - d + d * Math.pow((d - 1) / d, n);
}

根據上面公式，我們評估一下

String.hashCode()

，Java裡面

hashCode

() 傳回

int

，是以哈希範圍是 \(2^{32}\)。看下

String.hashCode()

在1000萬UUID下的表現。

1000萬UUID，理論上的碰撞數量為11632.50

collisionRN(10000000, Math.pow(2, 32)) // 11632.50

使用下面代碼進行測試

private static Map<Integer, Set<String>> collisions(Set<String> values) {
	Map<Integer, Set<String>> result = new HashMap<>();
	for (String value : values) {
		Integer hashCode = value.hashCode();
		Set<String> bucket = result.computeIfAbsent(hashCode, k -> new TreeSet<>());
		bucket.add(value);
	}
	return result;
}

public static void main(String[] args) throws IOException {
        Set<String> uuids = new HashSet<>();
        for (int i = 0; i< 10000000; i++){
            uuids.add(UUID.randomUUID().toString());
        }
        Map<Integer, Set<String>> values = collisions(uuids);

        int maxhc = 0, maxsize = 0;
        for (Map.Entry<Integer, Set<String>> e : values.entrySet()) {
            Integer hashCode = e.getKey();
            Set<String> bucket = e.getValue();
            if (bucket.size() > maxsize) {
                maxhc = hashCode;
                maxsize = bucket.size();
            }
        }

        System.out.println("UUID總數: " + uuids.size());
        System.out.println("哈希值總數: " + values.size());
        System.out.println("碰撞總數: " + (uuids.size() - values.size()));
        System.out.println("碰撞機率: " + String.format("%.8f", 1.0 * (uuids.size() - values.size()) / uuids.size()));
        if (maxsize != 0) {
            System.out.println("最大的碰撞的字元串: " + maxsize + " " + values.get(maxhc));
        }
    }

碰撞總數11713非常接近理論值。

UUID總數: 10000000
哈希值總數: 9988287
碰撞總數: 11713
碰撞機率: 0.00117130

注意，上面測試不足以得出string.hashCode()性能結論，字元串情況很多，無法逐一覆寫。

對于JDK中的

hashCode

算法的優劣決定了它在哈希表的分布，我們可以通過估算理論值和實測值來不斷優化算法。

對于一些有名的雜湊演算法，比如FNV-1，Murmur2 網上有個文章專門對比了它們的碰撞機率，分布情況。

https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed

小結

哈希函數是将長資訊映射為長度固定的短資料，判斷一個哈希函數的好壞考量它的碰撞機率和哈希值的分布情況。

https://en.wikipedia.org/wiki/Birthday_problem