大龍的博客

留言簿(43)

收藏夾

ps (rss)

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 864
文章 - 2
評論 - 378
引用 - 0

hashcode重復的可能性超大(轉)

用String的hashcode得到int類型作為主鍵。其實hashcode重復的可能性超大，下面是java的缺省算法：

public int hashCode() {

int h = hash;

if (h == 0) {

int off = offset;

char val[] = value;

int len = count;

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

h = 31*h + val[off++];

}

hash = h;

}

return h;

}

但是什么情況下會重復？下面是測試代碼

import java.util.HashMap;

public class Test {

static HashMap map = new HashMap();

private static char startChar = 'A';

private static char endChar = 'z';

private static int offset = endChar - startChar + 1;

private static int dup = 0;

public static void main(String[] args) {

int len = 3;

char[] chars = new char[len];

tryBit(chars, len);

System.out.println((int)Math.pow(offset, len) + ":" + dup);

}

private static void tryBit(char[] chars, int i) {

for (char j = startChar; j <= endChar; j++) {

chars[i - 1] = j;

if (i > 1)

tryBit(chars, i - 1);

else

test(chars);

}

private static void test(char[] chars) {

String str = new String(chars).replaceAll("[^a-zA-Z_]", "").toUpperCase();// 195112:0

//String str = new String(chars).toLowerCase();//195112:6612

//String str = new String(chars).replaceAll("[^a-zA-Z_]","");//195112:122500

//String str = new String(chars);//195112:138510

int hash = str.hashCode();

if (map.containsKey(hash)) {

String s = (String) map.get(hash);

if (!s.equals(str)) {

dup++;

System.out.println(s + ":" + str);

}

} else {

map.put(hash, str);

// System.out.println(str);

}

在A-z范圍內有特殊字符，從結果看，僅僅3位長度的字符串：
不處理：　138510次重復
去掉字母意外字符：　122500次重復
所有字符轉小寫：6612次重復(少了很多）
去掉字母意外字符，并且轉小寫：沒有重復！4位字符串也沒見重復

不難看出：
1. 缺省實現為英文字母優化
2. 字母大小寫可能導致重復

可能：
長字符串可能hashcode重復
中文字符串和特殊字符可能hashcode重復

注：由于是2006年的事，所以上面得出的數據有誤。可自己進行測試。hash沖突次數大大減少。

posted on 2014-08-31 14:59 大龍閱讀(959) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品