蚂蚁花呗：阿里巴巴面试：Java 集合知识点（附图文解析）( 五 ) 支付宝|第三方支付

所谓 “拉链法” 就是将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

源码解析构造方法《阿里巴巴 Java 开发手册》推荐集合初始化时，指定集合初始值大小。（说明：HashMap 使用HashMap(int initialCapacity) 初始化）

转发后，关注+私信回复小编“666”免费获取《阿里巴巴 Java 开发手册》

HashMap 的前 3 个构造方法最后都会去调用 HashMap(int initialCapacity float loadFactor)。在其内部去设置初始容量和加载因子。而最后的 init() 是空方法，主要给子类实现，比如 LinkedHashMap 。
put() 方法
最后的 createEntry() 方法就说明了当 hash 冲突时，采用的拉链法来解决 hash 冲突的，并且是把新元素是插入到单边表的表头。
get() 方法
JDK1.8 实现JDK 1.7 中，如果哈希碰撞过多，拉链过长，极端情况下，所有值都落入了同一个桶内，这就退化成了一个链表。通过 key 值查找要遍历链表，效率较低。 JDK1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
TreeMap、TreeSet以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
源码解析构造方法JDK8 构造方法改动不是很大
确定哈希桶数组索引位置（hash 函数的实现）
HashMap定位数组索引位置，直接决定了hash方法的离散性能。 Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
hash

为什么要这样呢？
HashMap 的长度为什么是2的幂次方?

目的当然是为了减少哈希碰撞，使 table 里的数据分布的更均匀。

HashMap 中桶数组的大小 length 总是2的幂，此时， h & (table.length -1) 等价于对 length 取模 h%length 。但取模的计算效率没有位运算高，所以这是是一个优化。假设 h = 185 ， table.length-1 = 15(0x1111) ，其实散列真正生效的只是低 4bit 的有效位，所以很容易碰撞。 img
图中的 hash 是由键的 hashCode 产生。计算余数时，由于 n 比较小， hash 只有低4位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的 hash 高4位数据与低4位数据进行异或运算，即 hash ^ (hash >>> 4) 。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下：img在 Java 中， hashCode 方法产生的 hash 是 int 类型， 32 位宽。前16位为高位，后16位为低位，所以要右移16位，即 hash ^ (hash >>> 16)。这样还增加了hash 的复杂度，进而影响 hash 的分布性。

put() 方法
resize() 扩容
get() 方法
HashtableHashtable 和 HashMap 都是散列表，也是用”拉链法“实现的哈希表。保存数据和 JDK7 中的 HashMap 一样，是 Entity 对象，只是 Hashtable 中的几乎所有的 public 方法都是 synchronized 的，而有些方法也是在内部通过 synchronized 代码块来实现，效率肯定会降低。且 put() 方法不允许空值。
使用次数太少，不深究。
HashMap 和 Hashtable 的区别