三、为何 HashMap 的数组长度一定是 2 的次幂？
我们来继续看上面提到的 resize 方法
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index 也可能会发生变化，需要重新计算 index，我们先来看看 transfer 这个方法
void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已） for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。 e.next = newTable[i]; newTable[i] = e; e = next; } } }
这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过 对 key 值的 hashcode 进行 hash 扰乱运算后，再通过和 length-1 进行位运算得到最终数组索引位置。
HashMap 的数组长度一定保持 2 的次幂，比如 16 的二进制表示为 10000，那么 length-1 就是 15，二进制为 01111，同理扩容后的数组长度为 32，二进制表示为 100000，length-1 为 31，二进制表示为 011111。从下图可以我们也能看到这样会保证低位全为 1，而扩容后只有一位差异，也就是多出了最左位的 1，这样在通过 h&(length-1) 的时候，只要 h 对应的最左边的那一个差异位为 0，就能保证得到的新的数组索引和老数组索引一致 (大大减少了之前已经散列良好的老数组的数据位置重新调换)，个人理解。
还有，数组长度保持 2 的次幂，length-1 的低位都为 1，会使得获得的数组索引 index 更加均匀
我们看到，上面的 & 运算，高位是不会对结果产生影响的（hash 函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位 bit，如果低位全部为 1，那么对于 h 低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到 index=21 这个存储位置，h 的低位只有这一种组合。这也是数组长度设计为必须为 2 的次幂的原因。
如果不是 2 的次幂，也就是低位不是全为 1 此时，要使得 index=21，h 的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index 对应的这个 bit 位无论如何不会等于 1 了，而对应的那些数组位置也就被白白浪费了。
get 方法：
public V get(Object key) { //如果key为null,则直接去table[0]处去检索即可。 if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); }
get 方法通过 key 值返回对应 value，如果 key 为 null，直接去 table [0] 处检索。我们再看一下 getEntry 这个方法
final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } //通过key的hashcode值计算hash值 int hash = (key == null) ? 0 : hash(key); //indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
可以看出，get 方法的实现相对简单，key (hashcode)–>hash–>indexFor–> 最终索引位置，找到对应位置 table [i]，再查看是否有链表，遍历链表，通过 key 的 equals 方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash 这个判断没必要，仅通过 equals 判断就可以。其实不然，试想一下，如果传入的 key 对象重写了 equals 方法却没有重写 hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用 equals 判断可能是相等的，但其 hashCode 和当前对象不一致，这种情况，根据 Object 的 hashCode 的约定，不能返回当前对象，而应该返回 null，后面的例子会做出进一步解释。
四、重写 equals 方法需同时重写 hashCode 方法
最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写 equals 时也要同时覆盖 hashcode”，我们举个小例子来看看，如果重写了 equals 而不重写 hashcode 会发生什么样的问题
public class MyTest { private static class Person{ int idCard; String name; public Person(int idCard, String name) { this.idCard = idCard; this.name = name; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()){ return false; } Person person = (Person) o; //两个对象是否等值，通过idCard来确定 return this.idCard == person.idCard; } } public static void main(String []args){ HashMap<Person,String> map = new HashMap<Person, String>(); Person person = new Person(1234,"乔峰"); //put到hashmap中去 map.put(person,"天龙八部"); //get取出，从逻辑上讲应该能输出“天龙八部” System.out.println("结果:"+map.get(new Person(1234,"萧峰"))); } } 实际输出结果：null
如果我们已经对 HashMap 的原理有了一定了解，这个结果就不难理解了。尽管我们在进行 get 和 put 操作的时候，使用的 key 从逻辑上讲是等值的（通过 equals 比较是相等的），但由于没有重写 hashCode 方法，所以 put 操作时，key (hashcode1)–>hash–>indexFor–> 最终索引位置 ，而通过 key 取出 value 的时候 key (hashcode1)–>hash–>indexFor–> 最终索引位置，由于 hashcode1 不等于 hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值 null（也有可能碰巧定位到一个数组位置，但是也会判断其 entry 的 hash 值是否相等，上面 get 方法中有提到。）
所以，在重写 equals 的方法的时候，必须注意重写 hashCode 方法，同时还要保证通过 equals 判断相等的两个对象，调用 hashCode 方法要返回同样的整数值。而如果 equals 判断不相等的两个对象，其 hashCode 可以相同（只不过会发生哈希冲突，应尽量避免）。
五、JDK1.8 中 HashMap 的性能优化
假如一个数组槽位上链上数据过多（即拉链过长的情况）导致性能下降该怎么办？
JDK1.8 在 JDK1.7 的基础上针对增加了红黑树来进行优化。即当链表超过 8 时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高 HashMap 的性能，其中会用到红黑树的插入、删除、查找等算法。
关于这方面的探讨我们以后的文章再做说明。
附：HashMap put 方法逻辑图（JDK1.8）
