通过哈希函数，能看出，首先调用 key 的hashCode 方法，接着无符号右移 16 位，即将 key 的高16位 与 低 16位 异或得到的 hash 值，通过这个也就在说明，我们如果是自定义类型的话，比如 Person，那么一定要重写 hashCode 方法，不然则是调用 Object 里的 hashCode 方法了。

　　接着我们再往下看，putVal 方法里面的逻辑，这里代码比较长，我们分段演示：

　　这里就是判断哈希表是否为有元素，如果表为 null 或者 哈希表的长度为 0，就会初始化数组(Node类型的数组)，即调用 resize() 方法。初始哈希表的长度是 16，临界阈值为 16 * 0.75 = 12，也就是数组元素达到 12个即会扩容。往后走代码：

　　这里作用是通过 hash 值得到索引 i，也就是数组的下标，判断这个位置是否有元素了，如果没有则直接 new 一个节点放到该处。反之走 else 就表示该数组下标已经有元素了。

　　如果得到的 i 索引处有元素，则需要判断当前下标元素的 hash 值是否与我们要插入的元素 hash 值相同，如果相同，接着判断 下标元素的 key 与我们要插入元素的 key一样，或者通过 equals 方法比较是一样了，则表示是同一个元素，则不用插入了，e 保存这个已经存在的元素。到这里也能发现，这其实就是 Map 底层不能有重复 key 的原因了。

　　那如果他们不相同的情况下，就会判断该下标 i 的位置值是不是红黑树的节点(到了一定条件哈希桶中的元素会采用红黑树来组织数据)，如果是，则采用红黑树的方式进行插入元素，这里我们就不往里面看了。

　　最后都不满足的情况，也就是元素不相同，并且不是红黑树结构，则走后面的 else，首先这个 else 里面是个死循环，要想退出，必须满足两个条件，① 找到了可以插入的地方，② 在哈希桶中发现了相同的元素。

　　比较该数组索引 i 下标的下一个节点，如果为 null，则直接插入该节点，如果链表长度大于8，则可能需要树化，也就是转换成红黑树，如果找到了相同的 key，则不用插入直接跳出循环。

　　上面的 else 走完后，如果存在添加相同的元素的时候，e 则不为 null，只需要将待添加元素的 value 值赋值给原本存在元素的 value 值即可，也就是更新一下元素的 value 值。afterNodeAccess 方法不用管，是使用 LinkedHashMap 实现的一个操作，这里并没有使用。

　　最后部分：

　　这里有效元素个数自增，如果超过了数组长度，则重新判断是否扩容（两倍扩容）。 afterNodeInsertion 也不用管，LinkedHashMap中的，这里也没有实际用途。

　　总结：HashMap 的 put 方法，是根据 key 的 hashCode 来计算 hash 值的，即我们要在自定义类型中重写 HashCode 方法，再者，是根据 equals 来判断 key 是否相同，也表示着我们同时需要去重写 equals 方法。

　　

3.3 哈希表下的链表，何时会树化？

　　在上述讲解 put 方法的时候，发现插入元素的时候，数组索引位置的链表不止一个元素的时候会判断是否要转换成红黑树，那么具体要达到什么条件才能转换成红黑树呢？我们直接看上述的 treeifyBin 方法即可。

　　树化的前提是，链表的长度大于等于 8，就会树化，因为是从 binCount 是从 0 开始的，所以 TREEIFY_THRESHOLD - 1。那么链表的长度大于等于 8，一定会从链表变成红黑树吗？我们往后看：

　　第一个 if 当哈希表为空，或者表(数组)的长度小于64，只进行扩容即可，不会转换成树，当哈希表的长度大于 64，才有可能转换成红黑树。

　　所以我们最终得出，HashMap 中哈希表下的链表，当链表长度大于等于 8，并且哈希表的长度大于等于 64 则会将此链表转换成红黑树。

4、相关面试题

4.1 链表转换成红黑树如何比较？

　　前面我们学过 TreeMap TreeSet 底层就是红黑树，里面的元素必须是可比较的，那哈希表下的链表转换成红黑树之后，没有重写 compareTo 怎么办呢？这里会按照 key 的哈希值来进行比较，所以就算转换成红黑树后，也不会关于 key 有序，再者可能只是哈希表其中一个索引位置下的结构是红黑树，其他的仍然可能是链表。

4.2 hashCode 和 equals 的区别

　　hashCode 是虚拟出对象的地址，底层是 native 封装的，即 C/C++实现的，而 equals 则是比较两个对象是否相同。

　　当我们重写 hashCode 的时候，是调用 Objects 里面的 hash 方法：