关于HashMap的负载因子 load factor

Question

本帖最后由 qian119110 于 2010-12-21 20:19:58 编辑

Answer 1

如果负载因子是默认的0.75，HashMap(16)的时候，占16个内存空间，实际上只用到了12个，超过12个就扩容。
如果负载因子是1的话，HashMap(16)的时候，占16个内存空间，实际上会填满16个以后才会扩容。但是，用到的空间越多，hashcode重复的可能性就越大，同一个空间里面的元素数目就可能会增加，会增加查找的时间。

Answer 2

那为什么说增大负载因子可以减少hash表的内存，
不是容量极限扩大了吗？

Answer 3

如果负载因子是0.75，hashmap(16)最多可以存储12个元素，想存第16个就得扩容成32。
如果负载因子是1，hashmap(16)最多可以存储16个元素。同样存16个元素，一个占了32个空间，一个占了16个空间的内存。

Answer 4

那假如现在有132个键值对（12的倍数）
负载因子是0.75 占 132个空间
负载因子1      占144个空间
负载因子大的反而多占用空间，
怎么能得出增大负载因子可以减少Hash表所占用的内存空间这个结论呢.

Answer 5

好吧 先说说我的理解，错误的请纠正
我现在的理解，增大负载因子可以减少hash表的内存空间，
这个内存空间指的是初始容量initialCapacity构造hash表所产生的空间，
在容量极限(threshold）一定时，负载因子越大，则实际容量（capacity）越小，即所需初始容量（initialCapacity）越小，则初始构造的hash表所占空间越小。增大负载因子会增加查询数据的时间开销，
肯定是多产生了Entry链。
在发生"hash冲突"情况下（即hashCode相同 equals不同），会产生Entry链，
当要查找时，遍历Entry链花的时间多。
但是这个和空间有什么关系？
Entry即键值对数组所占的空间少，为什么发生的hash冲突变多了？

Answer 6

Entry数组所占空间变少，为什么hash冲突变多了？
hashCode的计算方法没变，不应该多产生Entry链啊。

Answer 7

楼主可以先看看HashSet这个数据结构，比HashMap稍微简单一些。采用Hash散列进行存储，主要就是为了提高检索速度。众所周知，
有序数组存储数据，对数据的检索效率会很高，但是，插入和删除会有瓶颈产生。
链表存储数据，通常只能采用逐个比较的方法来检索数据（查找数据），但是，插入和删除的效率很高。于是，将两者结合，取长补短，优势互补一下，就产生哈希散列这种存储方式。具体是怎么样的呢？
我们可以理解成，在链表存储的基础上，对链表结构进行的一项改进。
我们将一个大的链表，拆散成几个或者几十个小的链表。
每个链表的表头，存放到一个数组里面。这样，在从大链表拆分成小链表的时候就有讲究了。
我们按照什么规则来将一个大链表中的数据，分散存放到不同的链表中呢？
在计算机当中，肯定是要将规则数量化的，也就是说，这个规则，一定要是个数字，这样才比较好操作。
比如，按照存放时间，每5分钟一个时间段，将相同时间段存放的数据，放到同一个链表里面；
或者，将数据排序，每5个数据形成一个链表；
等等，等等，还有好多可以想象得到的方法。
但是，这些方法都会存在一些不足之处。
我们就在想了，如果存放的数据，都是整数就好了。
这样，我可以创建一个固定大小的数组，比如50个大小，然后，让数据（整数）对50进行取余运算，
然后，这些数据，自然就会被分成50个链表了，每个链表可以是无序的，反正链表要逐个比较进行查询。
如果，我一个有200个数据，分组后，平均每组也就4个数据，那么，链表比较，平均也就比较4次就好了。
但是，实际上，我们存放的数据，通常都不是整数。
所以，我们需要将数据对象映射成整数的一个算法。
HashCode方法，应运而生了。
每个数据对象，都会对应一个HashCode值，通过HashCode我们可以将对象分组存放到不同的队列里。
这样，在检索的时候，就可以减少比较次数。在实际使用当中，HashCode方法、数组的大小 以及 数据对象的数量，这三者对检索的性能有着巨大的影响。
1.如果数组大小为1，那和链表存储没有什么区别了，
而且，还多了一步计算HashCode的时间，所以，数组不能太小，太小查询费时间。
2.如果我只存放1个数据对象，数组又非常大，那么，数组所占的内存空间，就比数据对象占的空间还大，
这样，少量数据对象，巨大的数组，虽然能够使检索速度，但是，浪费了很多内存空间。
3.如果所有对象的HashCode值都是相同的数，
那么，无论数组有多大，这些数据都会保存到同一个链表里面，
一个好的HashCode算法，可以使存放的数据，有较好的分散性，
在实际的实现当中，HashSet和HashMap都对数据对象产生的HashCode进行了二次散列处理，
使得数据对象具有更好的分散性。上述的1和2就是楼主的问题。以上纯属个人见解，请大家多多指教。

Answer 8

当你调用map.get("abc")时，是按hashcode进行检索的，可是hashcode如何得到呢？
hashcode是存放在一个数组里，hashcode的访问是按照数组的序号来访问的，这里是计算hashcode的，
 static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
而这里，就是计算每个hashcode的数组序号的,length就是那个数组的长度。
static int indexFor(int h, int length) {
        return h & (length-1);
    }如果有不同的hashcode被放在了相同的indexFor下面，就产生hash冲突，就是e!=null,解决hash冲突有许多种方法，而这里是往下继续查找，直到找到为null的值。建议LZ看看hash表数据结构。

Answer 9

那个负载因子(load factor)是时间和空间的一种折中  如果增大load factor 可以减少hash表所占用的内存空间,但会增加查询的时间开销