在HashMap中,key为null的entry会存储在下标0的位置,上面进行覆盖操作,来看addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) { /* JDK1.7以后的扩容条件；size大于等于threshold,并且新添加元素所在的索引值不等为空 也就是即使当size达到或超过threshold,新增加元素,只要不会引起hash冲突则不扩容; JDK1.8去掉了为null的判断 */ if ((size >= threshold) && (null != table[bucketIndex])) { //将大小扩容到原来的两倍 resize(2 * table.length); //如果key为null,将放到index为0的位置,否则进行取hash的操作 hash = (null != key) ? hash(key) : 0; //根据获取的hash值进行获取下标 bucketIndex = indexFor(hash, table.length); } //创建entry createEntry(hash, key, value, bucketIndex); }来看扩容resize()方法,传入的是2倍的旧数组的长度
void resize(int newCapacity) { //将旧table赋值给oldTable Entry[] oldTable = table; //获取旧table长度 int oldCapacity = oldTable.length; //如果长度已经等于最大限制设置为Integer的最大值 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //创建新table,长度为参数为传入的参数newCapacity Entry[] newTable = new Entry[newCapacity]; //该方法将oldTable的数据复制到了newTable transfer(newTable, initHashSeedAsNeeded(newCapacity)); //将新扩容的table改为当前hashmap的存储table table = newTable; //重新计算阈值 threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }在扩容方法中主要关注将数据转移的transfer方法
void transfer(Entry[] newTable, boolean rehash) { //获取新创建的table长度 int newCapacity = newTable.length; //遍历旧table for (Entry<K, V> e : table) { /*代码第一次判断如果当前下标entry是否为空, 如果为空则切换到下一个Entry节点 如果不为空,第二次就是判断当前下标的entry是否形成链表 如果形成链表将一直判断是否有下一个节点,当把该下标链表遍历完毕后, 然后切换到下一个entry节点进行相同的操作 * */ while (null != e) { //获取下一个entry Entry<K, V> next = e.next; if (rehash) { /** * 判断e.key是否为null,如果为null将e.hash赋值为0 * 否则调用hash()方法进行计算hash */ e.hash = null == e.key ? 0 : hash(e.key); } //通过当前遍历旧表的entry的hash值和新table的长度来获取在新表的下标位置 int i = indexFor(e.hash, newCapacity); /* * jdk1.7是进行头插法,也就是不需要知道当前下标位置是否存在Entry * 只需要将旧表中Entry节点,通过计算出下标位置 * 在新添加的Entry中直接将当前下标元素赋值给next属性,然后新添加的节点赋值给当前下标 */ e.next = newTable[i]; newTable[i] = e; e = next; } } }其中有几个需要关注的方法
//hash()======这个方法简单理解为来通过key来计算hash,在get时通过hash可以确保是同一个entry对象 final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded & ~ // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } //indexFor()=========== /** 这里使用&于运算符,两个相同为1返回1,否则返回0,例如 0010 1101 1010 1011 结果 0010 1001 */ static int indexFor(int h, int length) { return h & (length - 1); }我们现在回到resize扩容方法,这个方法中最主要的就是这个将旧数组中数据复制到新数组中这个transfer()方法了,其他的操作上面都有注释,对应着看应该可以看懂
这里再主要说一下indexFor方法,在初始化HashMap时为什么在设置初始大小的时候必须为2的倍数
下面以HashMap初始化大小为16为例
首先&运算符两都为1才为1,否则为0
假设hash值为....1010 1010 而现在hashmap的长度为16,即(16-1)=15
hash:1010 1010
15: 0000 1111
因为15的低四位为1,也就是说通过&位运算符能对结果造成影响的只有低四位的四个1,其他高为都为0
这也是hash()方法的用处尽量让其他位参与hash运算,达到更加分散的hash值
假设初始大小为单数,例如15,那么通过(length - 1);,结果为14,14的二进制为
0000 1110
那么和计算出的hash进行&运算能对结果进行影响的位数会减少1位,这还是好的情况,如果传入的初始大小为17那么会怎样?
17通过length-1的操作为16,16的二进制为0001 0000,那么再和hash值进行&的操作
hash: 1010 1010
16:
0001 0000
只有两种情况,0000 0000 和0001 0000 ,那么设置的hashmap的大小将毫无作用,
只会在0000 0000 和0001 0000 的位置进行put操作,而0000 0000 为0下标,用来添加null的key那么添加的数据将会全部添加 到16的位置!