江苏龙网

  1. 首页 > 人文 > >

详解HashMap集合( 六 )

13、 哈希表的加载因子(重点)
// 加载因子final float loadFactor;说明：
1.loadFactor加载因子 ， 是用来衡量 HashMap 满的程度 ， 表示HashMap的疏密程度 ， 影响hash操作到同一个数组位置的概率 ， 计算HashMap的实时加载因子的方法为：size/capacity ， 而不是占用桶的数量去除以capacity 。 capacity 是桶的数量 ， 也就是 table 的长度length 。
loadFactor太大导致查找元素效率低 ， 太小导致数组的利用率低 ， 存放的数据会很分散 。 loadFactor的默认值为0.75f是官方给出的一个比较好的临界值 。
当HashMap里面容纳的元素已经达到HashMap数组长度的75%时 ， 表示HashMap太挤了 ， 需要扩容 ， 而扩容这个过程涉及到 rehash、复制数据等操作 ， 非常消耗性能 。， 所以开发中尽量减少扩容的次数 ， 可以通过创建HashMap集合对象时指定初始容量来尽量避免 。
同时在HashMap的构造器中可以定制loadFactor 。
构造方法：HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap 。 2.为什么加载因子设置为0.75,初始化临界值是12？
loadFactor越趋近于1 ， 那么 数组中存放的数据(entry)也就越多 ， 也就越密 ， 也就是会让链表的长度增加 ， loadFactor越小 ， 也就是趋近于0 ， 数组中存放的数据(entry)也就越少 ， 也就越稀疏 。
如果希望链表尽可能少些 。 要提前扩容 ， 有的数组空间有可能一直没有存储数据 。 加载因子尽可能小一些 。
举例：
例如：加载因子是0.4 。那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了 。加载因子是0.9 。那么16*0.9---->14 那么这样就会导致链表有点多了 。 导致查找元素效率低 。 所以既兼顾数组利用率又考虑链表不要太多 ， 经过大量测试0.75是最佳方案 。

  • threshold计算公式：capacity(数组长度默认16) * loadFactor(负载因子默认0.75) 。 这个值是当前已占用数组长度的最大值 。 当Size>=threshold的时候 ， 那么就要考虑对数组的resize(扩容) ， 也就是说 ， 这个的意思就是 衡量数组是否需要扩增的一个标准 。扩容后的 HashMap 容量是之前容量的两倍.
4.2构造方法HashMap 中重要的构造方法 ， 它们分别如下：
1、构造一个空的 HashMap， 默认初始容量（16）和默认负载因子（0.75） 。
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的加载因子0.75赋值给loadFactor ， 并没有创建数组}2、 构造一个具有指定的初始容量和默认负载因子（0.75） HashMap 。
// 指定“容量大小”的构造函数public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}3、 构造一个具有指定的初始容量和负载因子的 HashMap 。 我们来分析一下 。
/*指定“容量大小”和“加载因子”的构造函数initialCapacity: 指定的容量loadFactor:指定的加载因子*/public HashMap(int initialCapacity, float loadFactor) {//判断初始化容量initialCapacity是否小于0if (initialCapacity < 0)//如果小于0 ， 则抛出非法的参数异常IllegalArgumentExceptionthrow new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次幂if (initialCapacity > MAXIMUM_CAPACITY)//如果超过MAXIMUM_CAPACITY ， 会将MAXIMUM_CAPACITY赋值给initialCapacityinitialCapacity = MAXIMUM_CAPACITY;//判断负载因子loadFactor是否小于等于0或者是否是一个非数值if (loadFactor <= 0 || Float.isNaN(loadFactor))//如果满足上述其中之一 ， 则抛出非法的参数异常IllegalArgumentExceptionthrow new IllegalArgumentException("Illegal load factor: " +loadFactor);//将指定的加载因子赋值给HashMap成员变量的负载因子loadFactorthis.loadFactor = loadFactor;/*tableSizeFor(initialCapacity) 判断指定的初始化容量是否是2的n次幂 ， 如果不是那么会变为比指定初始化容量大的最小的2的n次幂 。 这点上述已经讲解过 。但是注意 ， 在tableSizeFor方法体内部将计算后的数据返回给调用这里了 ， 并且直接赋值给threshold边界值了 。 有些人会觉得这里是一个bug,应该这样书写：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容） 。但是 ， 请注意 ， 在jdk8以后的构造方法中 ， 并没有对table这个成员变量进行初始化 ， table的初始化被推迟到了put方法中 ， 在put方法中会对threshold重新计算 ， put方法的具体实现我们下面会进行讲解*/this.threshold = tableSizeFor(initialCapacity);}最后调用了tableSizeFor ， 来看一下方法实现：/*** Returns a power of two size for the given target capacity.返回比指定初始化容量大的最小的2的n次幂*/static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n


推荐阅读


上一篇：正确使用#include语句的双引号形式和角括号形式

下一篇：带你揭开BFC的神秘面纱