Jdk1.7下的HashMap源码分析

常量属性

/**

* The default initial capacity - MUST be a power of two.

* 默认初始容量大小

*/staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;// aka 16/**

* MUST be a power of two <= 1<<30.

* hashMap最大容量，可装元素个数

*/staticfinalintMAXIMUM_CAPACITY =1<<30;/**

* The load factor used when none specified in constructor.

* 加载因子，如容量为16，默认阈值即为16*0.75=12,元素个数超过(包含)12且，扩容

*/staticfinalfloatDEFAULT_LOAD_FACTOR =0.75f;/**

* 空数组，默认数组为空，初始化后才才有内存地址，第一次put元素时判断，延迟初始化

*/staticfinalEntry[] EMPTY_TABLE = {};

2、存在的死循环问题

扩容导致的死循环，jdk1.7中在多线程高并发环境容易出死循环，导致cpu使用率过高问题，问题出在扩容方法resize()中,更具体内部的transfer方法：将旧数组元素转移到新数组过程中,源码如下：

voidresize(intnewCapacity){ Entry[] oldTable = table;intoldCapacity = oldTable.length;//1.如果原来数组容量等于最大值了，2^30,设置扩容阈值为Integer最大值，不需要再扩容if(oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE;return; }//2.创建新数组对象 Entry[] newTable =newEntry[newCapacity];//3.将旧数组元素转移到新数组中,分析一transfer(newTable, initHashSeedAsNeeded(newCapacity));//4.重新引用新数组对象和计算新的阈值table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY +1);}

transfer方法

/**

* Transfers all entries from current table to newTable.

* 从当前数组中转移所有的节点到新数组中

*/voidtransfer(Entry[] newTable,booleanrehash){intnewCapacity = newTable.length;//遍历旧数组for(Entry e : table) {//1,首先获取数组下标元素while(null!= e) {//2.获取数组该桶位置链表中下一个元素Entry next = e.next;//3.是否需要重新该元素key的hash值if(rehash) { e.hash =null== e.key ?0: hash(e.key); }//4，重新确定在新数组中下标位置inti = indexFor(e.hash, newCapacity);//5.头插法：插入新链表该桶位置，若有元素，就形成链表，每次新加入的节点都插在第一位，就数组下标位置e.next = newTable[i]; newTable[i] = e;//6.继续获取链表下一个元素 e = next; } }}//传入容量值返回是否需要对key重新HashfinalbooleaninitHashSeedAsNeeded(intcapacity){//1.hashSeed默认为0,因此currentAltHashing为falsebooleancurrentAltHashing = hashSeed !=0;//2,sun.misc.VM.isBooted()在类加载启动成功后，状态会修改为true// 因此变数在于，capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD，debug发现正常情况ALTERNATIVE_HASHING_THRESHOLD是一个很大的值,使用的是Integer的最大值booleanuseAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//3,两者异或，只有不相同时才为true，即useAltHashing =true时，dubug代码发现useAltHashing =false，booleanswitching = currentAltHashing ^ useAltHashing;if(switching) { hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) :0; }//正常情况下是返回false，即不需要重新对key哈希returnswitching;}

代码如下：

publicVput(K key, V value){//1,若当前数组为空，初始化if(table == EMPTY_TABLE) {//分析1inflateTable(threshold); }//2,若put的key为null,在放置在数组下标第一位，索引为0位置，从该源码可知// hashMap允许键值对 key=null,但是只能有唯一一个if(key ==null)// 分析2returnputForNullKey(value);//3,计算key的hash，这里与1.8有区别 //分析3 inthash = hash(key);// 4,确定在数组下标位置，与1.8相同inti = indexFor(hash, table.length);// 5，遍历该数组位置,即该桶处遍历for(Entry e = table[i]; e !=null; e = e.next) { Object k;if(e.hash == hash && ((k = e.key) == key || key.equals(k))) {// 找到相同的key，则覆盖原value值，返回旧值V oldValue = e.value; e.value = value;//该方法为空，不用看e.recordAccess(this);returnoldValue; } }//因为hashMap线程不安全，修改操作没有同步锁，//该字段值用于记录修改次数，用于快速失败机制 fail-fast,防止其他线程同时做了修改，抛出并发修改异常modCount++;// 6,原数组中没有相同的key，以头插法插入新的元素//分析4addEntry(hash, key, value, i);returnnull;}

分析1: HashMap如何初始化数组的，延迟初始化有什么好处？

结论： 1、1.7,1.8都是延迟初始化，在put第一个元素时创建数组，目的是为了节省内存。

初始化代码：

privatevoidinflateTable(inttoSize){// Find a power of 2 >= toSize//1.该方法非常重要，目的为了得到一个比toSize最接近的2的幂次方的数，// 且该数要>=toSize,这个2的幂次方方便后面各种位运算// 如：new HashMap(15),指定15大小集合，内部实际创建数组大小为2^4=16// 分析见下intcapacity = roundUpToPowerOf2(toSize);//2，确定扩容阈值threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +1);//3，初始化数组对象table =newEntry[capacity]; initHashSeedAsNeeded(capacity);}

Q:如何确保获取到比toSize 最接近且大于等于它的2的幂次方的数？

深入理解roundUpToPowerOf2方法:

privatestaticintroundUpToPowerOf2(intnumber){// assert number >= 0 : "number must be non-negative";//如果number大于等于最大值 2^30，赋值为最大，主要是防止传参越界，number一定是否非负的 returnnumber >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number >1) ? Integer.highestOneBit((number -1) <<1) :1;//核心在于Integer.highestOneBit((number - 1) << 1) 此处}

先抛出2个问题：

1：这个（number - 1) << 1 的作用是什么？

2：这个方法highestOneBit肯定是为了获取到满足条件的2的幂次方的数，背后的原理呢？

结论： Integer的方法highestOneBit(i) 这个方法是通过位运算，获取到i的二进制位最左边（最高位）的1，其余位都抹去，置为0，即获取的是小于等于i的2的幂次方的数.

如果直接传入number,那么获取到的是2的幂次方的数，但是该数一定小于等于number，但这不是我们的目的；

如highestOneBit(15)=8highestOneBit(21)=16而我们是想要获取一个刚刚大于等于number的2次方的数，(number-1)<<1 因此需要先将number 扩大二倍number <<1 , 为什么需要number-1,是考虑到临界值问题，恰好number本身就是2的幂次方，如 number=16，扩大2倍后为32， highestOneBit方法计算后结果还是32，这不符合需求。

publicstaticinthighestOneBit(inti){// HD, Figure 3-1i |= (i >>1); i |= (i >>2); i |= (i >>4); i |= (i >>8); i |= (i >>16);returni - (i >>>1);}

2的幂次方二进值特点：只有最高位为1，其他位全为0

目的：将传入i的二进制最左边的1保留，其余低位的1全变为0

原理：某数二进制： 0001 ,不关心其低位是什么，以*代替，进行运算

深圳网站建设www.sz886.com