love fish大鵬一曰同風起，扶搖直上九萬里

公告

留言簿(15)

隨筆分類(493)

隨筆檔案(498)

相冊

MIX

閱讀排行榜

常用鏈接

統計

隨筆 - 500
文章 - 0
評論 - 155
引用 - 0

積分與排名

積分 - 529056
排名 - 91

friends

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重復

posted on 2006-06-25 10:34 liaojiyong 閱讀(1461) 評論(0) 編輯收藏所屬分類: Java

新用戶注冊刷新評論列表


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




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 能為你的程序錦上添花的幾種程序結構（轉） Java虛擬機運行機制(轉) JDK6的新特性(轉) 求兩時間點之間日期差的簡潔方法（轉）代碼發現的問題及解決方案（轉） serialVersionUID 最弱智的搜索字符串算法 Java1.5泛型指南中文版(Java1.5 Generic Tutorial) （轉） Java文件操作大全（轉） JFreeChat的介紹（轉）