HashMap Java 1.7 解析

定义：基于哈希表的Map接口实现类。

继承了AbstractMap抽象类，实现了Map接口，实现了Cloneable接口，实现了Serializable接口。
不保证有序（如插入顺序）
初始容量是16，最大容量是2^30
允许 null 的键/值。key=null时，放在数组第0个位置，hash值为0。

对比HashTable，由于HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null。
非线程安全（非同步）。可通过 Collections.synchronizedMap(new HashMap())获得线程安全的HashMap.
在第一次put()时会初始化数组。

/**
     * 函数源码分析2：indexFor(hash, table.length)
     * JDK 1.8中实际上无该函数，但原理相同，即具备类似作用的函数
     */
      static int indexFor(int h, int length) {  
          return h & (length-1); 
          // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）

问题1： 为什么不直接采用经过hashCode（）处理的哈希码作为存储数组table的下标位置？

为了解决 “哈希码与数组大小范围不匹配” 的问题，HashMap给出了解决方案：哈希码与运算（&）（数组长度-1）；
问题2： 为什么采用哈希码与运算(&) （数组长度-1）计算数组下标？

首先，数组长度是2的次幂，二进制表示就是首位为1，其他位都为0，如果直接和hash码做&运算的话，得到的数组索引结果都是偶数，相当于浪费了一般的数组空间。如果（数组长度-1）首位为1，低位为1，和hash码做&运算的结果有哈希码决定，可能为1或0，这样保证了计算后的数组存储位置的均匀性，降低了hash冲突。

其次，h & (length-1)相当于h % length，即hash值对数组长度取模。之所以与(&)运算，而非求余(%)，是为了提高运算效率。
问题3：为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？

增大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少Hash冲突。
为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键
- final类型，保证了key的不可变性。
- 内部已重写了hashCode() 、equals()方法。
HashMap 中的 key若 Object类型，则需实现哪些方法？

实现 hashCode() 、equals()。
- hashCode()：计算需存储数据的存储位置。实现不恰当会导致严重的hash冲突。
- equals()：比较存储位置上是否存在存储数据的键 Key，保证键 Key 在哈希表中的唯一性。存在，则更新value值即可。不存在，则直接插入数据。

插入前，先判断容量是否足够，若不足够，则进行扩容（2倍）、重新计算Hash值、重新计算存储数组下标。
若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值。
扩容时，根据新容量（2倍容量）新建1个数组，即新table 。将旧数组上的数据（键值对）转移到新table中，从而完成扩容。然后重新设置阈值 threshold = (int)(newCapacity * loadFactor);
键值对的添加方式：单链表的头插法
- 即将该位置（数组上）原来的数据放在该位置的（链表）下1个节点中（next）、在该位置（数组上）放入需插入的数据-> 从而形成链表。
- 在扩容resize（）过程中，在将旧数组上的数据转移到新数组上时，转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况。
- 此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现环形链表，从而在获取数据、遍历链表时形成死循环（Infinite Loop），即死锁的状态 = 线程不安全 。

1
2
3

注意：由于 `JDK 1.8` 转移数据操作 = **按旧链表的正序遍历链表、在新链表的尾部依次插入** ，所以不会出现链表 **逆序、倒置** 的情况，故不容易出现环形链表的情况。

但 `JDK 1.8` 还是线程不安全，因为 无加同步锁保护

核心参数：
- 数组（Table）的大小 =容量的大小（capacity）。默认容量是16。容量范围必须是2的次幂 & < 最大容量（2^30)。
- 加载因子（loadFactor） = 0.75。
- 扩容阈值（threshold） = 容量（capacity） * 加载因子（loadFactor）
- HashMap 大小 = 数组长度 + 所有链表的长度。

参考：Java：这是一份全面 & 详细的HashMap 1.7源码分析指南

HashMap Java 1.7 解析

为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键