HashMap原理

HashMap是将数组和链表的有点结合起来实现的。

数组：在内存中存储连续，访问速度较快，但是插入删除需要移动，所以比较慢，插入和删除时间复杂度是O(N)，遍历复杂度是O（1）

链表：在内存中存储不连续，依靠指针指向下一个元素，插入和删除比较快，遍历比较慢，插入和删除时间复杂度是O(1)，遍历复杂度是O（N）

HashMap 数组index的计算方法为：

/**

* Returns index for hash code h.

*/

staticintindexFor(inth,intlength) {

returnh & (length-1);

}

当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

index = hash(key) % array.length