HashMap总结

1.底层数据结构，1.7和1.8的不同

1.7：数组（初始大小为16）+链表

1.8：数组（初始大小为16）+（链表or红黑树），链表长度超过 8 的时候，会将链表转化为红黑树来提高查询效率（组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）。当节点数小于6时，红黑树将退化成链表

2.键的索引如何计算

1.7：

static int hash(int h) {
 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

1.8：

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

jdk1.7的hash方法扰动了4次，而jdk1.8的hash方法更加简洁。首先调用hashcode方法获取键（key）的哈希码，并将其与右移 16 位的哈希码进行异或运算。然后hash的结果与数组容量进行取模操作（hash&（length - 1），需要length为2的幂次方），这个余数就是对应的数组的下标，然后存放键在对应下标的位置。

3.为什么得到哈希码之后要进行二次hash操作

把哈希值右移 16 位，也就正好是自己长度的一半，之后与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，让数据元素更加均衡的分布，增大了随机性。

4.扩容机制

HashMap 的扩容是通过 resize 方法来实现的，该方法接收一个新的容量 newCapacity，然后将 HashMap 的容量扩大到 newCapacity：

获取旧数组及容量：如果旧容量已经达到 HashMap 支持的最大容量 MAXIMUM_CAPACITY（ 2 的 30 次方），就将新的阈值 threshold 调整为 Integer.MAX_VALUE（2 的 31 次方 - 1）
创建新数组并转移元素：将旧数组 oldTable 中的元素转移到新数组 newTable 中。转移过程是通过调用 transfer 方法来实现的。该方法遍历旧数组中的每个桶，并将每个桶中的键值对重新计算哈希值后，将其插入到新数组对应的桶中。
重新计算阈值 threshold：转移完成后，方法将 HashMap 内部的数组引用 table 指向新数组 newTable，并重新计算阈值 threshold：

threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

5.新的容量如何计算

新容量 newCapacity 被初始化为原容量 oldCapacity 的两倍
如果 newCapacity 超过了 HashMap 的容量限制 MAXIMUM_CAPACITY（2^30），就将 newCapacity 设置为 MAXIMUM_CAPACITY
如果 newCapacity 小于默认初始容量 DEFAULT_INITIAL_CAPACITY（16），就将 newCapacity 设置为 DEFAULT_INITIAL_CAPACITY

6.jdk1.7扩容机制中如何将旧的小数组元素拷贝到新的大数组中

通过transfer方法实现，该方法接受一个新的 Entry 数组 newTable 和一个布尔值 rehash 作为参数，其中 newTable 表示新的哈希表，rehash 表示是否需要重新计算键的哈希值：

遍历旧哈希表中的每个 Entry：如果 rehash 为 true，则需要重新计算键的哈希值，根据新哈希表的长度和键的哈希值，计算 Entry 在新数组中的位置 i。
头插法：由于新元素需要被放在链表的头部，因此将新元素的下一个元素设置为当前数组位置上的元素。

头插法存在问题：扩容后可能会改变原来的顺序

7.jdk1.8扩容机制改进

差别主要在hash方法上，当数组长度为 2 的幂次方时，能够很巧妙地解决 JDK 7 中遇到的问题。1.8的hash方法如下（与上文一致）：

    static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

数组扩容后的索引位置，要么就是原来的索引位置，要么就是“原索引+原来的容量”，遵循一定的规律。

8.数组长度为什么是2的幂次方

如果使用2的幂次方，可以用按位与操作替换取模操作，提升计算效率（当length为2的幂次方时，hash%length=hash&(length-1)）
当数组进行扩容的时候，需要将链表中的元素逐个遍历，将每个元素的hash值 & 原来的容量如果=0，说明留在原地，如果不等于0，说明需要移动到新位置。然后用两个链表分别存放，最后通过原桶下标位置 + 旧数组容量就可以直接移动到新的桶下标位置，一次性移动

9.HashMap的put流程

创建：hashmap的数组是懒惰初始化的，只有第一个元素插入的时候才会创建
计算hash：获取键的哈希码，然后进行hash运算，最后按位与得到元素存放的下标
判断下标是否有元素：如果没有，创建Node节点，然后放入
如果有：
如果是TreeNode，说明已经是树化了，那么需要走红黑树的更新逻辑
如果是Node，那么走链表的更新逻辑，如果链表长度达到树化阈值，那么需要走树化逻辑。1.7是头插法，1.8是尾插法
扩容，1.7超过扩容阈值不会马上扩容，需要判断是否有空位，如果没有在进行扩容， 1.8是超过扩容阈值就马上扩容（1.8有优化：按位与原来的容量判断是否0）

10.负载因子为什么是0.75

为了在时间和空间成本之间达到一个较好的平衡点，既可以保证哈希表的性能表现，又能够充分利用空间。
如果负载因子过大，填充因子较多，那么哈希表中的元素就会越来越多地聚集在少数的桶中，这就导致了冲突的增加，这些冲突会导致查找、插入和删除操作的效率下降。
如果负载因子过小，那么桶的数量会很多，虽然可以减少冲突，但会导致更频繁地扩容，在空间利用上面也会有浪费。

11.线程不安全：put 会导致元素丢失

两个线程同时判断一个位置是null，所以同时创建了节点准备插入桶下标，然后其中一个插入完成，另一个进行了覆盖，造成了一个数据丢失

12.线程不安全：扩容会死循环（1.7头插法出现）

线程1进行扩容，会有两个临时变量e和next，分别指向第一个跟第二个节点（a和b），然后准备进行扩容的时候，发生了线程上下文切换
线程2执行了，他也有两个临时变量，然后进行扩容，扩容之后，因为1.7使用的是头插法，所以原就数组链表中的元素比如a 指向 b，会变成 b 指向a，然后扩容完成
切换会线程1，他还会执行完扩容流程，此时线程1的 e 和 next还是原先的a 和 b，但是此时他们的顺序已经发生了改变，此时e是a插入，然后next是b，然后e插入a之后，获取next值，也就是b，然后插入，next值就会去获取下一个节点的值，因为刚才线程2扩容使得两个节点顺序发生了改变，b指向了a，然后此时next值是a，那么刚才已经插入过 a了，此时又插入了a，那么链表的顺序是 a和b两个节点互相指向，造成了死循环

13.线程不安全：put 和 get 并发时会导致 get 到 null

因为线程 1 执行完 table = newTab 之后，线程 2 中的 table 此时也发生了变化，此时去 get 的时候当然会 get 到 null 了，因为元素还没有转移

14.重写HashMap的equal和hashcode方法需要注意什么？

HashMap使用Key对象的hashCode()和equals()方法去决定key-value对的索引。当我们试着从HashMap中获取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，在这种情况下，两个不同Key也许会产生相同的hashCode()和equals()输出，HashMap将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方

15.重写HashMap的equal方法不当会出现什么问题

HashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。所以 equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等。
重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回false，这样的一个后果会导致在hashmap等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与hashmap只能有唯一的key的规范不符合
另外作为key的对象需要是不可变类，不然对象被修改了，下次hashcode值发生了改变就找不到了。

16.为什么要用红黑树，为什么一上来不树化