大龍的博客

導(dǎo)航

<

2007年4月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

留言簿(43)

收藏夾

ps (rss)

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統(tǒng)計(jì)

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

hashcode重復(fù)的可能性超大(轉(zhuǎn))

用String的hashcode得到int類型作為主鍵。其實(shí)hashcode重復(fù)的可能性超大，下面是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;

}

但是什么情況下會(huì)重復(fù)？下面是測試代碼

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范圍內(nèi)有特殊字符，從結(jié)果看，僅僅3位長度的字符串：
不處理：　138510次重復(fù)
去掉字母意外字符：　122500次重復(fù)
所有字符轉(zhuǎn)小寫：6612次重復(fù)(少了很多）
去掉字母意外字符，并且轉(zhuǎn)小寫：沒有重復(fù)！4位字符串也沒見重復(fù)

不難看出：
1. 缺省實(shí)現(xiàn)為英文字母優(yōu)化
2. 字母大小寫可能導(dǎo)致重復(fù)

可能：
長字符串可能hashcode重復(fù)
中文字符串和特殊字符可能hashcode重復(fù)

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

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

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




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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