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

2021 年 11 月 8 日
筆記

哈希函數

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

用於哈希表的哈希函數。比如布隆過濾里的哈希函數，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 網上有個帖子專門對比了它們的碰撞概率，分布情況。

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

小結

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

//en.wikipedia.org/wiki/Birthday_problem