江苏龙网

  1. 首页 > 人文 > >

详解HashMap集合( 三 )

问题： 为什么必须是2的n次幂？如果输入值不是2的幂比如10会怎么样？
HashMap构造方法还可以指定集合的初始化容量大小：
HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap 。 根据上述讲解我们已经知道 ， 当向HashMap中添加一个元素的时候 ， 需要根据key的hash值 ， 去确定其在数组中的具体位置 。HashMap为了存取高效 ， 要尽量较少碰撞 ， 就是要尽量把数据分配均匀 ， 每个链表长度大致相同 ， 这个实现就在把数据存到哪个链表中的算法 。
这个算法实际就是取模 ， hash%length ， 计算机中直接求余效率不如位移运算(这点上述已经讲解) 。 所以源码中做了优化,使用 hashpublic HashMap(int initialCapacity) {//initialCapacity=10this(initialCapacity, DEFAULT_LOAD_FACTOR); }public HashMap(int initialCapacity, float loadFactor) {//initialCapacity=10if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10}/*** Returns a power of two size for the given target capacity.*/static final int tableSizeFor(int cap) {//int cap = 10int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}说明：
由此可以看到 ， 当在实例化HashMap实例时 ， 如果给定了initialCapacity(假设是10) ， 由于HashMap的capacity必须都是2的幂 ， 因此这个方法用于找到大于等于initialCapacity(假设是10)的最小的2的幂（initialCapacity如果就是2的幂 ， 则返回的还是这个数） 。下面分析这个算法： 1)、首先 ， 为什么要对cap做减1操作 。 int n = cap - 1; 这是为了防止 ， cap已经是2的幂 。 如果cap已经是2的幂 ，又没有执行这个减1操作 ， 则执行完后面的几条无符号右移操作之后 ， 返回的capacity将是这个cap的2倍 。 如果不懂 ， 要看完后面的几个无符号右移之后再回来看看 。下面看看这几个无符号右移操作： 2）、如果n这时为0了（经过了cap-1之后） ， 则经过后面的几次无符号右移依然是0 ， 最后返回的capacity是 1（最后有个n+1的操作） 。这里只讨论n不等于0的情况 。
3）、注意：|（按位或运算）：运算规则：相同的二进制数位上 ， 都是0的时候 ， 结果为0 ， 否则为1 。
第一次右移 ：
int n = cap - 1;//cap=10n=9n |= n >>> 1;00000000 00000000 00000000 00001001 //9|00000000 00000000 00000000 00000100 //9右移之后变为4-------------------------------------------------00000000 00000000 00000000 00001101 //按位异或之后是13由于n不等于0 ， 则n的二进制表示中总会有一bit为1 ， 这时考虑最高位的1 。 通过无符号右移1位 ， 则将最高位的1右移了1位 ， 再做或操作 ， 使得n的二进制表示中与最高位的1紧邻的右边一位也为1 ， 如：
00000000 00000000 00000000 00001101第二次右移 ：
n |= n >>> 2;//n通过第一次右移变为了：n=1300000000 00000000 00000000 00001101// 13|00000000 00000000 00000000 00000011//13右移之后变为3-------------------------------------------------00000000 00000000 00000000 00001111 //按位异或之后是15


推荐阅读


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

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