HashMap为何数组的长度是2的n次方

• 1.这个方法非常巧妙， 它通过 h & (table.length -1) 来得到该对象的保存位， 而HashMap 底层数组的长度总是 2 的 n 次方， 2n-1 得到的二进制数的每个位上的值都为 1，那么与全部为 1 的一个数进行与操作， 速度会大大提升。

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

• 3.当数组长度为 2 的 n 次幂的时候， 不同的 key 算得的 index 相同的几率较小，那么数据在数组上分布就比较均匀， 也就是说碰撞的几率小， 相对的， 查询的时候不用遍历某个位置上的链表， 这样查询效率也就较高了。

HashMap 的扩容机制：

而负载因子表示一个散列表的空间的使用程度，有这样一个公式：initailCapacity*loadFactor=HashMap的容量。

所以负载因子越大则散列表的装填程度越高，也就是能容纳更多的元素，元素多了，链表大了，所以此时索引效率就会降低。

反之，负载因子越小则链表中的数据量就越稀疏，此时会对空间造成烂费，但是此时索引效率高。

当 HashMap 中的结点个数超过数组大小loadFactor（加载因子） 时， 就会进数组扩容，loadFactor 的默认值为 0.75。也就是说，默认情况下，数组大小为 16，那么当 HashMap中结点个数超过 160.75=12 的时候， 就把数组的大小扩展为2*16=32， 即扩大一倍， 然后重新计算每个元素在数组中的位置， 并放进去， 而这是一个非常消耗性能的操作。

多线程下 HashMap 出现的问题：

• 1.多线程 put 操作后， get 操作导致死循环,导致 cpu100%的现象。 主要是多线程同时put 时， 如果同时触发了 rehash 操作， 会导致扩容后的 HashMap 中的链表中出现循环节点， 进而使得后面 get 的时候， 会死循环。

• 2.多线程 put 操作， 导致元素丢失， 也是发生在多个线程对 hashmap 扩容时。

HashMap 和 HashTable 的区别

• 1. Hashtable 是线程安全的， 方法是 Synchronized 的， 适合在多线程环境中使用， 效率稍低； HashMap 不是线程安全的， 方法不是 Synchronized 的， 效率稍高， 适合在单线程环境 下 使 用 ， 所 以 在 多 线 程 场 合 下 使 用 的 话 ， 需 要 手 动 同 步 HashMap ，Collections.synchronizedMap()。

• 2.HashMap 的 key 和 value 都可以为 null 值， HashTable 的 key 和 value 都不允许有 Null 值。

• 3.HashMap 中数组的默认大小是 16， 而且一定是 2 的倍数， 扩容后的数组长度是之前数组长度的 2 倍。 HashTable 中数组默认大小是 11， 扩容后的数组长度是之前数组长度的 2 倍+1。

• 4.哈希值的使用不同

• 5 HashMap 重新计算 hash 值， 而且用&代替求模

HashTable 的效率比较低的原因

在线程竞争激烈的情况下 HashTable 的效率非常低下。 因为当一个线程访问HashTable 的同步方法时， 访问其他同步方法的线程就可能会进入阻塞或者轮训状态。 如线程 1 使用 put 进行添加元素， 线程 2 不但不能使用 put 方法添加元素， 并且也不能使用get 方法来获取元素， 所以竞争越激烈效率越低

判断是否含有某个键

在 HashMap 中， null 可以作为键， 这样的键只有一个； 可以有一个或多个键所对应的值为 null。 当 get()方法返回 null 值时， 既可以表示 HashMap 中没有该键， 也可以表示该键所对应的值为 null。 因此， 在 HashMap 中不能用 get()方法来判断 HashMap 中是否存在某个键， 而应该用 containsKey()方法来判断。 Hashtable 的键值都不能为 null， 所以可以用 get()方法来判断是否含有某个键。