HashMap初始化参数剖析

HashMap除了有无参的构造方法（默认会构造出一个默认为16的数组及loadFactor=0.75的HashMap)外，也可以在New  HaspMap的时候指定这两个值。原构造方法声明如下：

HashMap(int initialCapacity, float loadFactor) 
          Constructs an empty HashMap with the specified initial capacity and load factor.

 

第一个参数：initialCapacity，初始化容量。

第二个参数：loadFactor，重新加载比例。即当Map的容量小于initialCapacity*loadFactor的时候，进行扩容。扩容就意味着重新申请更大的内存，对原来的数据进行重hash。显然是一件很浪费时间的问题。

 

 

通常情况下，我们可能需要将一个List里面的东西，转化成一个HashMap来进行进一步的运算。这个时候，我们可以调用List.size获得元素的数量，这样，我们就可以在构造一个HashMap的时候就指定他的大小。

比如：

Map<Long,Object> data = new HashMap<Long,Object>(list.size,1f)

 我们认为，这样初始化化HashMap就会省去中间Map因默认的16数组不够导致的resize和rehash，性能会高点。

 

 

你可能会认为，如果你这样写，初始化容量就是list.size。

 那你就大错特错了。我们看看HashMap的源码：

 // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1; //此处的意思就是不断的加倍扩展
        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];

 从代码可以看出，hashMap的大小只可能是2,4,8,16,32,128,....1024......等大小，也就是2的n次方大小，如果你的list里面不幸是129个元素，那么HashMap就会创建一个256的数组。就是这么悲催。

不过，指定大小肯定比不知道大小，性能要高点。

 

为啥hash的数组非得要2的n次方呢？因为Hashmap进行hash后取数组坐标的时候是这样运算的。

  static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

如果length为非2的n次方。比如是3，那么3-1的二进制位0010，其hash后的坐标除了table[2]外，其他的都hash到table[0]上面了。

也就是说，如果非2的n次方的话，hash定位的时候冲突就会成倍增长。

综上所述，我们在使用HashMap的时候，如果知道hash的key的数量的话，尽量指定hash的initialCapacity和loadFactor。这样能够提高性能。另外，loadFactor,理想情况下1是最好的，因为你已经知道总大小，如果hash的算法足够好的话，正好能够将所有的值都无冲突的hash到正确位置，这样的话不用resize；如果hash算法算法不够好，冲突多，那么数组肯定有剩余，也不用再resize。

 

好了，写这个纯粹为一时兴起。但这个同时也引起了我对另一个问题的探索，就是String的hashcode重复的概率。

因为String的hashcode，代码是这样：

public int hashCode() {
int h = hash;//默认0
if (h == 0) {
    int off = offset;//默认0
    char val[] = value;//字符串是用字符数组表示的.
    int len = count;//字符串长度
            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
 }

 

 

哪个问题，我就再写一篇吧。

 

参考资料：

http://blog.csdn.net/sgbfblog/article/details/7580510

 

 

 

请支持原创：

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

 

 

 

 

 

对这类话题感兴趣？欢迎发送邮件至[e-mail]

关于我：邯郸人，擅长Java，Javascript，Extjs，oracle sql。

更多我之前的文章，可以访问 我的空间

 

评论

2 楼 donlianli 2013-11-21  

jahu 写道

请你去看下，hashmap的api，，说的什么啊。随便弄一点东西出来就写。有意思吗？

有理解错误的，欢迎指出。你说的hashmap的api指得是什么？

1 楼 jahu 2013-11-21  

请你去看下，hashmap的api，，说的什么啊。随便弄一点东西出来就写。有意思吗？