(转）谨慎使用String作为HashMap的Key

http://donlianli.iteye.com/blog/1979674

首先简单复习一下哈希表知识（大学课本定义）。
        根据设定的哈希函数f(key)和处理冲突的方法将一组关键字映像到一个有限的连续地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表。
         哈希函数f(key)是一个映像，使得任何关键字由此所得到的哈希函数值都落在表允许范围之内。
         对不同的关键字可能得到同一哈希地址，即key!=key2，但是f(key1)=f(key2)，这种现象称为冲突。一般情况下，冲突只能减少，而不能完全避免。

还不清楚？请百科普及一下吧。


通过上面的复习，我们知道，决定一个哈希表的性能主要是哈希表的键值的冲突概率。如果哈希后的冲突很低，性能就高，相反，性能则低。使用一个好的哈希算法，可以降低哈希冲突的概率，提高命中率。

但是，如果被哈希的Key本身就是重复的，那么哈希算法再好，也无法避免哈希值的冲突。

我们都知道，在Java中，HashMap一般是使用对象的hashcode作为哈希的Key的。那么使用String作为HashMap的Key，好不好呢？或者，你在不知情的情况一下，已经干过很多次了。

String的hashCode方法。

Java代码  收藏代码
public int hashCode() { 
    int h = hash; 
        int len = count; 
    if (h == 0 && len > 0) { 
        int off = offset; 
        char val[] = value; 
 
            for (int i = 0; i < len; i++) { 
                h = 31*h + val[off++]; 
            } 
            hash = h; 
        } 
        return h; 
    } 


核心的代码就一行。就是

Java代码  收藏代码
h = 31*h + val[off++]; 
他的意思就是一个字符串的hashcode，就是逐个按照字符的utf-16的编码值求和。

我个人觉得，像这样的计算hashcode的话，各个字符串很容易重复（虽然我数学不好）。比如："C9"和“Aw”
的hashcode都是2134。这样的长度为2位的字符串，我用程序统计了一下，重复的概率大概是0.6665928。

当字符长度为3个字符时，重复的概率成上升趋势，达到0.8911293，4位时为0.9739272。当然，5位长度的概率我不知道，因为我的机器上跑不出来结果。
测试代码见附1。

这么高的重复率，如果你使用它作为hashcode的话，势必会造成很大的哈希冲突，从而降低哈希表最初的设计初衷，性能降低。

但是，那String设计的时候，为啥这样设计hashcode呢？我经过测试，当字符串仅为数字时，多长的字符串，hashcode都不会重复。这是为什么呢？

从他计算的公式的31的系数看，应该是31为一个跨度，即只要字符串中的字符串的跨度在31个之内，hash值就不会重复，经过测试，确实如此。也就是说，如果你使用纯英文大写或纯英文小写字母拼接起来的字符串，其hashcode一般不会重复的。不知道这个31最初是怎么算出来的，但是，毋庸置疑，我们可以通过重新String的hashcode方法，将31改为128，那么冲突就会大大降低。

看看可能会作为Key的情况。
1、MD5，一般是字母加数字，字符跨度为75.
2、oracle的sys_guid()产生的逐渐，字符跨度为43.
3、java的UUID，跨度为75.
4、其他唯一主键情况。

建议，如果你的对象主键是上述类型，则尽量少的使用HashMap作为进行运算的工具类。

因此，当你打算使用String作为HashMap的Key时，我建议两点：
1、如果你不知道你的Key的可能的取值范围是否超过31，并且不知数量是多大时，尽量不要使用。
2、如果你对性能要求很高，请尽量不要将字符串作为主键。


附1：计算字符串重复概率的代码
Java代码  收藏代码
import java.util.HashMap; 
/**
* 测试字符串的hashcode重复几率
* @author [email protected]
*/ 
public class StringHashCode { 
     
    static HashMap<Integer,Object> map = new HashMap<Integer,Object>();  
    /**
     * 第一个可见字符
     */ 
    private static char startChar = ' ';  
    /**
     * 最后一个可见字符
     */ 
    private static char endChar = '~';  
    private static int offset = endChar - startChar + 1;  
    /**
     * 重复次数
     */ 
    private static int dupCount = 0;  
     
    public static void main(String[] args) {  
        for(int len=1;len<5;len++){ 
             char[] chars = new char[len];  
             tryBit(chars, len);  
             int total=(int)Math.pow(offset, len); 
             System.out.println(len+":"+total + ":" + dupCount+":"+map.size()+":"+(float)dupCount/total); 
        } 
         
    }  
  
    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) {  
        Integer key = new String(chars).hashCode(); 
        if (map.containsKey(key)) {  
            dupCount++;  
        } else {  
            map.put(key, null);  
        }  
    }  
} 

附2：计算字符串为长度为2的重复hashcode的代码


Java代码  收藏代码
import java.util.HashMap; 
/**
* 测试字符串的hashcode重复几率
* @author [email protected]
* 求长度为2的hashcode重复的字符串
*/ 
public class PrintStringHashCode { 
     
    static HashMap<Integer,Object> map = new HashMap<Integer,Object>();  
    /**
     * 第一个可见字符
     */ 
    private static char startChar = ' ';  
    /**
     * 最后一个可见字符
     */ 
    private static char endChar = 'z';  
    private static int offset = endChar - startChar + 1;  
    /**
     * 重复次数
     */ 
    private static int dupCount = 0;  
     
    public static void main(String[] args) {  
        int len =2; 
         char[] chars = new char[len];  
         tryBit(chars, len);  
         int total=(int)Math.pow(offset, len); 
         System.out.println(len+":"+total + ":" + dupCount+":"+map.size()+":"+(float)dupCount/total); 
    }  
  
    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 s = new String(chars); 
        Integer key = s.hashCode(); 
        if (map.containsKey(key)) {  
            dupCount++;  
            System.out.println(map.get(key)+" same :"+s+" hashcode:"+key); 
        } else {  
            map.put(key, s);  
        }  
    }  
} 

已有 0 人发表留言，猛击->> 这里<<-参与讨论


ITeye推荐

• —软件人才免语言低担保 赴美带薪读研！—